NOIP2025游记

闲话少叙，开始写题。T1 一眼秒了，就 $x$ 先排序，$x+y$ 只选最小，然后枚举选几个 $x$ 即可。光速开写，8 : 38 写完程序，8 : 40 过所有大样例，心态暴涨；看到 T2……？？？什么玩意，没看懂题，敲了个暴力，样例没过。苦战 30 min 一分没有，跳 T3，哇这不是树形 dp 板子吗！不对不对要状压，啊不对不对 $N$ 这么大怎么状压。爆炸，跳T4。坏了 T4 也不会，打了个小常数 $O(N^3)$ 暴力跑路，$N \le 3000$ 的大样例能跑进 2.5s，效率还行。

又回到 T2，又虚空想了 20min，想着应该做不出来，决定打 T3 树形 + 状压 dp，20min 写完过样例 1、2，样例 3 卡完了，原因是转移是 $O(2^N)$，这不得炸飞。此时我的脑袋开始思考 $f(u,i \cup j)\gets \max \{{f'(u,i) + f(v,j)}\}$ 的转移如何优化，苦思10min+ 得出的结论是 FWT……坏了我不会打也不想打，想着应该骗分骗完了，然后就放那儿了。唉当时如果想到直接枚举补集子集的话说不定卡个常能草过 $N \le 18$。（听了讲评发现 $O(N^3)$ 好简单早知道多花点时间想了 QAQ）

最难蚌的 T2 现在还是 0pts，开始硬磕。终于看懂了题，但是暴力照样难写，第一遍我按题目描述写的贪心 + 背包模拟，写了 40min 过小样例，键盘不顺手，跑的超慢；刚写完又发现根本不用 dp 因为物品价格是 1 或 2，显然分类排序然后枚举每一类选几个就好。写完已经 100 行了，又一眼出特殊性质 A 和 $m=2n-1$，快速幂一下。

现在发现已经没啥可做的，我在 WPS 上滚动来滚动去想找一找有没有可以骗的分，看到了 T4 的特殊性质 A （ $L=R$）以为会了结果写出来还是 $O(N^3)$ 预处理。继续滚来滚去，逐渐开始发呆。

不知发呆了多久，终于鼓起勇气再次硬磕 T2。这次并不是没收获，苦思 40min，手模 3 组样例，$m=2$ 终于想出。大概是大力分讨出不合法情况然后减掉，可以分讨是因为大到小排序后要么选两个 $w=1$ 的 $a_i$，要么选一个 $w=2$ 的 $a_i$：

写了好久才过样例，此时只剩 20min，抓紧时间把所有题大样例又测了一遍，然后就结束了。