构造、交互、通信题

抽屉原理

摩尔投票

绝对众数：在可重集合中出现次数严格大于一半的元素。

思路：维护当前剩下的数是什么，以及它的数量，然后以一换一，最后剩下的绝对是绝对众数。

• Choosing Ads

  对于一个符合要求的数 \(x\)，设其出现次数为 \(c\)，则有 \(c \ge len * p\%\)。若令 \(q = \lfloor \frac{100}{p} \rfloor + 1\)，则 \(c > \frac{len}{q}\)。于是我们每次删除 \(\frac{len}{q}\) 个互不相同的数，再用线段树维护即可。

• Matching vs Independent Set

  好巧妙的题目！我感觉想到它，我们需要观察题目中的“或”， 并大胆猜想。

  先随意求出一组边独立集。如果它 \(\ge n\)，则输出；否则我们可以据这组边独立集构造出一组点独立集，且其一定 \(> n\)。