NOIP 游记

AIerqwq · 2025-11-29 19:33:57 · 生活·游记

Day -3

水了道可撤销并查集题，心态++。

Day -2

看了看洛谷的 NOIP 模板测试，发现自己有十几个板子还没做过，吓哭了。

尝试做某神秘网站远古思维题目照片装裱，结果在数据结构这块卡住了。

Day -1

在学校想了半天，发现自己的智商高达 -350234。理由：昨天那道题 set + 线段树二分就能做了。

Day 0

给自己定了个规则：

• 一开始先看完 4 题，开好所有的文件。
• 从 T1 开始做。
• 每道题先思考 10s 正解，如果想不出来就开始拿部分分。
• 部分分从暴力分开始拿起，每道题暴力分加起来应该有 60\sim 80pts。
• 一定要想特殊性质。
• 写完代码一定要检查时间复杂度是否符合预期。否则像今年 S T1 80\rarr 55。
• 如果有大模拟，一定要先理清思路。
• 考试最后 30min 不写代码，写迷惑行为。 GD 规定不能写题目外的内容，只能被迫写代码了。
• 最后 15min 检查文件等。

Day 1

开题。

T1 是啥糖果题，想了 10s 发现好像可以分成一个一个和两个两个，感觉挺简单。但先不急，打个爆搜先。

爆搜很简单，枚举每次选哪个糖果即可。O(n^{(m+1)})，可以过前 3 个点。

1h 打完爆搜，15+0+0+0=15。

T2 就上难度了。

题目就是介绍一道 01 背包题，但是重量只能取 [1,2]。小 R 尝试使用一种常见的贪心解法解决。现给定每种物品的价值，请你求出有多少种情况小 R 的做法是最优解。

感觉有点难，应该绿上/蓝？

考虑做法如何才会假掉。

呃呃呃 10s 时间过了，先打暴力吧。

贪心方法就直接按题目模拟了，注意为了防止精度的一些问题，可以进行公式转化：

最优解直接背包。

这样单次判断就是 O(nm) 了，搭配枚举重量可以做到 O(nm2^n)。

1h30min，15+12+0+0=27。

T3 是给出一棵树，要你给每个点赋一个权值，使每个点的子树的 \text{mex} 的之和尽可能大。

有点难啊。蓝/紫吧。花了 5s 没想出来一点，剩下 5s 喝水（

打 O(n^{(n+2)}) 暴力竟然只能拿两个点，太惨了。

1h50min，15+12+8+0=35。

T4 是一个数列查询，但查询的东西很猎奇。

这个 q 有点奇怪，感觉应该是对着答案用什么神秘算法？不管了，反正我肯定不会磕这题正解的，打暴力。

我好菜啊，只能打 O(nq^4) 暴力。喜提 0 个点。

2h20min，15+12+8+0=35。暴力分比预期低不少。

开始推 T1。

感觉挺简单的，橙吧。那就直接按照上面的思路想正解得了。

注意到两个两个选的操作一定会用在同一种糖果。这就不用证明了吧。

所以剩下的都是选一个的。显然，选一个的糖果 x_i 越小越好。

我们可以先按 x_i+y_i 排序，然后把所有的 x_i 放进堆（按 x_i 排序然后找 x_i+y_i 最小值也行），然后枚举对多少种糖果选一个，最后将剩下的值除以 x_1+y_1 即可。O(n\log n)。

这种做法大样例全过，自己也对拍了约 2\times 10^6 组，都正确。

那可以说做法是对的吧。

2h40min，100+12+8+0=120。

然后是 T2。

考虑怎样才能卡快速获得最优解。

观察样例：

注意：若 w_1=w_2=1,w_3=2，则小 R 会依次购买第 2 颗和第 1 颗糖果，原价总和为 4，但小 R 可以只购买第 3 颗糖果，原价总和为 5。

再思考一下，发现如下结论：

在小 R 的基础上，将最后几个重量为 1 的弹出，使得剩下的容量为 2，然后用这个 2 买原价最高的容量为 2 的物品，取最大值就是最优解。

按照这个思路就可以通过分组排序+双指针轻松设计出来 O(n\log n) 的判断方法了。对 a_i 预先排序可以去掉这个 \log，时间复杂度为 O(n2^n)，可以过 5 个点。

3h10min，100+20+8+0=128。

那正解应该是 O(n^2) 的 DP 了，对吧……？

没时间想正解了，只能再找性质拼点了。

看一下特殊性质。

诶怎么还有 a_i 相等的点啊。这么送？

3h30min，100+24+8+0=132。

然后注意到有 m=2 的点。显然可能的解法就是取两个价值最大的重量为 1 的物品或一个价值最大的重量为 2 的物品。

首先考虑只有一个重量为 1 的物品的情况。假设这个物品为 i(i\gt 2)，显然它必须满足 a_i\lt a_1 且 2\times a_i\gt a_1。

然后考虑多个重量为 1 的物品的情况。按照上面的结论，我们可以知道，只需要找到前两个重量为 1 的物品就行，后面的物品重量不重要。O(n^2) 枚举即可。

4h10min，100+44+8+0=152。

然后看了看 T3 依然想不出来，所以转到 T4。

我发现我的暴力显然可以用 ST 表优化。但是只剩 20min 了，我牺牲了检查文件的时间调这题，但是到考试结束也没调出来。

最终成绩：100+44+8+0=152。

Day 1+

什么？黄紫紫紫？

什么？黄紫黑紫？

什么？黄紫黑黑？

你是说我一个 CSP-S 刚一等的蒟蒻在黄紫黑黑的比赛中拿了 152？？？