2025CSP-S游记/总结
Balanced_sm · · 生活·游记
前情提要
我在中山某个强校集训，但是这里的教练叫我们不要在网上发有关集训的任何内容，哪怕说在哪集训都不可。
总之我向天天被模拟赛暴打
正文
由于10.31的CSP-S模拟我个人觉得比去年难度大挺多，遂与当天早上与同学讨论今年会不会很难，但在看到J组的题后放心了，觉得J组简单的话S应该也不会太难 ，结果J的难度补到S上了……
开考前的监考老师在说注意事项时举了亿些上午的例子，但叫我们不要外传（原话：刚刚说的那些只是极少数情况啊，不要外传啊，不然我小命不保）
开考前还在因为监考老师的发言而笑嘻嘻，开考后就笑不出来了……
一开始一眼看出T1是贪心，但很遗憾，我写了一坨5K的神秘玩意后测大样例，发现竟然错了1组，在经历一段时间的调试修改和深思熟虑后，我觉得这不是贪心，这是DP,然后光速想到了式子，但我不知道DP不是正解，试图优化，发现时间余额不足，随便糊了一坨
此时考试时间已经过半，而只写了T1部分分的我心态开始爆炸——对标一下去年的难度，我不是废物还有谁能是……
所以真的不要给题目预设难度区间，和预期不符时很搞心态，容易把做不出这题归为自己能力问题……
还好我这个类人物体虽然心态不咋地，但好在策略没有特别糟，我在做题前把所有题都看了一遍，所以初始都有个暴力思路，不至于完全因为心态炸掉而导致智商为负最终连暴力都写不好 （虽然我T2确实受我心态挺大影响，发神经搞了特殊点的特判，但是错的，本来我的暴力是能过所有特殊点的，这样一搞，差不多20分无了TAT）
接下来先写了个T4的暴力搜索，随手加了点剪枝 （大袜子你是真的一点都不怕剪到大动脉吗）——目前剩下的小于m就不用继续搜了，搜下去也不可能从不合法变为合法，直接return掉，在剩下的人中，如果已经选了大于等于m个人，那其他无论怎么排都会是合法的，直接加上，虽然我不知道这些剪枝能不能帮我多拿点分，但反正当时顺手就写了。
返回T2一看，这不是31号CSP模拟中出现了足足2次的最小生成树嘛，那我可太会了，但那些诡异的乡镇点应该怎么选呢，不知道啊时间不够了先枚举吧。
光速 （并非） 写完了暴力，开始考虑时间时间复杂度会不会有点爆表，就在这时这个诡异类人物体开始将进行思考的器官切换为脚……我给特殊点加了点诡异的处理，本身这个处理没问题，这个想法确实可以起到对特殊点起到优化作用，但是！但是！我在读每个乡镇点的数据时动了n!我动了n!这样它在读入时就会出错，最后结果是读入本应该完了却还依旧在进行读入，最后会水灵灵的TLE…… （20分啊那可是20分啊！！！！） 希望这个只有特殊点会跑到那个特判那里，不然我就完蛋了啊啊啊啊啊，分都没了啊……
还剩个T3，一眼看出
T3的暴力我后面还原出来在洛谷测出了40分，太恐怖了，希望CCF的数据也那么水 （祈祷ing）。
T3我是这样写的，预处理字符串t1、t2在位置i前有多少位是不同的，然后枚举n，枚举交换的起始位置，如果这个位置前有字符不同就可以break掉，去查下一对s了，如果在这个交换区间后有字符不同，就continue一下，继续去找下个位置，如果前缀后缀都相同的话就遍历一遍区间是否每个字符都对得上，是的话就++cnt。这个做法时间复杂度应该是
经验总结
不要给题目预设难度，试题不可能都完全符合往年情况的，把简单的想难了有可能会导致做不出，把难的想简单了可能会搞心态，所以对于难度的判断只看题目本身就好，不要结合这是什么考试的T几，这些对于那个题目来说都是无关紧要的，重要的全在题目里。
时间不够也不要太慌，开始做题前先把题目过一遍，最好有个暴力思路，这样后面时间不够思考了的时候可以直接写暴力，而且先过一遍心里也有个底，不至于太害怕时间的问题。
如果要给特殊点特判，想清楚，你的优化想法可能是对的，但你的实现有问题，这也无掉了，如果本身就能过，没必要再去折腾专门特判特殊点，别给本身能过的搞不能过了。
在卡住时一定要跳，别死磕，死磕会完蛋，这里拿不到分，其他地方也拿不到就废了。