从入门到头秃周末休闲赛37诚实的人
题目大意:有n个人,这些人分成两部分:1.诚实的,他说的话全是真实的。2.不友善的,他说的话可能是真也可能是假。
每个人说了ai句话:第i个人的第j句话是:x是y的,其中x表示一个人的编号,y是1或者0,表示诚实和不友善。现在问最多可能有多少人是诚实的。
解题思路:
看到了n的范围小于15,考虑二进制枚举出所有情况,然后分别加以判断。
例如有五个人,其中一种二进制枚举出的情况是00110,那么我们只需要判断第三和第四个人说的话是否矛盾即可,其余的人可以直接跳过。
判断思路:
如果a说x是诚实的,但是b说x是不友善的,那么当前枚举的情况不成立
如果a说x是诚实的,但是x在当前枚举的情况中是不友善的,那么当前枚举的情况不成立
如果a说x是不友善的,但是x在当前枚举的情况中是诚实的,那么当前枚举的情况不成立
AC代码:
1 | struct node |