20231006 NOIP#16（33daiOJ）总结

时间安排

7:40~8:00

看题，\(A\) 一眼切了，\(B\) 会两档，\(C,D\) 没想法。

8:00~8:20

写 \(A\) 的正解。

8：20~8:40

写 \(B\) 的 \(30pts\) 。

8:40~8:50

原来算错了 \(C\) 的爆搜复杂度，现在写了 \(C\) 的第一档。

8:50~9:20

会了 \(D\) 链的特殊性质写了 \(10pts\) 。

9:20~11:40

罚坐中……

总结反思

• 做不出来题时可以尝试打表并推式子。

题解

A.脑洞题

这题很简单且做法极其多样，后缀和应该是最简单好写的吧。

B.区间DP

设 \(f[l][r]\) 表示区间 \(l\sim r\) 所有可能的答案的和。 转移时枚举断点 \(k\)：
对于加法 \(f[l][r]=\sum_{k=l}^{r-1}(f[l][k]\times (r-k-1)! + f[k+1][r]\times (k-l)! )\times \binom{r-l-1}{k-l}\)
对于减法 \(f[l][r]=\sum_{k=l}^{r-1}(f[l][k]\times (r-k-1)! - f[k+1][r]\times (k-l)! )\times \binom{r-l-1}{k-l}\)
对于乘法 \(f[l][r]=\sum_{k=l}^{r-1}f[l][k]\times f[k+1][r]\times \binom{r-l-1}{k-l}\)

C.打表题

打表结论：要么每一列黑白交替，要么每一行黑白交替。
把整个棋盘黑白染色，然后翻转所有 \((i+j)\) 是偶数的坐标的棋子颜色。对于合法的方案来说，就变成了：要么每一列都同色，要么每一行都同色。
那么答案就是用每一列都同色的方案，加上每一行都同色的方案，减去所有行所有列都同色的方案。