题解 [email protected]洛谷 | [email protected] 【Not Afraid】

题意简述:有 2×n2\times n 个人,编号分别为 n,n+1,,1,1,2,,n-n,-n+1,\cdots,-1,1,2,\cdots,n,其中编号为相反数的两个人中有一个叛徒和一个好人。现在有 mm 个团队,知道团队成员的编号,问是否可能存在一个团队,所有人都是叛徒。


思路:

怎么保证一个团队至少有一个好人呢?我们知道编号为 iii-i 的两个人中有一个叛徒、一个好人,因此如果存在 i[1,n]i\in\left[1,n\right],满足 iii-i 编号的两个人在同一个团队里,那个团队就会有好人。

反过来,如果对于所有 i[1,n]i\in\left[1,n\right]iii-i 不同时在一个团队里,那么那个团队有可能全部都是叛徒——让团队中的那些人全为叛徒,相反数编号不在团队里,全为好人,即可构造。

因此,本问题转换为:求每一个团队中是否存在一对相反数。我们用一个映射(map)来记录出现过的数,然后统计即可。


代码:

//By: [email protected]_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;
}