NOI plus 2025 游寄

· · 生活·游记

比赛前一晚没睡好，躺床上 1h 才睡着，早上起来没精神

到考场了，发现电脑死机，换座。然后换到了另一个坏的电脑，按 Enter 键会打出 6，换到了备用机上

开题！开 T1，这不一眼？15min 过所有大样例。看 T2，由于赛前把 assign 秒了，信心大增（伏笔）。看了 10min，把题读懂了（吗），又随便看了下 T1，突然发现 m 在减到负数时可能出错，于是加了个判断（其实不加也没事，保险一点）

继续看 T2，随便想了想，也挺简单的。开写，测试样例，输出 2？一看样例解释，不对！读错题了！浪费了 1h。再读一遍，终于读懂了，继续想。

想了一会儿，发现这道题不对劲，已经超出我的能力范围了。但才 10:15，继续想。这题的关键突破点应该是贪心什么时候会出错，只有解决这个问题才能计数。于是我们可以考虑一个子问题：

对于一个降价方案 \{w\}，设 w_i=1 对应的 a_i 集合为 \{a_1,a_2,\dots,a_k\}，其中 a_i 降序排列。w_i=2 的集合为 \{b_1,b_2,\dots,b_{n-k}\}，b_i 降序排列。在这种情况下，什么时候贪心策略会出错？

那这就涉及到一个问题：怎么求最高的原价？很明显是背包，但是背包并不利于解决此题，她和这个贪心策略搭不上关系。卡住了，看看 T3 和 T4，应该可以有个十几分暴力，待会打（吗），上个厕所清醒一下。

继续想。w_i \in \{1,2\}，这是一个重要的条件！怎么用呢？2 是 1 的两倍。定义两个指针 p,q，如果 a_p+a_{p+1}>b_q，就把 a_p 选上，p 往后跳。否则选 b_q，q 往后跳。可是还是不太直观。容易发现的是，如果 a_p+a_{p+1} \le b_q，那么 a_{p+1} \le \dfrac{1}{2} b_q

用贪心策略是选 a_p,b_q,a_{p+1}，而正确的策略是先选 a_p,b_q，再根据 a_{p+1},a_{p+2},b_{q+1} 决定是否选 a_{p+1}。如果整个操作过程中选了这个数，那么这一步跟贪心策略并无区别，如果不选，那就说明后面的 a_{p+2},a_{p+3},\dots 全都不会要。这就是两个算法的区别，中间选的过程不重要，重要的是末尾几个数。

已经 11:00，按照计划，现在应该停止思考正解，开始想暴力分。而子问题仍未解决，只是找到了一个比较模糊的方向，具体衡量“贪心什么时候会出错”的标准仍然没有想到。至于怎么计数，怕不是比赛结束可能都想不出来。所以还是看暴力怎么拿分吧。

dfs 20 分是容易的，特殊性质 A，m=2n-1,2n-2 是容易的。先想特殊性质 B，这个特殊性质的意图很明显。贪心策略和答案的区别在于是否选中了 a_k，于是可以枚举 a_k 和 k，根据这个去计算不合法方案数量，再用所有方案一减即可。不合法方案数量是容易计算的，问题出在下面几个方面：

这些问题显然都可以通过构造样例输出调试信息解决，傻子来了都能调试好。但当时我的心态已经非常不好了，怀疑式子推错，改了几次没通过大样例（用大样例调试？？？），也没有耐心去用小样例 debug（我是【】）

最后 1h，把深搜，特殊性质 A，m=2n-1 写了。debug 浪费过久时间，甚至 m=2n-2 没调完。

最后得分：100+28+0+0=128，开局 30min 拿 100 分，后面 4h all in T2 狂砍 28 分，T3 T4 碰都没碰，到最后还没整场都在打暴力的人分数高（笑

如果当时没有看错题浪费时间，如果我坚持把特殊性质 B 调下去，如果我能再细心一点……

可惜没有如果，这一场比赛已经过去，没有拿到理想的分数，就是实力不够。接下来的一年里，要继续好好训练，争取下一次拿到省一。