csp-S总结

· · 生活·游记

T1

很简单地贪心，写了40min

T2

先说暴力做法O(m*2^k) ，把初始的边与乡村的边一起排序，然后再枚举乡村的集合，求最小生成树耗时约40-50min

然后接着写正解，隐隐感觉我写的东西根正解有莫大的关系，以为复杂度差得不多只有O(1e9),想到只保留最开始的n-1条边（最小生成树树边），因为最优的选法一定是连上枚举的乡村后，再断开一些边，非树边不会比树边优，故而是对的

对拍了

T3

大失误，一直写特殊性质，只有5pts

T4

先打得T4（暴搜）导致T3的暴力没打上

估分

100+100+5+8=213