CSP2025总结+订正

li_cat · 2025-11-02 20:56:32 · 个人记录

游记全站推荐了，就这边另起炉灶吧

赛时教训总结

• T1时间浪费严重，估计严重偏离(dp估计20min,调了2h)，边界写错;以及在明知消耗了大量时间的情况下继续调
• T1没有研究清楚问题就开始写贪心，原本的反悔想法没有深挖去切到另一个思路
• T2大胆猜到了结论，然后大胆把它推翻了，没有比较明确的逻辑推翻它

  订正

  T1

  T2

  孩子们大胆猜想小心证伪是对的

  引理:对于任意一棵原图的最小生成树，新图都只会删掉其中一些边而不会新增原图的其他边

  考虑使用反证法，对于一棵已有的树，如果可以把其它的边换上去更优的话：

• 它能换的边只有两端的点在最小生成树上形成的路径
• 更优的前提是，这条边比它们小 这与它是原图的最小生成树矛盾

于是就可以提前排好做一遍，把 n-1 条边提到前面，其它的也提前排好，用的时候直接归并

然后暴力枚举 k

时间复杂度 O(2^knk\alpha(nk)+(m+kn)\log m)

T3

T4

之后训练规划

比赛策略出现了重大失误，赛时所需的评估能力非常缺乏

再加上训练时间本来就少，可能得考虑划分出一个做题的程序