PtzWC 2018, Yandex Cup

F. Shuffle

• 将标号变为 0∼n−10 \sim n - 10∼n−1，则
  shuffle(s)=s0s2…sn−2s1s3…sn−1\text{shuffle}(s) = s_0s_2\dots s_{n-2}s_1s_3\dots s_{n - 1} shuffle(s)=s0​s2​…sn−2​s1​s3​…sn−1​
• 设 pip_ipi​ 表示 iii 变换后得到的标号，则
  pi={i2,if iis eveni−12+n2,if iis oddp_i = \begin{cases} \frac{i}{2}, \text{if}\ i\ \text{is}\ \text{even} \\\frac{i - 1}{2}+\frac{n}{2},\text{if}\ i\ \text{is}\ \text{odd}\end{cases} pi​={2i​,if i is even2i−1​+2n​,if i is odd​
• i→pii \to p_ii→pi​ 构成若干个轮换，通过 KMP\text{KMP}KMP 可以求出每个轮换上 sss 在一个周期（轮换的长度）内逆序循环位移能得到 ttt 的位移次数（注意不止一个，且最少的不一定是最后答案的限制条件），可以得到若干同余方程的限制形式。
• 注意到：
  • 当 i=n−1i = n - 1i=n−1 时，pi=ip_i = ipi​=i
  • 当 0≤i
• 通用的可能思考方向，∑pi=n(pi≥0)\sum p_i = n(p_i \ge 0)∑pi​=n(pi​≥0)，pip_ipi​ 至多有 O(n)\mathcal O(\sqrt n)O(n​) 种。
• 由欧拉定理 2φ(n−1)≡1(mod(n−1))2^{\varphi(n - 1)} \equiv 1(\mod (n-1))2φ(n−1)≡1(mod(n−1)) 且 Ordn(2)∣φ(n−1)\text{Ord}_n(2)|\varphi(n - 1)Ordn​(2)∣φ(n−1)，故轮换的长度均为 φ(n−1)\varphi(n - 1)φ(n−1) 的约数，我们可以将同种长度的限制条件整合到一起，不同的环长至多有 O(n)\mathcal O(\sqrt n)O(n​) 种，因而总时间复杂度 O(φ(n−1)n)\mathcal O(\varphi(n - 1)\sqrt n)O(φ(n−1)n​)。
• Code

I. ≤ or ≥

• 若只是简单地取中位数，可能会被刻意构造使得某个栈内元素始终无法取出。
• 考虑给深度为 ddd 的栈赋一个权重 f(d)=adf(d) = a^df(d)=ad，每次取加权中位数，则每次总的权重会变为原来的 12+f(d−1)2f(d)=a+12a\frac{1}{2}+\frac{f(d-1)}{2f(d)}=\frac{a+1}{2a}21​+2f(d)f(d−1)​=2aa+1​，总移动次数为 log⁡2aa+1(nak)\log_{\frac{2a}{a+1}}(na^k)loga+12a​​(nak)，通过计算可知 a=3a = 3a=3 时最优。
• Code

PtzWC 2022. Day 1. Kyoto U Contest 2

G. Game with Balls and Boxes

• 首先可以单独考虑每个轮换，轮换间元素的交换显然是无用的。
• 在某个轮换中，若所有盒子均在第一次打开，直接结束；否则若第一次打开的盒子被分成几段，每段最左边的盒子和没有被打开的盒子均需要在第二次被打开，由此做线性 DP 即可。
• Code

K. King’s Palace

• 考虑 meet-in-the-middle\text{meet-in-the-middle}meet-in-the-middle。
• 取 n1=n−⌊n3⌋n_1 = n - \lfloor \frac{n}{3} \rfloorn1​=n−⌊3n​⌋，n2=⌊n3⌋n_2 = \lfloor \frac{n}{3} \rfloorn2​=⌊3n​⌋，暴搜前 n1n_1n1​ 面墙，将与之冲突的后 n2n_2n2​ 面墙的刷法用 3n23n_23n2​ 位二进制数 sss 压缩，方案数记为 fsf_sfs​，对 fsf_sfs​ 做 FMT，再爆搜后 n2n_2n2​ 面墙，记这 n2n_2n2​ 面的刷法对应的二进制数为 s′s's′，则将答案加上 f(23n2−1)⊕s′f_{(2^{3n_2} - 1) \oplus s'}f(23n2​−1)⊕s′​。
• 总时间复杂度 O(n13n1+n23n2+3n223n2)\mathcal O(n_13^{n_1}+n_23^{n_2}+3n_22^{3n_2})O(n1​3n1​+n2​3n2​+3n2​23n2​)
• Code

PtzWC 2022. Day 2. KAIST Contest + KOI TST 2021

A. Points

• 碰到 max⁡/min⁡\max/\minmax/min 后接常数项时，可考虑取某一项的限制条件。
• 当 ux+vx≥uy+vyu_x + v_x \ge u_y + v_yux​+vx​≥uy​+vy​ 时，即当 ux−uy≥vy−vxu_x - u_y \ge v_y - v_xux​−uy​≥vy​−vx​ 时，取 ux+vxu_x + v_xux​+vx​，否则取 uy+vyu_y + v_yuy​+vy​。
• 将 ux−uyu_x - u_yux​−uy​ 作为 uuu 的下标，将 vy−vxv_y - v_xvy​−vx​ 作为 vvv 的下标，将所有 u,vu,vu,v 存在一棵线段树内，则所有取 ux+vxu_x + v_xux​+vx​ 项的最小值相当于取一个 uuu 和一个 vvv，使得 uuu 的下标大于等于 vvv，所有取 uy+vyu_y + v_yuy​+vy​ 项的最小值相当于取一个 uuu 和一个 vvv，使得 uuu 的下标小于等于 vvv，容易用线段树维护。
• Code

C. AND or PLUS

• 设 i=x∨y,j=x∨zi = x \vee y, j = x \vee zi=x∨y,j=x∨z，则
  Ai+Aj
• 固定 x,yx,yx,y，设 f(z)=Ax∨y∨z−Ax∨zf(z) = A_{x\vee y\vee z} - A_{x \vee z}f(z)=Ax∨y∨z​−Ax∨z​，则上式等价于
  f(∅) 若存在解 (x,y,z)(x, y, z)(x,y,z)，则存在解 (x∨(z−lowbit(z)),y,lowbit(z))(x \vee (z - \text{lowbit}(z)), y, \text{lowbit}(z))(x∨(z−lowbit(z)),y,lowbit(z))。
• 交换 i,ji,ji,j，同理可证，若存在解 (x,y,z)(x, y, z)(x,y,z)，则存在解 (x∨(y−lowbit(y)),lowbit(y),z)(x \vee (y - \text{lowbit}(y)),\text{lowbit}(y),z)(x∨(y−lowbit(y)),lowbit(y),z)。
• 可推出，若存在解 (x,y,z)(x,y,z)(x,y,z)，则存在解 (x∨(y−lowbit(y))∨(z−lowbit(z)),lowbit(y),lowbit(z))(x \vee (y - \text{lowbit}(y)) \vee (z - \text{lowbit}(z)), \text{lowbit}(y),\text{lowbit}(z))(x∨(y−lowbit(y))∨(z−lowbit(z)),lowbit(y),lowbit(z))。
• 因而直接枚举即可，时间复杂度 O(N22N)\mathcal O(N^22^N)O(N22N)。
• Code

L. Curly Pacetrack

• 首先需要将横向和纵向的道路分开考虑，只有瓷砖内恰好有一个方向的横向道路和一个方向的纵向道路才能算 curly tiles\text{curly tiles}curly tiles。
• 以横向道路为例，每次考虑每行两个相邻已铺好瓷砖之间的瓷砖摆放方案，不难证明，根据这两块瓷砖的横向道路方向是否相同，以及两块瓷砖之间需要摆放的瓷砖数量（包含 x ）的奇偶性，瓷砖摆放方案只有两种可能：
  1. 所有摆放的瓷砖均恰好有一个横向道路。
  2. 所有摆放的瓷砖只有一块不恰好有一个横向道路。
• 第 1 种情况不需要考虑 o 和 x 的分布，对于第 2 种情况：
  • 若所有需摆放的瓷砖的标记均为 o，无解。
  • 若需摆放的瓷砖的标记中存在 x，可令 x 所在瓷砖不恰好有一个横向道路以实现最大化 curly tiles\text{curly tiles}curly tiles。
  • 不属于以上两种情况，则需要在标记不为 o 的瓷砖中选择一个使其不恰好有一个横向道路。
• 纵向道路同理，我们需要使不恰好有一个横向道路和不恰好有一个纵向道路的瓷砖尽可能重叠，建出求二分图求最大匹配即可。
• Code