C
@cjdst教我E!
高桥总是有kkk个袋子,我们只需记录xxx的个数与kkk判断一下就行。
D
比较神秘的题目,A1A_1A1 与B1B_1B1 肯定是(x,y)(x,y)(x,y)之中一个,或者全部。
因为A1A_1A1 和B1B_1B1 选择是对称的,我们从A1A_1A1 分析:
注:我们称“自由”表示这个在mmm场都出现过,反之为“固定”。
1.A1A_1A1 为自由,B1B_1B1 为自由:AAA有n−1n-1n−1个选择,BBB有n−1n-1n−1个选择,但两者有重复。
2.A1A_1A1 为自由,B1B_1B1 为固定:AAA有n−1n-1n−1个选择,BBB方面在固定搭档中选≠A1\not= A_1=A1 的方案。
3.A1A_1A1 为固定,B1B_1B1 为固定:用setsetset求二者交集即可。
BBB同理,这样就做完了。
E
不会
F
竟然是codeforces的原题??!
先拿一道题做引子
先考虑减小无效边的情况,再考虑到连自己质数倍数一定最优(当然要自己手玩数据的),而且从编号大的往小的枚举一定不劣。
接着看这道题,它加入了边权,这怎么办呢?
还是想去运用上道题的思路,显然找质数倍数肯定不行了,注意到这道题V≤106V \le 10^6V≤106,我们可以考虑枚举边权底数ddd,从大到小枚举一定不劣。枚举此底数的倍数,能连就尽量连,直至连通,这样我们就做完了。
时间复杂度为调和级数O(VlogV)O(V \log V)O(VlogV)