ARC136题解

这场 ARC 比较考验观察能力，就是找到切入点的能力。我会尽量在题解里给出一个观察的过程，至于证明，比猜到结论简单。这场暴露出来我的容易进死胡同的问题，也可能是人类本质。就是一种思路做不出来的时候跳不出来，思维僵化了。以后训练中得注意对想不出来的题尝试“跳出思维定势”。也可能只是 trick 掌握得不够，导致跳出来也不知道想啥。可以先多积累些思路，毕竟“思而不学则殆”。

C - Circular Addition

题面

收获的思路：

1. 在差分数组上看区间加减
2. 问最小操作次数时，找几个下界，尝试证明其最大值可以取到。证明时可以尝试把创造过程逆转为消除过程，因为消除时的信息更多，而创造是在“创造”信息。

我看到了第一个切入点“用差分数组处理区间加减问题”。如果您对这个题毫无头绪，可以先对着这句话看自己能想到哪一步。将目标数组看作环并作长为 $n$ 的差分数组，发现这个差分数组和一定为 0，而且每次操作一定是使得一个数 +1，一个数 -1。显然我们可以通过每次选择一正一负的一对位置操作来得到目标差分数组，操作次数为差分数组中正值之和。

然后我发现过不了最后一个样例，仔细一看发现其实也没能给出前两个样例的具体操作步骤，不太对劲。具体来说，就是可以交换差分数组上的操作顺序来获得额外的“全体 +1”buff，这个信息在差分数组里被丢掉了。从这时开始，我就开始想着怎么最大化这个 buff，以及是不是最大 buff 和零 buff 之间的所有值都能取到，陷入了苦战。

按照题解来讲的话，我们已经观察到了一个操作次数下界，还有另一个显然的下界，就是数组中的最大值。我们猜想：他们中的最大值是可以被取到的。然后反过来想将目标数组变为 0 的过程。我们发现这个思路在近达上一场比赛 ARC135D 中就出现过，需要学习一个。

实际应用中，这种猜想很可能会错，尤其是难题。所以姑且提出一个做题步骤：

1. 观察总结此前得到的事实，提出猜想
2. 代入样例，若有误返回1
3. 尝试证明，若证伪返回1
4. 如果证明或不会证而自信，开码
5. 如果没证出来且不太自信，多造点样例，再次手玩或对拍，若有误返回1，否则开码

按照步骤，我们应当代入样例。发现没问题，开始尝试证明。如果我们在每一时刻都能降低这一时刻的“差分数组下界$L_1$”和“最大值下界$L_2$”中的最大值，我们就构造性地证明了猜想的正确性。为了降低最大者，我们需要对$L_1$和$L_2$的大小做出假设来进行进一步推理。

1. $L_1<L_2$：此时数组中不可能有 0，否则为了从 0 增加到 $L_2$，差分数组中正值部分至少是 $L_2$，这与 $L_1<L_2$ 矛盾。于是全体 -1 即可，这样能使 $L_2$ 减小 1。
2. $L_1>L_2$：如果数组中有 0，我们只要挑选一段包含最大值的极大非零区间来全体 -1，这样能使 $L_1$ 减小 1。如果数组中没有 0，数组中一定有若干“山谷”，所以一定可以找一段极大的“连续最大值区间”（要求其左右不再是最大值）来减 1，这能使 $L_1$ 减小 1。
3. $L_1=L_2$：如果数组中有 0，一定是单调增加到 $L_2$ 再单调减小到 0，将非零部分 -1 即可同时减小 $L_1$ 和 $L_2$。如果数组中没有0，数组中一定有若干“山谷”。如果*极大的“连续最大值区间”*唯一，那么将其减 1 即可。否则，一定可以找到一个区间覆盖所有的最大值，例如除去最小值后获得的区间。将这个区间全体减 1 即可。

把这个过程反过来想会变得更难想，尤其是 $L_1=L_2$ 时的操作。所以这个“减小双下限最大值”的 trick 应该被加入知识库。

D - Without Carry

题面

收获：SOSdp

推荐博文：SOSdp，zeta transform 前者为后者前置知识，本题只需要学习前者。但是来都来了，为什么不都学一下呢？

读完博文直接就会做了，不会就看官方题解，不必多说。

E - Non-coprime DAG

题面

收获：我观察能力低下？

1. 不够耐心，一条思路还没想透彻就放弃
2. 可以把结论写出来，更容易发现规律，形式的不同会影响思考方式

在看题解之前，您至少应该发现“不可达”和“互质”并不等价，例如9可以经12和14到达35。并且经过了一定的思考。

对 $i<j$ ，考察 $i$ 是否可达 $j$ 。后文同余符号皆模 2 ，$f(i)$ 为 $i$ 的最小质因子。

1. $i\equiv 0,\;j\equiv 0$，此时一定可达。
2. $i\equiv 0,\;j\equiv 1$，此时来到了第一个重要观察：可以尝试经过 $j - f(j)$ 这一偶数到达 $j$ ，所以不超过 $j-f(j)$ 的偶数都 ok ，即要求$i\leq j-f(j)$。而比它大的偶数，和 $j$ 的差距已经小于其最小质因子了，没有机会走到 $j$ 了。
3. $i\equiv 1,\;j\equiv 0$，类似于 2 ，要求$i+f(i)\leq j$。
4. $i\equiv 1,\; j\equiv 1$，此时来到了第二个重要观察，也是我卡住的地方。由于我没有将上面的观察列出来，我并没有注意经过偶数到达奇数这条路，或者隐约觉得这效率低下。其实这个类比还是比较明显的，大脑好用时起码可以猜一个结论出来。先写结论：$i+f(i)\leq j-f(j)$ 即可。首先，两者都是奇数，这就决定了只加一个（一定为奇的）质因数并不能使 $i$ 到达 $j$ ，至少要加 2 个。如果想由偶数搭桥，显然i -> i+f(i) -> j-f(j) -> j的路径就是最优的。如果不这样做，要么 $i,j$ 有公因子（此时 $i+f(i)\leq j-f(j)$ 必成立，或者仍然可以理解为从偶数搭桥），要么还是需要转到 $j-fac(j)$ 再转到 $j$ ，其中 $fac(j)$ 是 $j$ 的某个因子。而这一个转变最少也要加 $f(i)$ ，转变后最少也要再加 $f(j)$ 到达 $j$ ，本质还是从偶数搭桥。

现在我们获得了“可达”的数学表达。我又卡在这里了（我去想 DAG 了并且没跳出来，悲）。注意到不等号左右的内容都很相似，并且右侧可以加1（因为模2的限制，两式仍然等价），尝试总结为一个式子。可以将不等式变形为：

1. $i+1\leq j$
2. $i+1\leq j-f(j)+1$
3. $i+f(i)\leq j$
4. $i+f(i)\leq j-f(j)+1$

可以总结为：

$i$ 可达 $j$ $\Leftrightarrow$ $up(i)\leq low(j)$，其中 $up(i)=(i\equiv0)?i+1:i+f(i)$，（注意这个 $+1$ ，这是因为 $i<j$ 不带等号）$low(j)=(j\equiv0)?j:j-f(j)+1$。

再次总结这个表达，对任意的 $i, j$，当且仅当 $up(i)\leq low(j)$ 或 $up(j)\leq low(i)$ 时他们之间可达，用区间语言表达就更干净：$[low(i), up(i))$ 与 $[low(j),up(j))$ 没有交点时可达（注意区间开闭）。于是题目变成：寻找有公共交点的区间族 $\{[low(i), up(i))\mid i\in\mathbb{N}\}$ ，使得 $\sum_{i}A_i$最大。随便做。