NOIP2025游记

· · 生活·游记

wow，我居然会写游记。

Day -???

前一周校运会，在机房打“Three Country Kill”。

然后刷板子，打 vp，刷板子，打 vp。

刷 CF 是吃 shi 来的，折磨。

Day 0

放学后回家冲凉就坐地铁去酒店。

深高高中园实在太偏，出来地铁站一个人也没有，到了居民区才多少有点人，有一种回到老家小县城的感觉，路上时不时会刷新小卡片（我可没捡起来）。

拿到房卡后回房间刷手机复习算法，期间 @Nasaepa 来串门，与其讨论神奇单对数的三维偏序问题，非常人类智慧。

想做这道题的戳这：P11197 [COTS 2021] 赛狗游戏 Tiket。

Day 1

哇酒店早餐比学校食堂不知道好吃多少倍！！！

打车到高中园，进入候考室，捕捉到野生的 @Haren0z。

我的考场是 9 号，创新高中 507。考场不让带吃的就很离谱，我把包装全撕了都不让带。（想问一下 GD 其他考点是不是这样）

高中园提供 vscode 超级奈斯，即使没有 cph 和 C/C++ 配置都比 Dev 好用不知道多少倍。这里真的要给大家推一下 vscode 内置命令行， Ctrl + J 唤出面板直接输 g++ xxx.cpp -O2 -Wall -Wextra -Wl,--stack=200000000 -static -std=c++14 && a < xxx1.in > .out && fc xxx1.ans .out，把这个命令粘在代码末尾注释掉，这样每次要运行程序把它粘到命令行里就行。这样的好处是方便测大样例，不像 Dev 每一次都要改 freopen。

不想看做题环节的直接折叠掉就好。

:::info[省流：前 10min 拿的分比后 4h20min 拿的分高]{open}

闲话少叙，开始写题。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：

  2. 仅有一个 w=1：分讨 w_1 为 2 或 1，枚举第一个 w_i=1 的 i 或 w_j=2 的 j，统计：若 a_i > a_j 且 a_i \le \frac{a_j}{2} 或 a_i > b_j 且 a_i > \frac{a_j}{2} ，则 \max\{i,j\} 以后的 w 随便选，贡献 2 ^ {n-\max\{i,j\}}；

  3. 至少两个 w=1，一个 w=2：分讨 w_1、w_2 为 1 / 2，枚举第一个和第二个 w=1 的下标 i、j，第一个 w=2 的下标 k，统计：若 a_i+a_j>a_k 且 a_i+a_j\le \frac{a_k}{2} 或 a_i+a_j<a_k 且 a_i+a_j> \frac{a_k}{2}，则 \max\{i,j,k\} 以后的 w 随便选，贡献 2 ^ {n-\max\{i,j,k\}}。

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

（话说怎么开始写题解了……）

总而言之就是废了，欢迎前来评论交流并踩爆本蒟蒻。

11.28：CSP-S 2025 废了，NOIP 2025 再战

11.29：NOIP 2025 废了，CSP-S 2026 再战

估分就不在文章里宣了，别到时候打我脸。