题解 P4212 【外太空旅行】

引领天下

2018-09-18 20:46:49

Solution

这题目其实是bitset的一个很好的应用,再结合一下楼下的随机数算法即可AC。 注意一下,**由于两个人之间要么是朋友要么是敌人**,那么我们可以考虑将两个人之间的关系改为**2进制**。这就是bitset的原理。 bitset很强大,可以对很多数据类型进行转换,重点是:**支持运算操作!** 那么这题的做法就很显然了:直接用一个bitset `now` 来维护当前顺序可以入选的名单(用 `&` 运算可以模拟水火不容 or 基♂情满满) 剩下来的就是用随机生成顺序来取最大值了,最后存答案的bitset `ans` 的数量( $ ans.count() $ 就是答案)。(ans中1的个数即表示有多少人能和睦相处) 代码就不贴了,只有18行,相信大家都能打出来。