加训串串！
wing_heart
·
·
生活·游记
炸飞！写不完啊，要加训串串！
数论和串串肯定不会考的！考了我就炸飞。
邱队告诉我监考是草台班子，他们要检查同一个学校不能四连通，然后发现不管是横排竖排 s 形都无法实现。
怎么这么幽默。
进入考场。
怎么提前入场还可以有自习室休息。这么好。
因为来太早了错过合照/ll
诶，为什么我的手机 QQ 发出去的单个超级表情是小的啊？
之前一直都是大的啊？为什么啊？好神秘啊。
大手子怎么这么牛/崇拜
诶，为什么我的手气这么差的？我的 RP 确有问题！
见到了 wqb！
为什么我们考场一半六中一半广东省实验学校？怎么这么会排座位？
这个键盘有点脏脏的/咦
这个凳子不舒服/咦
怎么今年可以提前解压压缩包！
开虚拟机！虚拟机配置都正常，好评！多分了一些内存，还把共享文件夹直接改成了 GD-xxxxx 文件夹，这样就不用担心结束时忘记 copy 文件夹的问题了！
开 vscode 打缺省源。好像挺顺畅的，好评！
插件就只有最初始的插件。不像上次 NOIP 有彩虹括号呢。
看 t1，怎么，有点困难。S 组 t1 不是水题来的吗？
我还是认为 t1 应该是签到，所以先敲了 t1。大概用时 0.5h。
是一个比较板的贪心。每个人先选择最大值。然后可能存在一个 club 的人数超了，假设是 club A，那么按照 b-a,c-a 排序，贪心取。然后可能 B、C 会出现人数超限的情况，再排序贪心取即可。复杂度一只 \log。
会不会假掉啊，最后有空再对拍吧。
然后去看 t2。怎么，有点困难。看来这场真的没有签到了。
肯定先对原图求出最小生成树。
然后用乡镇替代掉树上一些边？做树上问题？
但是很难做。
那就枚举选择的乡镇集合。加上这些乡镇的边，求最小生成树。
$M$ 太大了。但是我们发现原图的最小生成树没有选上的边，加入乡镇后更不会选上了。所以原图的有效边只有 $n-1$ 条。
于是就做完了，排序可以归并。或者不真的并起来，直接在取用边的时候取最小的即可。
时间复杂度大概是 $O(nk2^k)$。
大样例怎么这么水，没有极限数据？最慢大样例跑了 0.15s。这个做法感觉多少有点不像 t2 了，标算会更快吗？
但是此时已经过了 2h。其实如果测了极限数据发现超时，我也没法卡吧。不如最后有空再测极限数据吧。
t3、t4 的题目已经看了，t3 是串串题/yun，t4 是计数题。
感觉 t3、t4 都是可做题，但是感觉会比较困难，估计我只能做一题了。那肯定是认为 t3 会更容易做吧。
然后花了将近 1h 写了个时间复杂度假的做法。我以为是 $O(L\log L)$ 的呢，实际上是 $O(L^2)$。
我不知道为什么我会认为字典树查一次是 $\log$ 的啊？有任何道理吗？这应是本场比赛最大的错误。
我直到测大样例发现很慢，才看出问题。很神秘啊。
然后我大概想到了正解，这里写清晰版的吧。
谨慎起见，我写了双哈希。
把 $s_1,s_2$ 拆成 $A+B+C,A+B'+C$。令 $B,B'$ 的长度最短。
$t$ 也这么拆。
把 B 那部分替换成 `#`。
然后就可以对一个串串 $t$，查找有多少和它的 B 相同的 $s$ 是它的子串。
直接哈希加 AC 自动机就可以秒掉了。
但是 AC 自动机怎么敲来着，只有 0.5h 多了，我没有自信写完 AC 自动机。先打完 t4 暴力吧。
加训串串！怎么可以半个小时都写不完 AC 自动机的！
t4 真的没有时间思考了。随便打了 $n \le 18$ 的状压 DP。和 $n=m$ 的送分，$24pts$。
然后还有大概 $20mins$。
写 AC 自动机还是推 t4 更多性质？为什么不能多给我半个小时啊/ll/ll/ll
写 AC 自动机吧。
没有写完。
100+100+25+24 遗憾离场。
------------
无缘 WC 了。之后也没有机会了。
如此成绩，如何 NOI？
或许做完 t2 我确实应该上个厕所，至少也要喝口水休息一下吧。当时我嫌上厕所麻烦还浪费时间。只剩下 2h，我很可能确实有些着急了。
或许就能避免降智的情况了。
毕竟，如果是温水煮青蛙一样的红温，似乎很难意识到我红温了。
你当然可以说这场 CSP 是炸飞，但是场场炸飞不就是正常发挥了吗？你的模拟赛也不见得高到哪里去。
我有些害怕出榜，我害怕看到自己的排名。
如果 CSP 可以看成模拟赛，NOIP 怎么看成正赛？
我天天嚷嚷着不会数学、不会串串，又嚷嚷着题目改不完，没有时间补习数学和串串。但是怎么不见你减少划水的时间，抽出时间去补习数学和串串呢？
蓝紫是我做的最多的难度级别的题目了。如果连蓝紫都做成这样，如何 NOI？去年在市赛上赛时切掉过的 AC 自动机而已，更多 NOI 的算法都还没有学。SAM 学这么多次都没有学会，其他算法学了就能马上在 NOI 上敲出来吗？
你说现在 CCF 注重思维而不是算法了。那么 t2 这样经典的 trick 为什么要做 1.5h？
今年的末尾 NOI Ag 都要 400+，除去笔试，就是 300+，是不是得达到将近 400 比较保险？是不是每天要切将近 2 题？那就得切紫题了。
需要加训！
我真的能银吗？
真不好说。
做个梦吧。今年末尾金是 571，去掉笔试是 471。所以要拿银，对标今年 NOI 的话，应该冲着至少每天打 2 题的水平。
我们都有美好的明天！
------------
update 2025.11.05
100+100+90+24
90 分，和过了差不太多。也算一个满意的成绩吧。
------------
根据云斗的统一评测，GD 有 20 个 AK。
很合理。但是好恐怖。
我是 GD rk54。全场唯一一个 314 分。
ZJ 也有 20 个 AK。吓哭了。
运动会好玩！