专栏文章

CSP2025总结+订正

lli_cat
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minepgdh
此快照首次捕获于
2025/12/02 01:11
3 个月前
此快照最后确认于
2025/12/02 01:11
3 个月前
查看原文
游记全站推荐了，就这边另起炉灶吧

赛时教训总结

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

订正

T1

T2

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

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

考虑使用反证法，对于一棵已有的树，如果可以把其它的边换上去更优的话：
  • 它能换的边只有两端的点在最小生成树上形成的路径
  • 更优的前提是，这条边比它们小 这与它是原图的最小生成树矛盾
于是就可以提前排好做一遍，把 n−1n-1 条边提到前面，其它的也提前排好，用的时候直接归并
然后暴力枚举 kk
时间复杂度 O(2knkα(nk)+(m+kn)log⁡m)O(2^knk\alpha(nk)+(m+kn)\log m)

T3

T4

之后训练规划

比赛策略出现了重大失误，赛时所需的评估能力非常缺乏
再加上训练时间本来就少，可能得考虑划分出一个做题的程序

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...