CS3022-SPJ Eden 游记

· · 个人记录

CSP2023-JS -> CS3022-SPJ，这很合理。

作为一个高三选手，应该是最后一次参加 CSP 和 NOIP 了，打完 NOIP，应该就是 OI 生涯的结束了。所幸，另一方面，作为西湖大学的同学，我的 ICPC 也正式开始了（虽然网络赛都能被吊打）。

这次比赛同时我约了云斗一起造民间数据，责任又多了一分。

CSP-J

早上我打开电脑，忽然洛谷群炸开了锅。

我一看，原来 SSH 省网络出了点问题。

赛后我开始逐个分析今年的题目，写了份 std。

今年的 T1 仍然是数学的分类讨论...哎怎么 n\le 10^9？细想一下，题目说每一天取一次苹果，而且只问最后一个苹果哪天取完，而最后一个苹果被取走前总是最后一个，所以只要维护当前有几个就可以了，中间的编号不规律也不用管。

然后就是时间复杂度的问题。每天取走了约 1/3 的苹果，所以大概是个 \log。但是对小朋友而言好像有点难啊——哦不对，对数函数还真是 J 组要求的。

然后是第二题。我怎么都感觉自己出过这个题，但是细想了一下不是——虽然都是汽油和固定的加油站位置。

看了下数据范围感觉一时间没啥好想法，先等着。

然后第三题没绷住。本来云斗有一个很好的宣传自己模拟赛的机会——云斗 J 组模拟卷 T2，本来是给你 n 个二次函数然后 q 次询问每次给一个 x 求所有 y_i>0 的 i 异或和，但是花觉得太毒瘤了所以改成了一次函数。

要是我坚持二次函数，可能我们就可以宣称自己押中了 J 组 T3 和 S 组 T4要解二次方程。

因为没搞到大样例，所以我自己随便测了两组就发给组里其他人了。

然后我就打开了第四题，刚打开便有一股陈年老题特有的年代感。那还是我初二的时候，恰好当年 AK 了 CSP-J，印象深刻。

我沿用了那道题的思路，先建立分层图，建立了边后尝试最短路。现在的我和当年的想法不同了，我会把二维重编号为一维写一个新函数。

首先最短路模型肯定是对的，如果你到上一站的时间更早，则到当前站的时间不可能更晚，只要想办法 BFS 即可。

然后卡住了。因为开放时间的存在，我们的 BFS 不一定对——先到达的点，离开的时间不一定更早。

那么考虑放弃队列，而采用离开时间顺序更新？哎这样好像依赖值域了，而且绝对不好写。

考虑换一个对图要求更低的算法，比如 Dijkstra？这个算法只要求距离最短的图不会被更新即可。好像除了 2\times 10^6 条边搞 m\log m 不太正常以外其他东西都相当正常。

但是我现在目的是生成数据啊，用了点 S 组算法，或者是时间有点危险怎么了。所以就没接着想，码完就交给别人了。

回头想了想 T2。要不试试看递推，假如目前我刚好能活到某个站点，我要怎么修改我的计划，才能让自己能顺利开到下一个站点。

好像只要从前面的加油站挑一个最便宜的就可以了。看上去确实不难，但是我觉得还是有点有趣成分在的。但是总感觉见过啊，到底怎么回事呢。

T3 的代码被造数据的同学揪出来，说有一份代码他输出了 1-sqrt(7)，我输出了 1+-1sqrt(7)，然后他说要回去仔细检查是否对于 -1 也要省略加号或者 1。

我：woc 好像根本没讨论 a 的正负，较大根中 q_2 肯定是大于 0 的。

内心 OS：对不起高中数学老师了= . =。

CSP-S

到达学校。今年终于不在仓前了。准考证号 ZJ-S00014，排的很前面。

电脑终于用上了 Windows 10。那位态度恶劣的监考老师也没有出现。

进考场时，老师对一同学说：“考试时不要用修正带啊”。

桌子特别小，我拿出尺子量了一下，桌宽 64 厘米，放腿的地方因为有个机箱所以只有 39 厘米宽。

今年密码没啥整活的。

T1（评分：橙）

啊？

真的就枚举所有密码？

虽然题目不难，但是我仍然 3 点才做完。判定密码和状态之间的改变量是否连续，好像还是有点麻烦的。

我觉得其实我应该再暴力一点，不仅枚举密码，还直接枚举转法，10^5\times 81\times 5 也是稳稳当当的。

这么看来我觉得云斗 S 组 T1 押题相当准确啊（笑），就是那玩意码量还是大了点。

T3（评分：绿）

本来看到 T2 觉得就是括号树翻版，但是细想了一下并没有告诉你每个字符是左括号还是右括号。当时思考了一下，好像也没法直接转化成括号树。

然后看了下 T3，大模拟，看看 T4 吧。

T4 上来直接解一元二次不等式是没绷住，某种意义上我们云斗《也本可以押中题的》。尽管如此，细想了一下，每棵树成长时间不固定好像也没什么特别的 idea。（赛后 os：不是，早上刚吃了二分 BFS 的亏现在你又忘了你有二分这个工具是吧）

然后犹豫了一下写 T2 还是 T3。注意到这已经是我最后一次 CSP 了，分数没有那么重要，不如弥补一下 2020 年儒略日的遗憾，告诉自己三年过后已经不会被 S 组模拟绊倒了。

硬碰硬了 100 分钟，测了下大样例，应该强度还行，就没管了。

（注：2019 年我括号树写了 150 分钟。）

T2（评分：蓝）

回来继续想这个东西，考虑到去年有不可以总司令，我们相信根据”每个字符都出现偶数次“可以解决大部分问题（确信）

虽然这显然不靠谱，但是我稍微改进了一下我的猜想。假设 f(x) 记录的是最大的让 [l,x] 所有字符出现偶数次的 l，那么我猜测 [l,r] 可消当且仅当任取 l\le x\le r，要么 s_x 第一次出现，要么 s_x\ge l。

感性理解了一下好像很对，然后开始考虑实现。

和当年括号树的想法一样，设 pre(x) 为 x 结尾的最短可消串。这时候我发现当 s_x=s_{x-1} 时 pre(x)=x-1，否则（子集的 \min 大于本身的 \min） pre(x)<pre(x-1)。

接着思考，如果发现 s_{pre(x-1)-1}\ne s_x，那么 pre(x) 还得小于 pre(pre(x-1))... 总之就是往前跳 pre 直到找到相同字符为止。

感性理解了一下复杂度好像也很对。我还写了个 O(n^3) 的区间 DP 对拍了一下，似乎没啥问题。

T4

此时只剩下 20 分钟。写了个性质 A，还写假了。

大概我其实还是速度不够快吧。我觉得其实再给点时间我是能想到二分的。