题解 CF787B 【Not Afraid】
rui_er
2020-09-04 23:12:49
题意简述：有 $2\times n$ 个人，编号分别为 $-n,-n+1,\cdots,-1,1,2,\cdots,n$，其中编号为相反数的两个人中有一个叛徒和一个好人。现在有 $m$ 个团队，知道团队成员的编号，问是否可能存在一个团队，所有人都是叛徒。
---
思路：
怎么保证一个团队至少有一个好人呢？我们知道编号为 $i$ 和 $-i$ 的两个人中有一个叛徒、一个好人，因此如果**存在** $i\in\left[1,n\right]$，满足 $i$ 和 $-i$ 编号的两个人在同一个团队里，那个团队就会有好人。
反过来，如果对于**所有** $i\in\left[1,n\right]$，$i$ 和 $-i$ 不同时在一个团队里，那么那个团队有可能全部都是叛徒——让团队中的那些人全为叛徒，相反数编号不在团队里，全为好人，即可构造。
因此，本问题转换为：求每一个团队中是否存在一对相反数。我们用一个映射（map）来记录出现过的数，然后统计即可。
---
代码：
```cpp
//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
int n, m;
map<int, int> mp;
int main() {
scanf("%d%d", &n, &m);
for(int i=1;i<=m;i++) {
int _;
scanf("%d", &_);
mp.clear();
bool ok = false;
while(_--) {
int x;
scanf("%d", &x);
if(mp[-x]) ok = true;
mp[x] = 1;
}
if(!ok) return puts("YES"), 0;
}
puts("NO");
return 0;
}
```