ARC148游记

A – mod M

题目链接

这道题我们可以首先对于所有的数 $%2$ ，可以证明出答案最多不超过 $2$ ，此时我们就可以把问题转化为：是否存在一个数使得序列 $a$ 中所有元素减去这个数之后的最大公因数大于$1$，就是一道妥妥的同余了。

A题代码

B – dp

题目链接

这道题我们可不难想出$O(n^3)$的做法，即枚举左端点和右端点，检查这段区间的答案变换过后是否比当前答案更小，如果是，则更新当前答案。

然后就是优化了，我们可以发现，从开头开始，我们遇到的第一个 $p$，是一定得被修改成 $d$ ，这样肯定是最优选择，那么我们就可以省略了枚举左端点的步骤，此时时间复杂度为$O(n^2)$，足以通过此题。

B题代码

C – Lights Out on Tree

题目链接

这道题我们首先有一些性质:

1.每个节点最多按一次

2.节点按下的先后顺序没有影响

依据这个性质，我们可以得到：当一个硬币头朝上时，要按下这个节点按钮的最佳选择是：

1.这个节点的父亲是尾朝上

2.这个节点的子树全是头朝上

对于第一点，我们可以由性质1证明出来，如果这个节点的父亲是头朝上，那我们就再等到他父亲再继续。

然后对于第二点，依据性质2，我们可以假设如果一个节点在一开始表明头朝上了，我们遍历到他的父亲时，这个节点里的所有子树都已经头朝上了(有点类似于 动态dp 的思路?)，反之，这个节点里所有子树都已经尾朝上，我们就需要按下这个节点的按钮。

C题代码