CSP2025游寄

· · 生活·游记

前一天晚上九点放了学就回家收拾了一下坐车去了附近的宾馆，晕车，到了就睡了，前一天才期中考完，此时已经约2周没怎么碰电脑了。

早上发现了许多故人，但是没有ljy,问了问居然是太过于细心以至于没拿准考证。

虽然已经退了，但还是被老师拉去拍了个合照，在前面拿着旗子，淋了一分钟的雨。。。没有照片，不知道有没有人有，有的话发一下谢谢。

监考老师居然有一个是贾老师。

AK,没什么好说的，就是第三题花了10分钟回忆摄像头贪心。左边那个初一的xxs，约3.5h时开始无声欢呼（大致就是捏拳，然后表情喜悦），后来听他与别人聊天说是360分。

中午去瑞星咖啡坐了四十分钟的样子，咸奶茶有点烫，感觉不如甜的，喝着有点像咖啡，越喝越香。

下午ljy居然没有忘记拿准考证，稀奇。

碰见了lwk,gjt,得知lwk上午迟到了21分钟，gjt疑似因为太有钱了所以把报名费白送给了ccf(China Coin federation)，上午没来。

我右边那个人迟到了32分钟居然还成功进来了，不知道是不是老师太善良。

T1开始还以为是什么抽象dp，苦思冥想连O(n^2)都没想出来，就觉得肯定不是我的问题，T1怎么可能会很难？就往贪心想，直接把多余的贪心匀到损失最小的组去，就过了。

T2一开始还以为乡村就是城市，还在思考为什么有这种抽象题目描述，看了看样例发现是我理解错了，想魔改kruskal+dp，发现不行，再一看k最多只有10,n只有1e4，乡村最多nk条边，那直接2^k枚举一下选不选不就好了，但是m有1e6,就算不考虑m,1e8带个log不也炸了，于是想了想，发现先克鲁斯卡尔一下，没选上的边再加了乡村之后选了肯定不会更优，所以提前优化掉m-n+1条边，但是排序还是麻烦，于是想到提前排好序，k+1个数组来归并，但是n+k的father数组只开了1e4+5，还好我写了个mksj造了个满数据发现RE了，改了过来，此时过去了约1.33h，在编译选项开了O2,然后发现跑了1.44s!然后开始卡常，简易快读，位运算等都砸了上去,然后1.04s，我当时忽略了以下两件事：1，ccf原来的机子快于一中；2，换了个新机子更快（虽然我没发现换了新机子）。接着谜之卡常，浪费了半个小时，最终简易快读换成了关同步流，1.04s->0.96s，现在看来纯纯浪费时间。

T3看到后感觉很不妙，因为是字符串，而跟字符串相关的，我只会哈希，记得一半的trie模板，但是T4似乎是更加困难的计数dp，我都不会，于是先把T4拼了个12分，想写状压，但是dp我都不熟，调不出来，于是重新思考T3，总感觉有些性质，但就是发不现，最后发现了，可以把不同的那一坨提出来，然后就剩下个判前后缀，似乎可以用trie，但是得在两棵trie上跑，似乎还得用某种神奇方法解决字符串同时在两棵trie树上的问题，解决了还要解决给每个询问加贡献的问题，大抵是严重超出了我的能力范围，于是又想了想，好像可以AC自动机，匹配的时候算贡献，但是我AC自动机的板子一点不会，也没有细想，于是决定哈希加暴力，18:10的时候我想用个哈希表，但是不会pair的哈希，翻了5分钟的头文件库，啥也没找到，就只能用map，然后似乎可以枚举长度去匹配？但是没时间改了，18:20的时候终于把哈希调好了，18:23的时候还没过样例，18:27的时候过了大样例，似乎可以写一些B性质多拿20分？时间不允许，只能检查了一下。

ljy说第四题应该是正解但不知道哪里错了没跳出来，还是太强了。他们听说我不是在代码里开的O2似乎还有点遗憾。。。

在洛谷和熨斗测出来100+100+80+12=292。

查了分，100+100+50+12=262，第三题如果枚举长度就可以直接过。。。不应该在T2卡常的，不然我至少能拼个B性质，或者改成枚举长度，这个算是经验问题吧。

看来字符串和计数dp都是我的短板。

（似乎我附近的人比我高的不多？目前只发现了4个，窃喜）。