CSP-S2025游记
wanghuwang666 · · 生活·游记
CSP-S2025 游记
刚坐上，电脑显示屏有问题，左边有两道彩色条条，右下角都是黑的，显不出来，无伤大雅。
打开文件，鼠标滚轮🖱不听我话，直接划到了T2🚀，最小生成树？算了算了，先写 T1。开 T1 开 T1，什么？！上难度了，比去年 T1 强多了。看看再看看，还是不会。想了个贪心思路，发现样例没过。
把贪心搞得更贪，先考虑 1 组再考虑 2 组后考虑 3 组，先考虑 1 组再考虑 3 组后考虑 2 组，先考虑 2 组再考虑 1 组后考虑 3 组……六♻种顺序都搞了一遍，存6个答案！样例对了！大数据一个没过。
贡献？不行。后来又考虑二分，发现很难判定。dp？不可能不可能！不能是 DP！徘徊彷徨了一阵子，开始背起一字口诀。
想起一字决，“优”！是用优先队列还是大根堆呢？啥？这俩难道是一个东西（为此我思考🤔了 10 秒钟），噢！真是一个东西！换，是用 set 还是优先队列呢？还是大根堆好用，用大根堆。
整理了一下思路，先把所有人的贡献从大到小排序，再把所有人最大贡献从大到小排序，导致我第一次在结构体里开了一个结构体。码风很怪异。
写完了，编译、运行，心里却想：不会对的不会对的，样例可能都不过，一直在这样安慰自己。后来我惊奇的发现，小样例过了！大样例——超时了！
lemon🍋果然不是人信的东西，开了C++14，硬是让我险过 80 分。不应该呀，我写的食间腐杂度管够啊？
想起我考前背的快读板子，把它写了下来。哇！我的快读居然通过编译了！把大样例也给救活了✅！第一次莫队快读板子，也是整场比赛唯一用到昨天复习的一大堆板子中唯一用到的。
开 T2，果然是最小生成树！把所有边建上跑 Kruskal 不就行了！以为自己过了 T2，谁知道输出了个 112，不愧是 T2，肯定不是这么简单的题。
注意到人人实力有限，考虑暴力，时间复杂度
又注意到有很难评价的做法，先跑最小生成树🌳，在对于每一条乡镇边把连接的两个城市路径上最长的边换了，不就行了吗！
于是开始打最近公共祖先，我居然默下来了！（虽然语文卷子两个字形全部写错）但是输出了106，进步了！比 112小！白打这么长时间板子。
想到这种图论题不是人写的，于是开始看 T3，字符串！不是人写的，跳 T4。
8 分数据还是好得的😃，又注意到
于是开始静😶等结束……
静等🥱…… 静等😴……
T2 还有救吗？燃了一会儿，没救。
一想 T3 不写白不写，于是全部输出0⭕。
交文件🖥⌨🖱……
走人🏃♂️！