怕是最后一个暑假好好学 OI 了,好好卷,争取弥补高一的遗憾吧。
7.7
【UER #1】DZY Loves Graph
乍一眼一看,加边、删边、回溯三种操作,后来发现漏看了一些重要的东西:
- 每次加的边长度单调递增,这意味着如果只有加边操作第一次形成最小生成树后答案一直会是这棵树。
- 删最大的 \(k\) 条边,这意味着一旦破坏了最小生成树不可能有别的边代替删除的边使其再次连通。
- 回溯只回溯前一个操作,且不会连着回溯。
- 每条边只会被真实地删一次(不包括回溯掉的)
用按秩合并优化的并查集维护图,单次加边 \(O(\log n)\) ,单次删边 \(O(1)\) 。
回溯的话,如果前一个为 \(\text{Add}\) ,那就直接加边删边。如果前一个为 \(\text{Delete}\) ,那删边操作看删完后是否破坏之前的生成树(或本来就没有),不用去真的删边。
复杂度 \(O(m \log n)\)
牛客练习赛113
转化题意后就是求模 \(n\) 意义下的一个二元同余方程,考虑枚举其中一元,在 \(O(n)\) 的时间内可取遍模 \(n\) 意义下所有余数,以此算出另一元,暴力枚举统计即可。
一个数组中最多可能有两个元素出现的次数不少于一半,且只有在两种元素各占一半的时候取到两个最多。考虑枚举最多的元素是哪一个,设元素 \(x\) 一共有 \(s\) 个。那它的贡献即为:
\[\sum_{i=1}^{s}\sum_{j=0}^{i}\binom{s}{i}\binom{n-s}{j}
\]
最后要把存在两个元素各占一半的情况减掉。
\(\text{F}\) 直接按上式枚举统计即可,\(\text{G}\) 把带 \(i\) 的部分分离出来,剩下的可递推计算。