2025CSP第二轮游记

· · 生活·游记

day-30 ~ day-1

DP + 组合数，稍微复习了一下数据结构和字符串。

day0

11：30到学校，12：00问了考普及的同学，稍微口糊了4道题，比去年简单。

2：30开始，找准考证找到了2：15，进考场， 打完头文件，监考老师发密码。

2：35开始看考题，T1看到了 n/2 ，这不是绝对众数吗？之前写题遇到过，看范围， n\le10^5 dp不可做，一眼贪心，写代码写了15分钟，加上调和测样例，半小时写完。

T2是最小生成树，一眼 2^knk\log{nk}，但可悲的是最后那个 \log 也没有优化掉，其实只需事先把 nk 条边排序一下，枚举时扫一遍即可，可惜后面一直在优化 2^k，浪费了半小时，打完只剩 2.15 小时了，测完样例匆匆跑掉，估分 [64,80]。

此时还有2小时，一等肯定稳，喝了口水开 T3，开始认为可以多次替换，感觉暴力都写不出来，然后看大样例时突然醒悟，打了 25 分暴力匹配跑掉了（我应该写个hash或kmp的，有40分）。

只有 30 分钟了，匆匆开T4，n! 全排列打完，看到了 m \le 1 的性质，以为直接输出 n! 即可，后面发现有 0 的情况，推错了，但没时间了，直接交吧。

还有 3 分钟，还在推T4的部分分，熬到了最后一秒，我是考场最后一个走的。

估分：100+[64,100?]+[20,25]+[8,12]=[192,237]，正常发挥。

后记

周天去武汉打 ICPC，2题，提前一小时跑路，好像是第一个出来的。

很快金牌佬帮我们 JX 破解了代码，去交代码，洛谷 234，云斗 241，梦熊 222，NOIp 肯定能去，wc别想了。

出分了，222，100+84+30+8，事实证明梦熊是最准的，省排 20，感觉 NOIp 一等有望。