【八月】CF *1700 ~*1900
466C
想双指针 假的。
考虑直接分类讨论能不能取：一个点能取，当且仅当他在总和的 \(\frac{1}{3}\) 处或 \(\frac{2}{3}\) 处。
那就很好讨论了：遍历一遍数组，能做左断点就做，找到另一个时累加已经找到的左断点数。
20C
板子。
474D
直接 dp。然后用前缀和回答询问。
先对好的串求出数量：设 \(dp_i\) 为到当前有多少个，转移即为：$$dp_i=dp_{i-1}+dp_{i-k}\times [i\ge k]$$
初值为 \(dp_0=dp_1=1\)。
然后对 \(dp\) 数组处理出前缀和，即可回答询问。
339D
直接建线段树，对每个结点的深度记录一下然后分成 \(\text{xor}\) 和 \(\text{or}\) 合并。
478C
贪心。 配着选一定更优，得那么气球总数除以3，就是可以满足的。然后判断什么情况不满足，即为不能配成对，则为三者互相加的最小值。
答案就是 \(\min(\frac{a+b+c}{3},a+b,a+c,b+c)\)。
118D
dp。
设 \(dp_{i,j,k,0/1}\) 现在有i个步兵j个骑兵上一个连续段有多长,最后放的是什么。
则转移分情况进行。
初始为 \(dp_{0,1,1,1}=dp_{1,0,1,0}=1\)。
转移为：
答案即为 $$\sum_{i=1}^{k} (dp_{n,m,i,0}+dp_{n,m,i,1})$$
时间复杂度空间复杂度为 \(\text{O(nmk)}\)。
977F
最长连续上升子序列。输出方案。
467C
dp。
设 \(dp_{i,j}\) 表示前边 \(i\) 个数，选了 \(j\) 个区间了。
则转移为 \(dp_{i,j}=\max(dp_{i-1,j},dp_{i-m,j-1}+\sum_{i=l_i}^{r_i}a_i)\)。
用前缀和 做到 \(\text{O(nm)}\)。
349B
贪心。
我们先选出最平均的那一个填，从高位到低位使得剩下的数尽可能地大。
注意更新贡献。
1359C
对于当前倒进去多少瓶热水是有单调性的，考虑二分这个瓶数，则答案即为 \(2\times ans-1\)。
1037D
考虑对于一个点的孩子的集合必然相同 于是想到用自动排序的 set 取下一次搜什么 这样就没有编号问题了。
1381A1/1381A2
A1
傻逼题。考虑每次找到不同的就换到开头把它一个反转然后再反转回去。
A2
考虑直接把两个序列都变成全 1 或 0，然后将 \(a\) 的操作正向输出，将 \(b\) 的操作反向输出。
1538D
考虑找到可行的上下界。
下界即为一步到位 找到两个数的 \(\gcd\) 即可。
容易发现每次用一个质因子速度最慢，则上界即为两个数质因子个数相加。
448D
对于每一行是单调的。
二分，那即可得到一行能够对答案的贡献：若最终都没有大过，即为 \(m\)，否则就是当前二分值在每一行整除的数的大小之和。
1328D
容易发现 \(4\)，直接暴力分讨。然后染色即可，可以按照种类染，也可以按照奇偶性染色。
证明答案不超过 \(4\)？考虑一个颜色种类至多与两个不同的颜色种类相邻即可。