NOIP 游记
2025-11-29 19:39:25
发布于：广东
Day -3
水了道可撤销并查集题，心态++。
Day -2
看了看洛谷的 NOIP 模板测试，发现自己有十几个板子还没做过，吓哭了。
尝试做某神秘网站远古思维题目照片装裱，在找第一个的时候卡住了。
求数据结构：
一个数组内有两个元素 。
每次查询给定 ，查询第一个 且 的元素，并删除这个元素。
第一个的定义是以 为第一关键字， 为第二关键字从小到大的第一个。
算了明天再想。
Day -1
在学校想了半天，发现自己的智商有 -350234。理由：昨天那道题线段树套 set 二分就能做了。
有点感冒，但问题不大。
做出来了。
Day 0
给自己定了个规则：
- 一开始先看完 题，开好所有的文件。
- 从 T1 开始做。
- 每道题先思考 10s 正解，如果想不出来就开始拿部分分。
- 部分分从暴力分开始拿起，显然每道题暴力分加起来有 。
- 一定要想特殊性质。
- 写完代码一定要检查时间复杂度是否符合预期。否则像今年 S T1 。
- 如果有大模拟，一定要先理清思路。
考试最后 30min 不写代码，写迷惑行为。GD 省把这个 ban 了，只能被迫写代码了。- 最后 15min 检查文件等。
Day 1
开题。
T1 是啥糖果题，想了 10s 发现好像可以分成一个一个和两个两个，感觉挺简单。但先不急，打个爆搜先。
爆搜很简单，枚举每次选哪个糖果即可。，可以过前 个点。其实我场上以为这个是 的，不过问题不大。
1h 打完爆搜，。
T2 就上难度了。
题目就是介绍一道 背包题，但是重量只能取 。小 R 尝试使用一种常见的贪心解法解决。现给定每种物品的价值，请你求出有多少种情况小 R 的做法是最优解。
感觉有点难，应该绿上/蓝？
考虑做法如何才会假掉。
呃呃呃 10s 过了，先打暴力吧。
贪心方法就直接按题目模拟了，注意为了防止精度的一些问题，可以进行公式转化：
最优解直接背包。
这样单次判断就是 了，搭配枚举重量可以做到 。
1h30min，。
T3 是给出一棵树，要你给每个点赋一个权值，使每个点的子树的 的之和尽可能大。
有点难啊。蓝/紫吧。花了 5s 没想出来一点，剩下 5s 喝水（
打 暴力竟然只能拿两个点，太惨了。
1h50min，。
T4 是一个数列查询，但查询的东西很猎奇。
这个 有点奇怪，感觉应该是对着答案用什么神秘算法？不管了，反正我肯定不会磕这题正解的，打暴力。
我好菜啊，只能打 暴力。喜提 个点。
2h20min，。暴力分比预期低不少。
开始推 T1。
感觉挺简单的，橙吧。那就直接按照上面的思路想正解得了。
注意到两个两个选的操作一定会用在同一种糖果。这就不用证明了吧。
所以剩下的都是选一个的。显然，选一个的糖果 越小越好。
我们可以先按 排序，然后把所有的 放进堆（按 排序然后找 最小值也行），然后枚举对多少种糖果选一个，最后将剩下的值除以 即可。。
这种做法大样例全过，自己也对拍了约 组，都正确。
那可以说做法是对的吧。
2h40min，。
然后是 T2。
考虑怎样才能卡快速获得最优解。
观察样例：
注意：若 ，则小 R 会依次购买第 2 颗和第 1 颗糖果，原价总和为 4，但小 R 可以只购买第 3 颗糖果，原价总和为 5。
再思考一下，发现如下结论：
在小 R 的基础上，将最后几个重量为 的弹出，使得剩下的容量为 ，然后用这个 买原价最高的容量为 的物品，取最大值就是最优解。
按照这个思路就可以通过分组排序+双指针轻松设计出来 的判断方法了。对 预先排序可以去掉这个 ，时间复杂度为 ，可以过 个点。
3h10min，。
那正解应该是 的 DP 了，对吧……？
没时间想正解了，只能再找性质拼点了。
看一下特殊性质。
诶怎么还有 相等的点啊。这么送？
3h30min，。
然后注意到有 的点。显然可能的解法就是取两个价值最大的重量为 的物品或一个价值最大的重量为 的物品。
首先考虑只有一个重量为 的物品的情况。假设这个物品为 ，显然它必须满足 且 。
然后考虑多个重量为 的物品的情况。按照上面的结论，我们可以知道，只需要找到前两个重量为 的物品就行，后面的物品重量不重要。 枚举即可。
4h10min，。
然后看了看 T3 依然想不出来，所以转到 T4。
我发现我的暴力显然可以用 ST 表优化。但是只剩 20min 了，我牺牲了检查文件的时间调这题，但是到考试结束也没调出来。
最终成绩：。
Day 1+
什么？黄紫紫紫？
什么？黄紫黑紫？
什么？黄紫黑黑？
你是说我一个 CSP-S 刚一等的蒟蒻在黄紫黑黑的比赛中拿了 152？？？
有帮助，赞一个