时间安排
7:35 - 7:45
看题。A 题一眼秒，B C 没思路，D 树形 DP。
7：45 - 7：50
随便过了 A 题。
7:50 - 8:50
写 B 题暴力的时候被卡了，时间复杂度怎么算都会 T 第一档分，也没什么好的处理方法，最后感觉应该跑不满就直接写了纯暴力。
8:50 - 9:30
思考 C，写了爆搜，\(n,m \leq 20\) 想了一个状压做法。
9:30 - 11:20
没想到那个状压那么难写，写到最后发现假了！！
11:20 - 11:37
非常慌，看 D。
11:37 - 11:40
会了链，但是时间显然来不及了。
总结反思
- 应当在看完题之后把能拿的分列出来，从付出时间及得到的收益两方面考虑最优的拿分策略。
- 算法题感觉还可以做做，人类智慧题做不了一点。
题解
A.序列划分
pj T2 难度。
B.表达式求值
法 1：将和转为期望算，最后再乘以 \((n-1)!\)。
法 2：区间 DP。设 \(f_{i,j}\) 表示区间 \([l,r]\) 所有可能的答案的和。枚举 \(k \in [l,r)\)，可以将 \(f_{i,k}\) 的可能答案和拆成 \(a_1,a_2,a_3 ... a_{s1}\)，\(f_{k+1,r}\) 的可能答案和拆成 \(b_1,b_2,b_3 ... b_{s2}\)。
- 乘法操作满足分配率，所以直接乘起来
\[f_{i,j}=\sum_{k=l}^{r-1} f_{l,k} \times f_{k+1,r} \times C_{r-l-1}^{k-l}
\]
- 考虑加法操作， 每个 \(k\) 对答案的贡献为 \((a_1+b_1)+...+(a_1+b_{s2})+(a_2+b_1)+...+(a_2+b_{s2})+ ... +(a_{1}+b_1)+...+(a_{s1}+b_{s2})\)。发现每个 \(a\) 都出现了 \(s2\) 次，每个 \(b\) 都出现了 \(s1\) 次，而 \(s1\) 和 \(s2\) 可以计算出来。
\[f_{i,j}=\sum_{k=l}^{r-1} f_{l,k} \times (r-k-1)! + f_{k+1,r} \times (k-l)! \times C_{r-l-1}^{k-l}
\]
- 减法同理
\[f_{i,j}=\sum_{k=l}^{r-1} f_{l,k} \times (r-k-1)! - f_{k+1,r} \times (k-l)! \times C_{r-l-1}^{k-l}
\]
C.放置棋子
人类智慧题。打表发现合法方案要么每一列黑白交替，要么每一行黑白交替，然后为了方便翻转 \((i+j)\) 为偶数的棋子，合法答案就变成了要么每一列同色，要么每一行同色。
D.看电视
发现答案的上界为 \(n+k\)，则连通块数目的上界为 \(\frac{n+k}{k+1}\)。
考虑根号分治，设 \(B\)，对于前半段使用 \(O(nB)\) 的树形 DP ，对于后半段使用 \(O(\frac{n^2}{B})\) 的树形背包。