NOIP2025 游记

· · 生活·游记

?~11.28

这段时间心情大起大落，从没做出来 ST1 的懊恼到知道自己在 NOIP 体验先上一分能体验 NOIP，十分刺激。但好在是有 NOIP 能打。于是认真准备了一周。

11.29

在 rdfz 考的。考场在 6 楼，而我没有发现电梯，直接爬到了 6 楼，累了个半死。进考场写缺省源，这是我的快读中的一部分：while(c>='0'&&c<'9')，关键是我测试的时候输了 -1235 状物，没有测出来。

8：27 发密码，8：29 看题。大概会 T1 了，先写。一开始思路假了一次，认为一直取 x+y 最小的是最优的。测大样例过不去意识到了问题，改了改就过大样例了。提交的时候是 8：58。

接下来的半个小时，我把其它三道题都想了一边，欸我不会 T2 啊！欸我不会 T2 多于 40 分的部分分啊！我是不是没救了啊！T4 是我最喜欢的数据结构，但是我好像只会白给的 40 啊！T3 我好像只会 O(2^n poly(n)) 啊！

于是先写 T4。期间发生了 #define int unsigned long long 然后在 ST表 中炸的很惨，大概是下标变成了一个很大的东西。调了调就调出来了，但是发现空间要 1个G，非常不好。于是把 st表中的数组换成了 vector<int>mx[20]，这下静态空间肯定没问题了，但是我也不会测动态空间啊。测大样例， AB性质大概都跑了 1.3s 左右，认为能过，就不卡常了。

接下来尝试写 T3 O(2^n poly(n))，写到一半发现假了，应该是 O(4^n) 的，觉得没前途啊。又想了想发现只能做到大概 O(3^n n^2)，和 O(4^n n^2) 好像没啥区别。于是决定先想想 T2 再留半个小时写这个。

现在大概是 11：00。想了想，发现我完全不会刻画 T2 这种结构。开始拼拼暴，先写了 20pts 的暴力，又写了 A 性质的 2^n。发现 m=2 给的分很多，开始思考。发现大样例中有很多 1048544 状物，考虑用 2^n 减去不和法的情况。那大抵就是 w_1=2 的情况。后面想了很多对的东西，但是代码输出总是差一点。弃了，然后看 16、17 两个点。发现一个是 2^n，一个是 2^n-eps。想了想就会做了。拼出来应该是 32pts。

最后还剩半小时，回到 T3。欸，怎么有 m=2，这不是菊花吗？玩了玩，发现会菊花了。写写写，过不了大样例。打开一看，再读会题，欸牛魔，怎么 d_1=0 啊。那不会了。想想想，想出了一个什么

(\sum_{fa_i=1}deg_i+1)+max_{fa_i=1} deg_i

但是离答案差 5 左右。一直想到了最后也没回，然后 8pts 的暴力也没打。检查了一下就到点了。估分是 100+32+0+40=172，大概是一个标准的二等奖吧。

upd:出分了。55+24+0+35=114，没救了。T1 写挂了一两个地方，不知道为什么挂这么多。T2 数据点分支没输入全。T4 最简单的点空间炸了。总共挂了 58 分。看来以后得加强练习防挂分能力了。