http://codeforces.com/contest/469/problem/D
题目大意：
给你一个长度为n数组，给你两个集合A、B，再给你两个数字a和b。A集合中的每一个数字x都也能在a集合中找到x-a的数字。同理，b集合也一样。问，这个数组能否分成这两个集合？（然后坑点就是集合里面的元素可以为空）
思路一：
首先定义type函数，-1表示不在任何集合内，0表示A集合内，1表示B集合，2表示该元素是a的一半。（之所以要表示成2的原因是因为这个数值很特殊，a-x=x，所以他可以满足A集合，但是同时也可能存在ty=-1的数值y，他的b-y=x，所以这个时候集合是可以发生改变的）
我们先暴力枚举并且二分找一下满足条件数组A里面的元素。再找一下数组B里面的元素，且在找这个数组B的时候不能修改A中集合中的元素（即ty=0）。
然后我们暴力发现还存在ty=-1的数值，那么他肯定不满足属于A集合，因此可能是属于B集合的，所以我们对该元素进行bfs一下就好了。
复杂度O（n）
//看看会不会爆int!数组会不会少了一维！ //取物问题一定要小心先手胜利的条件 #include <bits/stdc++.h> using namespace std; #pragma comment(linker,"/STACK:102400000,102400000") #define LL long long #define ALL(a) a.begin(), a.end() #define pb push_back #define mk make_pair #define fi first #define se second #define haha printf("haha ") const int maxn = 1e5 + 5; int p[maxn], ans[maxn], ty[maxn]; map<int, int> id; int a, b, n; ///a type is 0，b is 1, 2 is suit for a void bfs(int w){ queue<int> que; que.push(w); while (!que.empty()){ int pos = que.front(); que.pop(); int bval = b - p[pos]; int mypos = lower_bound(p, p + n, bval) - p; if (p[mypos] == bval) { if (ty[mypos] != 1) { int aval = a - p[mypos]; int sonpos = lower_bound(p, p + n, aval) - p; if (p[sonpos] != aval) continue; if (ty[sonpos] != 1){ que.push(sonpos); ty[sonpos] = -1; } } else continue; ty[mypos] = ty[pos] = 1; } } } bool solve(){ if (p[n] >= a && p[n] >= b) return false; ///集合在a里面 for (int i = 0; i < n; i++){ if (p[i] >= a) break; if (ty[i] == 0) continue; if (p[i] * 2 == a) { ty[i] = 2; continue; } int val = a - p[i]; int pos = lower_bound(p, p + n, val) - p; if (pos >= n || p[pos] != val) continue; if (ty[pos] == -1){ ty[pos] = 0, ty[i] = 0; } } ///集合在b里面 for (int i = 0; i < n; i++){ if (p[i] >= b) break; if (ty[i] == 0 || ty[i] == 1) continue; if (p[i] * 2 == b && ty[i] == -1){ ty[i] = 1; continue; } int val = b - p[i]; int pos = lower_bound(p, p + n, val) - p; if (pos >= n || p[pos] != val || ty[pos] == 0) continue; if (ty[pos] == -1 || ty[pos] == 2){ ty[pos] = 1, ty[i] = 1; } } for (int i = 0; i < n; i++) if (ty[i] == -1) bfs(i); for (int i = 0; i < n; i++){ if (ty[i] == -1) return false; if (ty[i] == 2) ty[i] = 0; } return true; } int main(){ int cnt = 0; cin >> n >> a >> b; for (int i = 0; i < n; i++){ scanf("%d", p + i); id[p[i]] = cnt++; } sort(p, p + n); memset(ty, -1, sizeof(ty)); bool flag = solve(); if (flag){ puts("YES"); for (int i = 0; i < n; i++){ int myid = id[p[i]]; ans[myid] = ty[i]; } for (int i = 0; i < n; i++){ printf("%d ", ans[i]); } cout << endl; } else puts("NO"); return 0; }
思路二：
当然，这题还可以用并查集来分配
假定，如果存在x，在数列中不存在a-x的数字，那么他一定属于集合B，同理，存在x，在数列中不存在b-x的数字，那么他一定属于集合A。然后我们只要利用这个条件，然后用并查集维护一下就好了。
这个的话可以看这个人的代码： 链接在此