扫二维码与项目经理沟通
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
题目链接
10年积累的网站设计、成都网站建设经验，可以快速应对客户对网站的新想法和需求。提供各种问题对应的解决方案。让选择我们的客户得到更好、更有力的网络服务。我虽然不认识你，你也不认识我。但先网站设计后付款的网站建设流程，更有石家庄免费网站建设让你可以放心的选择与我们合作。
这道题我们可以首先对于所有的数 \(\mod 2\) ，可以证明出答案最多不超过 \(2\) ，此时我们就可以把问题转化为：是否存在一个数使得序列 \(a\) 中所有元素减去这个数之后的最大公因数大于\(1\)，就是一道妥妥的同余了。
A题代码
题目链接
这道题我们可不难想出\(O(n^3)\)的做法，即枚举左端点和右端点，检查这段区间的答案变换过后是否比当前答案更小，如果是，则更新当前答案。
然后就是优化了，我们可以发现，从开头开始，我们遇到的第一个 \(p\)，是一定得被修改成 \(d\) ，这样肯定是最优选择，那么我们就可以省略了枚举左端点的步骤，此时时间复杂度为\(O(n^2)\)，足以通过此题。
B题代码
题目链接
这道题我们首先有一些性质:
1.每个节点最多按一次
2.节点按下的先后顺序没有影响
依据这个性质，我们可以得到：当一个硬币头朝上时，要按下这个节点按钮的最佳选择是：
1.这个节点的父亲是尾朝上
2.这个节点的子树全是头朝上
对于第一点，我们可以由性质1证明出来，如果这个节点的父亲是头朝上，那我们就再等到他父亲再继续。
然后对于第二点，依据性质2，我们可以假设如果一个节点在一开始表明头朝上了，我们遍历到他的父亲时，这个节点里的所有子树都已经头朝上了(有点类似于 动态dp 的思路?)，反之，这个节点里所有子树都已经尾朝上，我们就需要按下这个节点的按钮。
C题代码
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
微信二维码
移动版官网