2022/03/21 做题记录

Codeforces Round #778 (Div. 1 + Div. 2, based on Technocup 2022 Final Round)

A

显然通过两次 reverse 可以使得任意两个元素相邻，找到最大值次大值即可。

code: /code/2022.3.20/A.cpp

B

考虑一个前缀如果出现次数超过一次，那么删掉它的第一位剩下的那一段也一定在后面出现过，每次删第一个字符即可。

code:/code/2022.3.20/B.cpp

C

从小到大合并并不好做，于是设 f(x) 表示从原序列中删除 x 分裂成的所有数，如果原序列中不存在 x 那么 x 一定被分裂成了 $\lfloor \frac{x}{2} \rfloor$ 和 $\lceil \frac{x}{2} \rceil$ ,递归即可，否则我们从原序列中删掉一个 x 即可（因为如果即使这个 x 不是当前查找的结果，我们也可以在需要它时把它用当前分裂的来代替）。

code: /code/2022.3.20/C.cpp

D

不会，还没补

E

考虑最后的公差一定是原序列中两个数的差（否则答案是 n-1），我们对公差根号分治

对于 $k \le \sqrt{n}$ 的，由于 $a_i - a_j = (i-j)*k$ 等价 $a_i - i*k = a_j - j*k$，于是我们把每个数和它前面第一个满足 $a_i - i*k = a_j - j*k$ 的数连边，用并查集维护最大集合大小即可。

对于 $k \gt \sqrt{n}$ 的，我们发现只可能是一个数和它前面的 $\sqrt {n}$ 个数，直接递推即可。

因为用了哈希表套了个卡时才过。。。

code: /code/2022.3.20/E.cpp

F

考虑不同方案只有 $2^n$ 种，我们只需要求出每一个种的排名，类似线段树的建出一颗树来，对于每一个节点我们设它离叶子的距离为 level[i],那么我们可以对于每个点求出后 $level_i$ 位 $2^{level_i}$ 种不同的选法中这个点代表的这一段的字典序的排名（在这一层所有点所有合并方案中的），对于每个点我们就合并它的两个子树，可以发现把第 $level_i$ 位变成 1 的影响就是把它的两个子树代表的段交换（我一开始认为还要 reverse，最后发现不用）所以我们就可以利用一个 pair 表示这种合并方案的字典序，之后对于这一层离散化即可，不难算出总状态数是 $n \log n$。

code: /code/2022.3.20/F.cpp

模拟赛

A

赛时

发现一方会输当切仅当放下任何一个棋子都会形成一个图案，想不到什么比爆算 sg 更好的方案 /yun

赛后

还没补

upd1:

还真是爆算。。。

赛时感觉不太对劲就没往下想

我们可以找出所有图案的所有放置位置（一共有 $n \times m \times k=270000$ 种）并把每一个用一个长度为 $n+m$ 的二进制串表示，这样我们对这个大小为 $2^{n+m}$ 次方数组做高维前缀和就能得到所有方案是否合法，我们再设 $dp[S]$ 表示 $S$ 这个状态是先手必胜还是必败，一个状态是先手必胜当且仅当它存在一个后继状态为先手必败。

我们发现 dp 和前缀和数组均为 bool ，考虑能不能用位运算来批量处理。

我们按每个数二进制前 21 位分块，这样每一块的大小就是 $2^6$，正好可以用一个 unsigned long long 来表示（这个数二进制第 i 位表示每一块的共同前缀 + i 所储存的数是多少）,这样我们就可以通过一个 mask 来取出多个值。

我们做高维前缀和的时候就是枚举二进制所有为 0 的位并尝试将其反转，对于后 6 位我们可以记录 $tmp1_i$ 表示 $[0,64)$ 中二进制第 i 位为 0 的位所对应的 mask ，于是我们可以用一次与将它们都取出来，而将第 i 位反转也就是加上 $2^i$，对应到 mask 上也就是右移 $2^i$位，于是我们可以把取出来的一个整体右移后再或上去，这样我们就解决了枚举二进制后 6 位，对于枚举前面的位直接整体或上去即可，复杂度 $\mathrm{O(2^{n+m-6}*nm)}$。

而对于 dp 我们设为 1 代表必胜，为 0 代表必败，那么我们可以对于每一个状态或上它的所有后继状态取反后的结果，最后再与上自己这位对应的高维前缀和对应的数组取反后的结果（因为终止状态的后继是什么都没用），对于枚举高位直接做就行，枚举低位我们预处理 $tmp2_i$ 表示 $[0,64)$ 中的 i 能通过将二进制原来为 0 的一位取反所得到的所有的数对应的 mask，这样转移时我们就可以枚举每一个数然后通过 mask 求出取反后这些位是否有 1，复杂度 $\mathrm{O}(2^{n+m-6} \times (n*m+2^6))$

注意一下转移顺序。。。

感觉这个想法比较厉害，利用位运算来批量处理数据。

code: /code/2022.3.21/game.cpp

B

赛时

发现答案是 1 的条件是 $x=y$

那么答案是 2 的条件就是操作一次后 $x = y$，也就是 $x + y - (x - y) = x-y$ (绝对值无所谓，因为 $f(x,y)=f(y,x)$),解得 $x = 3y$。

发现每一个形似 $ax = by$ 的等式都可以进行两种扩展，就是把 a,b 分别乘在等号的左面和右面

$a(x+y-(x-y)) = b(x-y)$解得 $bx = (2a+b)y$

于是可以得到每一种合法的 $(x,y)$ 都是由 $(a,b)$->$(b,2a+b)$得到的，可以写出如下代码：

int F(int x, int y) {
  if (x == y) return 1;
  if (x > y) swap(x, y);
  y -= x;
  if (y % 2) return 0;
  int tmp = F(x, y / 2);
  if (!tmp) return 0;
  return tmp + 1;
}

从原来定义考虑，因为进行的都是加减操作，我们可以将 x,y 分别除以它们的 gcd，这样它们就都是奇数，而在计算 F 的递归中，x，y 会保持互质（于是一定一奇一偶或两奇），而 x+y 每递归一次都会除 2 ，那么不合法的情况就是 $\frac{x+y}{gcd(x,y)}$ 不是 $2^n$。

因为原序列是排列，那么我们可以对于每一个数 $x$ 枚举 $2^n$中的 $n$ 和 $gcd(x,y)$（这个数必定是 x 的因数），这两个的方案数总体上都是 $log_2^n$ 级别的，于是我们一共有 $n log^2 n$ 个点对（实际上更少），离线下来树状数组即可。

code: /code/2022.3.21/func.cpp

upd1:

实际上，对于每一个 $2^k = a+b$，其中 a,b 有 $\mathrm{O}(2^k)$ 种，而 gcd 有 $\frac{n}{max(a,b)} = \mathrm{O}(\frac{n}{2^k})$ 种，所以总点对数是 $\mathrm{O}(n log n)$的

C

赛时

看起来就不可做。