ARC148游记

A - mod M

题目链接

10年积累的网站设计、成都网站建设经验，可以快速应对客户对网站的新想法和需求。提供各种问题对应的解决方案。让选择我们的客户得到更好、更有力的网络服务。我虽然不认识你，你也不认识我。但先网站设计后付款的网站建设流程，更有石家庄免费网站建设让你可以放心的选择与我们合作。

这道题我们可以首先对于所有的数 \(\mod 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题代码