23/10/06 NOIP模拟赛总结
时间安排
7:40-8:00
看题
8:00-9:00
写T1，写了个极限复杂度 \(n^2\) 的代码，没想到优化，但感觉数据不会很严。
9:00-10:00
写T3，T4暴力，但两个暴力都挂了。
10:00-11:00
想T1 \(O(n\ log\ n)\) 的方法，就是没想到倒着枚举。
11:00-11:35
写了T2全为 + 的数据，发现T2暴力挂了，调暴力。
11:35-11:40
调不出来，写好文件输入输出，交题。
反思总结
暴力写挂，要多手搓几组小样例测试。
简要题解：
T1:
倒序双指针，记录后缀和，贪心计算答案。
T2:
区间DP+组合数
设 \(f_{l,r}\) 表示表示区间 \(l∼r\) 所有可能的答案的和。
设 \(g_{l,r}\) 表示 \(l∼r\) 中有几种可能的答案。
\[g_{l,r}=\sum_{i=l}^{r-1}\ g_{l,i}\times g_{i+1,r}\times C_{r-l-1}^{i-l}
\]
对于加法：
\[f_{l,r}=\sum_{i=l}^{r-1}\ (f_{l,i}\times g_{i+1,r}+g_{l,i}\times f_{i+1,r})\times C_{r-l-1}^{i-l}
\]
对于减法：
\[f_{l,r}=\sum_{i=l}^{r-1}\ (f_{l,i}\times g_{i+1,r}-g_{l,i}\times f_{i+1,r})\times C_{r-l-1}^{i-l}
\]
对于乘法：
\[f_{l,r}=\sum_{i=l}^{r-1}\ f_{l,i}\times f_{i+1,r}\times C_{r-l-1}^{i-l}
\]
T3:
打表找结论：要么每一列黑白交替，要么每一行黑白交替。
所以我们翻转 \((x+y)%2==0\) 的棋子，则合法的方案为：要么每一列都同色，要么每一行都同色。
T4:
暴力DP：
设 \(f_{u,0/1}\) 表示为以 \(u\) 为根的子树，\(u\) 不在/在某一个连通块中的最优解。
但我们对于每一个 \(k\) 都要做一遍DP，\(O(n^2)\) 的时间复杂度是无法通过该题的。
设 \(g_{i}\) 表示 \(k=i\) 时取到最优解的最小连通块数。
如果一个区间( \([l,r]\) )内有 \(g_{l}==g_{r}\)，此时我们只需要对 \(l\) DP一次，就可以求出 \([l,r]\) 的答案。
所以我们进行分治，设 \((l,r,ql,qr)\) 表示 在 \([l,r]\) 的区间中，已有 \(g_{l-1}=ql,g_{r+1}=qr\)，对 \(mid\) 进行DP求出 \(g_{mid}\)，若 \(g_{mid}==ql\) 则不需要继续处理左侧区间，右侧区间同理。