23/10/02 NOIP模拟赛总结
时间安排
1:50-2:40 先看了T1和T2，直接过样例。
2:40-3:00 T3没想到正解，先把40%打了。
3:00-3:50 上了个厕所，发现T3正解直接枚举，写完和自己的暴力对拍。
3:50-4:00 看了看后3题，感觉都不好做。
4:00-4:50 感觉T4是DP，但不会设状态，去打T5,T6暴力。
4:50-5:40 写了T4DP做法，但是赛时忘了重置dp数组，100->20。
5:40-5:50 检查了一遍，交题。
反思总结
1.多遍DP，不要忘了清空dp数组。
2.T2没有对拍，赛时害怕写错，但没留出足够时间对拍。
简要题解：
T1:
\(k \le 2021\)，直接预处理，\(O(1)\) 询问。
T2:
每向右循环移动一位，答案只加上一个数，减去一个数。
当向右循环移动 \(n\) 位时，新数组与原始数组一致，预处理向右循环移动 \(k\) 位的答案，其中 \(0 \le k \le n-1\)。
T3:
\([l,r]\) 中任选两个数，它们的最大公约数一定小于等于 \(r\)，从 \(1\) 到 \(r\) 枚举每个可能的公约数，判断在 \([l,r]\) 的区间中，含有这个约数的数字是否有多个。
T4:
设 \({f}_{i,0/1}\) 表示第 \(i\) 个位置修与不修。
修改后的状态有两种：
1.峰谷峰谷峰谷峰谷...
2.谷峰谷峰谷峰谷峰...
DP两种状态，在DP过程中判断当前位置的奇偶性。
T5:
我们每次选择叶子，从叶子开始不断向父亲跳，直到当前的直链满足条件。若跳到根还是不合法或者该过程中存在1个点已经被划分到了另1条直链上，那么一定无解。否则将该直链加入划分方案。
标签：20231002,le,峰谷,00,40,50,DP From： https://www.cnblogs.com/Kai-benefit/p/17741088.html