526互联

AtCoder Regular Contest 138

发布时间 2024-01-11 21:09:44作者: Alan_Zhao_2007

比赛链接

A - Larger Score

将一个 \(i\) 交换出前 \(K\) 个并将一个 \(j\) 交换进前 \(K\) 个需要的次数是 \(j-i\)。

于是只需要对于每个 \(j>K\) 找最大的 \(i\le K\) 使得 \(A_i<A_j\)。

B - 01 Generation

每次将末尾的所有 \(0\) 消去，然后只要第一个位置不是 \(0\) 就无解。否则消去第一个位置然后将整个串取反。

C - Rotate and Play Game

为什么如此困难？？？

考虑答案的上界，是前 \(\frac{N}{2}\) 大的数之和。由于可以自由地选起始位置，大胆猜想一定可以取到这个上界。

将前 \(\frac{N}{2}\) 大的数标为 \(-1\)，其他数标为 \(1\)，我们需要将整个数组循环移位使得所有前缀和均非负。这是简单的，将最小前缀和的位置移到最前面即可。

D - Differ by K bits

\(K=1\) 时是格雷码，构造是简单的。

考虑将格雷码中每个数的每一位都看作一个二进制数，也就是说有一个数组 \(b_0,b_1,\dots,b_{N-1}\)，对于格雷码中的一个数 \(x\)，设它当中的所有 \(1\) 位是 \(k_0,k_1,\dots,k_l\)，将它映射到 \(f(x)=b_{k_0}\operatorname{xor} b_{k_1}\operatorname{xor} \dots \operatorname{xor} b_{k_l}\)。

由于相邻两个数的异或需要 \(\operatorname{popcount}=K\)，所以所有的 \(b_i\) 的 \(\operatorname{popcount}\) 也都需要是 \(K\)。这些数还需要互不相同，所以 \(f(x)\) 也需要互不相同。

于是只需要找出 \(N\) 个线性无关的 \(\operatorname{popcount}=K\) 的数，将它们作为 \(b_0,\dots,b_{N-1}\) 即可。

E - Decreasing Subsequence

写了个 \(O(N^3)\) DP，结果和正解一点关系也没有，绷不住了。

对于所有 \(A_i\neq 0\) 的 \(i\)，连边 \(i\to (A_i-1)\)，这样形成的图是若干条从大指向小的链。一个下降子序列的形态就是 \(2K\) 个下标 \(0\le L_K<L_{K-1}<\dots<L_1<R_1<R_2<\dots<R_K\le N\)，其中 \(R_i\to L_i\) 有边。

一个下降子序列是 \(2K\) 个链上的 \(2K\) 条边。将这 \(2K\) 条链从下降子序列的位置断开，设 \(i\) 为 \(2K\) 条链断开后左边部分的大小之和，\(j\) 为右边部分的大小之和。计数：

  • \(\binom{n+1}{i+j}\) 枚举链上的点；
  • \({i\brace K}{j\brace K}\) 枚举链划分；
  • \(\sum_{x} {{n+1-i-j}\brace x}\) 枚举剩下的数的链划分。

时间复杂度 \(O(N^2)\)。