NOIP2025游记

· · 生活·游记

纪念我的最后一场OI

主要记录考场思维过程，再现这次我认为RP==MAX的发挥

-2h：被叫醒，困
-1h40min：吃早饭，尝逝酒店的咖啡
-1h：到达考场：南京航天航空大学
-50min:楼下合影留念
-40min: 进考场，试机，一共打了10个模板，但赛时就用到1个……

开赛！

0min: 阅读T1，直觉是dp，看到m<=1e18逐渐放弃……联想到CSP2024，NOIP2024，CSP2025 三场T1全部是贪心，就往这方面想，很快想到了
10min: 得到（部分错误的）T1做法
20min: 写完测大样例，测到第4个结果错了……还好n只有100，发现了做法的问题，最终思路：选择a_i+b_i最小的物品x，所有物品按a从小到大排序，枚举买前i个的a，剩下的全买x的a_x+b_x，O(nlogn)解决
40min: 写完，通过T1
40min-50min: 阅读T2，理解T2，题目不好理解啊
50min-1h20min: 思考T2，得到以下部分分做法（从简到难排序）：

  3. m<=10 (20pts)$：暴力枚举每个定价1还是2，check时按性价比排序模拟一遍，**01背包**算最优价值，复杂度$O(2^n*n^2)
  5. * **只有一个1**，设为$a_x$，剩下全是2最大的设为$a_y$，由于$m=2$，能且仅能买$a_x$或$a_y$。**不合法的情况是$a_y>a_x$且$a_y/2<a_x$**，显然$x\ne1$，所以$y=1$,枚举$x$从$2$到$n$判断，不合法就答案$-1
    • 至少2个1，设前两个1位置为x和y，（x<y,a_1 — a_{x-1}, a_{x+1} — a_{y-1}均为2），设2中最大原价为a_z，由于m=2，能且仅能买a_x+a_y 或 a_z，经过思考发现：当且仅当a_x>a_z/2且a_y\le a_z/2且a_x+a_y<a_z不合法。即：按性价比排序成x>z>y，这时按规则买a_x+a_y，但买a_z更优。显然x\ne1，所以z=1,枚举x, y从2到n依次判断，不合法就答案减2^{n-y}（显然{y+1}往后放1还是2无影响）。 复杂度O(n^2)

（特殊性质B大致也推出来了，但要算一堆组合数，情况也比较繁琐，就没深入）
1h20min-2h：实现上述部分分，还是很幸运基本上没调试。
2h-2h15min：阅读T3，直觉上可以直接dp出来，直接开写，写完dfs后觉得转移太困难了，于是去看T4。
2h15min-2h40min：阅读T4，易得O(q*n^3)暴力做法，一看数据范围惊呆了：最小的n=1000，一分没有！
这么呆滞了10min，疯狂手玩，最终发现：
(*)序列长度len确定时，从左到右预处理所有长度为len的序列权值，记为b_1,b_2,…b_{n-len+1}，发现能对a_i产生贡献的所有b_j为一个长度len的区间，且i右移1，这个区间也右移1，这就是滑动窗口啊!单调队列复杂度是优秀的O(n)！
于是对每一个询问，枚举len从L_i到R_i，每次按 操作做一遍，得到所有包含 i 的极好区间的权值，最后取max即可。
复杂度$O( q\sum(R_i-L_i))$，获得25pts（前3个点和性质A）

2h40min-3h:实现，发现性质B的大样例跑了5s多，灵机一动：既然R这么小（<=32），可以离线操作：
枚举len从1到32，每次按 操作做一遍，记录f[i][j]为包含i的长度为j的最大权值，就可以直接预处理出所有l和r情况下的答案，用一个ans[32][32]数组记录就行，询问时O(1)输出。
复杂度$O(32^2 n)$，获得15pts（性质B）

3h-3h20min：实现。其实到此已经拿到本场全部分数，下面看我浪费时间
3h20min-3h50min：用dp写T3，写完愉快通过样例1，但样例2五组就对一组
3h50min-4h05min:使劲改dp加特判，结果越改越错，和答案越差越大。最终放弃
4h05min-4h15min：暴力枚举每个点放0—n-1，获得O(n^n)算法，本来想减枝但怕答案变错，期望8pts
4h15min-4h30min:检查，没发现问题
期望：100+52+8+40=200
4h30min：哨音响，一切都结束了…………

+5min:我的代码没收上去，机器还显示要关机，慌得要命
+10min:发现考场还有2人跟我一样，最终考务处理后收上去了，虚惊一场
+20min:出考场，与hzy交谈，得知其切了T1+T2还是太强了%%% 但是似乎很多人炸了？
+40min:回到宾馆，评级：黄紫紫紫，原以为线和去年差不多，但接下来：
+80min:到车站，来一碗鸭血粉丝汤。一看变成：黄黑黑黑？这是NOIP？
一下午都很激动，看网络上各种有关NOIP的吐槽讨论
+4day：出分： 100+52+0+40=192，只比期望低8分，已经很满意了不纠结了
+14day：出线：JS一等128，个人感觉比较轻松：T1的正解+T2上述前3档部分分，刚好128.

时光荏苒，一眨眼我已经成为6届选手。从2020到2025，每一次OI都见证了我的成长。
回首，在OI的道路上，我付出了许多，好在结果是好的 退役之际，感谢两位教练多年的付出：我的妹妹syf，jxdlyg ，还有FastHorse的所有成员，很高兴和你们共同成长，愿你们都能实现梦想！
以后的路还很长，新的征途刚刚开始……