AtCoder Regular Contest++ 220

A

\(n=2,3,5\) 无解。手动构造 \(n=1,6,8\) 然后可以递推 \(n\to n+3\) 的解：将最小值变成 \(4\) 个 \(2x\)。

时间复杂度 \(\mathcal O(n\log n)\)。

B

由树上邻项交换的相关结论以及打表可以发现合法置换的充要条件是置换环数量为 \(1\)，问题转化为求一个对 \((a_i,b_i)\) 的重排最大化 \(\sum[b_i=a_{i\bmod n+1}]\)。不难发现这是一个图论题。

考虑在 \(n\) 个点的有向图上连有向边 \(a_i\to b_i\)，称为白边。接下来要添加一些 \(b\to a\) 的黑边。黑白交替的形态等价于一个欧拉回路，条件为 \(in_i=out_i\) 并且忽略孤立点后图连通。

称非自环的黑边为非平凡黑边，目标即为最小化非平凡黑边个数。先考虑 \(in_i=out_i\) 的条件，这里就需要至少 \(ans=\frac{\sum|in_i-out_i|}{2}\) 条非平凡黑边，再考虑图连通的条件：如果原图忽略孤点图连通那么最终 \(ans\) 就是前述的 \(ans\)；否则考察原图每个连通块，如果一个连通块内部全都是 \(in=out\) 的点，那么需要让 \(ans\to ans+1\) 使得与外界连通。

时间复杂度 \(\mathcal O(n)\)。

C

记答案序列为 \(b\)，显然有 \(b_i\in\{0,a_i\}\)。

solution 1：扫描线地刻画一下操作，每次 \(i\to i+1\) 的决策形如插入若干 \(l=i+1\) 以及删除若干 \(r=i\) 的线段，并且将当前线段的 \(r\) 都设为 \(i+1\)。简单调整可以发现每个位置上只有删除或者只有加入，进一步地一定是删除最少的或者加入最少的。因此有一个状态设计是 \(dp_i\) 表示 \(r=p\) 的操作次数为 \(im+X\) 的最大 \(k'\)，这个是凸的可以直接 slope trick 做。

solution 2：考虑当前局面的最小操作次数是否 \(\leq k\)，每次尝试将 \(a_i\to 0\)。求一个序列的最小代价，如果当前扫到 \(p=n\) 做能删除就做删除一定是不劣的，但在后续扫的过程中可能变为加入，考虑用反悔贪心描述这个过程：当前选择删除但是准备反悔为添加。一次反悔可以以 \((m-a_i)\bmod m\) 的代价将当前位置的覆盖次数添加 \(m\)，因此用小根堆维护即可。

时间复杂度 \(\mathcal O(n\log n)\)。

*D

不会做。

考虑将完全图的边看作一个下三角网格，对于边 \(i<j\) 看成格点 \((i,j)\)，这样等价于在网格上移动，满足水平移动和垂直移动交替做且每个格子最多走一次。\(|v_i-v_{i+2}|=1\) 等价于每次移动到相邻格子上。

等价于求一个 LRUD 字符串，表示从 \((1, 2)\) 出发、在水平和垂直移动之间交替的有效移动序列。

考虑每次由三角的左上角走到右下角，一个优秀的操作是不断走之字形向左移动并且保证较高的空间使用率，但是需要根据 \(n\) 的奇偶性来讨论递归构造，具体地：

• \(n\leq 6\) 时手动构造 \((1,2)\to (n-1,n)\) 的序列。
• \(n\) 为偶数时可以 \((n-5,n-4)\to (n-1,n)\)，先做 \(n-4\) 的子问题然后再接上。
• \(n\) 为奇数时可以先做 \(n-6\) 的子问题。

E

tnag。

\(n\) 本身不好处理，大体思路是枚举 \(X\bmod C\) 然后二分 \(X\)，将 \(n\) 的作用看成一个二分时用来判定的量。

\(\boldsymbol{C=1}\)：

二分答案 \(mid\)，检查 \([0,mid]\) 中是否有合法的 \(X\)。将 \(\text{popcount}(x)<k\) 看成 \(0\)，\(\ge k\) 看成 \(1\)，就需要支持查询 \([0,mid+n-1]\) 内最长 \(1\) 连续段的长度。有这些量后容易完成判定。

• 求内部最长连续段长度：设 \(mid\in[2^h,2^{h+1})\)，那么发现 \([0,2^h-1]\) 以及 \([2^h,mid]\) 是独立的子问题，对于后者可以递归到 \([0,mid-2^h]\) 且 \(k-1\)。模仿最大子段和的计算：考虑上传信息 \((pre,suf,mx)\) 表示当前前缀区间内的最长 \(1\) 后缀，最长 \(1\) 前缀以及内部最长连续段长度，那么信息是可以合并的。

预处理后可以 \(\mathcal O(\log^2V)\) 查询。注意到这个过程事实上是在做倍增，因此可以 \(\mathcal O(\log V)\)，也就是说不撤销掉每次的信息。

\(\boldsymbol{C>1}\)：

枚举 \(X\bmod C\) 然后二分 \(kC+b\)，随机排序后期望进行 \(\log C\log V+C\) 次二分。

考虑拆成高位以及最低 \(5\) 位，我们认为最低 \(5\) 位是任意变化的，但是高位一定是 \(0,1,2,\cdots\) 不会越过的。这样对于一个区间，只需要关心第一个位置 \(\bmod 2^5\) 的取值，然后再套用 \(C=1\) 的做法即可合并。时间复杂度 \(\mathcal O(\text{poly}(C,k,\log V)+T(\log C\log V+C)\log V)\)。

进一步地可以对所有 \(X\bmod C\) 一起做二分，并且用倍增的思路，复杂度 \(\mathcal O(TC\log V)\)。