提示
我只做前面两道题目,ee
T1
注意到至多只有一个社团会超人,因此考虑将人多的社团放到其他社团去
T2
注意到 k≤10k\le 10k≤10,考虑 2k2^k2k 枚举改造哪些乡村。
你会发现,不用每次都排序,可以先将 mmm 条边排好序,乡村的边借用链表思想。
目前是 O(mlogm+2k(m+nk))O(m \log m+2^k(m+nk))O(mlogm+2k(m+nk)) 会超时。
注意到可以先筛选出 n−1n-1n−1 条边,因此可以变为 O(mlogm+2knk)O(m \log m+2^knk)O(mlogm+2knk)。
后续改题
T1
我学到了代码实现方法
T2
其实完全不用链表的插入方式,可以之间将 n−1+nkn-1+nkn−1+nk 条边排好序,在后续处理中遇到未加入的乡村直接跳过即可。
总结
题目整体难度不大,主要是代码能力的考验