20231013 NOIP#19（33daiOJ）总结
时间安排
7:25~8:00
看题，\(A\) 一点不会，\(B\) 会 \(15\) 分，\(C,D\) 各会一档。
7:50~8:00
写 \(D\) 的第一档。
8:00~8:10
写 \(B\) 的前两档。
8:10~8:40
写 \(C\) 的第一档。
8:40~9:00
想到写了 \(B\) 的 \(n^2\)。
9:00~10:25
会了 \(A\) 题，但是因为 \(upper_bound\) 学艺不精没过大样例，调了半天改了线段树二分。
10:25~11:00
\(C\) 题尝试拼包。
11:00~11:50
都写完了，试图切 \(B\) 失败。
总结反思
- 考试捡有把握的写
题解
A.数据结构
找第一小于 \(x\) 的位置和区间询问最大值，数据结构随便搞。
B.贪心+数据结构
合并一定是 \(n\) 此操作，只考虑交换要多少次。
如果一个线段（被）包含于另一个线段，那么显然这两个线段不会产生交换次数，所以即求在一个区间内有多少线段只出现了一个端点。
那么可以将其按左端点排序，询问区间内有多少线段的右端点，数据结构维护即可。
C.构造
当 \(h=2\) 时问题很好解决，手推一点就会了。
如果 \(h>2\) 且 \(w=2\) 那么可以翻转坐标，变成 \(h=2\) 的情况解决。
如果 \(h>2\) 且 \(w>2\) 判断目标点是否在 \(S := \lbrace (1, 1), (2, 1) (3, 1), \ldots, (h, 1), (h, 2) \rbrace\) 集合内。如果在则翻转坐标变成不在的情况，如果不在则将 \(S\) 集合覆盖并垂直翻转。
D.计数DP
设 \(f[i][j][k]\) 表示走到第 \(i\) 步，已经扩展了 \(j\) 种点，包含 \(1\) 号点的最大的强连通子图的点数为 \(k\) 时的方案数。
起点都在上次移动的终点处，当移动时，终点就有三种情况：
\(1.\) 终点属于未拓展的点 \(f[i+1][j+1][k]+=f[i][j][k]\times (n-j)\)
\(2.\) 终点在不包含 \(1\) 的强连通里 \(f[i+1][j][k]+=f[i][j][k]\times (j-k)\)
\(3.\) 终点在包含 \(1\) 的强连通里 \(f[i+1][j][j]+=f[i][j][k]\times k\)
初始 \(f[0][1][1]=1\) ，答案为 \(f[m][n][n]\)。