NOIP2024 模拟赛 #12
学长出的模拟赛，风格挺好。
赛时
8:00 T1 会了一个 \(O(n^2\log n)\) 的做法，先写一下，看看能不能过样例。
8:20 过了小样例，大样例跑得慢但是是对的。
8:40 发现一个好的做法，可以枚举 \(c_i\) 最小的那一天选了哪个，再枚举 \(k\) 天，这样纯枚举复杂度是 \(O(k)\) 的。但是有些细节不太好处理。
现在转化成了一个经典问题，很多次遇到了，但我还是不会。
欸，好像会了。时间复杂度 \(O(k\log n)\)。贪心不好写，枚举解决！
9:05 ok，大样例全过了。最慢的点 \(0.4\) s。
T2 怎么还有 SPJ，这么神秘。下发了 checker 但是不知道怎么用。
9:35 T3 会了 \(O(m^n)\) 的爆搜，有了 \(15\) pts。
完了，不会 \(2^n\) 做法。
T4 一次旅行不可能经过很多的点，这样很浪费。也不可能经过一个点，
T4 直接模拟旅行不太可做，可以将题意转化为分成若干个连通块，而这是树，转化为哪些条边需要断掉。这样可以 \(2^{n-1}\) 枚举，计算每个连通块的贡献。
也许可以树形 DP，设 \(dp_i\) 为断掉与父亲的边时 \(i\) 子树内的答案，但是我不会转移，唐完了。
10：25 T4 的 \(10\) pts 写完了。
一次旅行经过的点数不可能大于 \(3\)，也就是每个连通块的大小小于等于 \(3\)，也不可能是 \(1\)。
欸，结论假了，寄。
\(10\ 1\ 1\ 1\ 11\) 这样，\(5\) 个数全选上是最优的。
10:55 把链 \(O(n^2)\) 的性质写了。
11:30 T2 通过找大样例规律拿了输出方案数的 \(20\) pts。
又写了 \(n=1\) 的分。
想冲一下 \(n,m\le 4\)，打算手玩。
玩得我头晕了，还有两种情况没写，不写了。
寄。
估分：\(100+28+15+20=163\)。
得分：\(100+28+15+20=163\)，rank 2。
赛后
T1 怎么除了我 A 掉的做法都是一样的啊，我就这么独特（。
T2 可以手玩一下发现一下消除 \(3\) 行或 \(3\) 列，感觉如果不考虑证明该做法最优还是简单的，但是细节肯定不少。
T3 容斥 + DP，赛时没写出 \(O(n^4)\) 的做法，亏大了。
T4 树形 DP，朴素 \(O(n^3)\)。然后 \(O(n\log n\log V)\) 的做法是一个 dsu on tree 加权值线段树，挺对的。
\(O(n\log V)\) 的做法是线段树合并优化 DP，很可订正。
感觉把状态列出来，再加上朴素转移，很困难。之后还是比较简单的。
总结
要多玩样例，找找规律，发掘性质，多拿性质分，从性质中推出正解。
对于数学还是要加强。