NOIP2025游寄

· · 生活·游记

赛前闲话

高二生第三次打NOIP，只求省一！

考场外有人说有不祥的预感，事实确实如此。

8:30

开题！

T1

看上去决策复杂，但第一题一般都是贪心？花3分钟口胡了一个做法：每次选当前状态最便宜的买，模拟一下不难得出当一件商品选了第二个后，之后会一直选它。

开码。。。

额？怎么样例过不了？原来做法假了。

接着又分析了下题目，发现选2次以上的商品最多只有一个，那我们就可以找出x_i+y_i最小值的商品，接着把所有商品的x_i值从小到大排序，枚举选i个只选一次的最小商品（注意这些商品应包括前面我们所选的x_i+y_i最小值的商品），找出答案最大值

9:05 通过所有大样例

T2

看了题目，想了20分钟正解，怎么这么简单？又仔细地审了遍题，才理解了真正题意，然后想出了一结论：策略不合法当且仅当出现以下情况：

贪心心过程中，因为剩余钱数为 1，跳过了一个性价比很高但买不起的 2 元糖果 u。随后，用这 1 元钱买了一个 1 元糖果 v（或者没买任何东西，即 v 不存在，a_v=0）。如果此时，在已经购买的 1 元糖果集合中，存在一个糖果 z，满足 a_u>a_z+a_v（即把 z 和 v 换成 u 会更优）

枚举u和v计算就行

花了大半小时想具体实现方法，发现有个O(N)组合数无法优化成O(1），导致时间复杂度试O(n^3)的。（赛后发现要用范德蒙德卷积，我还不会——）

不管了，O(n^3)10:00左右开码。

码完后发现大样例死活过不去，想了很多方法都找不到错误听着周围此起彼伏的键盘敲击声，我觉得我就如同废物

心态已炸，决定开后面两题。（此时已11:15）

T3

看着像DP？算了先看T4吧

T4

区间问题？感觉非常可做

暴力一眼，直接用ST表，不过只给15分？

那每次询问统计以i为右端点合法区间的最值，记在sum数组中，接着算每个点的答案考虑其有哪些右端点能覆盖到它。对这些右端点sum值去最值。可以用单调队列维护。

码码码。。但码到一半发现对于一个右端点来说，答案点不同，其合法区间的左端点的范围也不同。

呃。但对于一答案点i，右端点为i+1到i+l的合法区间全都可以覆盖i节点，满足以上结论。

那对右端点为i+l+1到i+r的合法区间呢？直接暴力可以拿下特殊性质分，，我开始思考更优的做法，但毫无进展。

此时已12；00，我还是只有100分，于是我决定把T2的20分暴力打了。

再次T2

按照我之前的结论开始二进制枚举后判断，有点难写，写完过了小样例，但是大一点的样例怎么都过不去，自己的结论是不是错的？感觉自己5年OI白学了，瞪着代码打了很久，此时心态已经炸完了。

12:30，决定只拿特殊性质的4分，剩点时间写T4代码吧。

再次T4

决定只拼暴力了，写出了来过不了样例，找了一个错误后还是过不了，到考试结束还未调出。

赛后

T2模数打错了！！！，只有100

总结

1.其实最重要的是心态吧， 可能太想拿省一了吧，没有预计到今年难度这么高，T2写不出来心态就炸了。如果果断把T4的40分写出来，再随便骗点分，就有省一了，心态导致什么分都想拿，最后什么也拿不到。

2.其次练的还不够多吧，想T2类似的计数题，今年都没练太多，怎么调这类代码我不是很熟练。还有全真模拟还是太少，考场心态与决策都不成熟。

可惜没有如果，只能卷文化课咯