题目链接：http://codeforces.com/contest/469/problem/d 题目的意思就是把n个不同的数分成2个集合。。 if number x belongs to set a , then number a ?-? x must also belong to set a . if number x belongs to set b , then number b ?-? x must also be
题目链接：http://codeforces.com/contest/469/problem/d
题目的意思就是把n个不同的数分成2个集合。。
if number x belongs to set a, then number a?-?x must also belong to seta.if number x belongs to set b, then number b?-?x must also belong to setb.这问题，一看上去。。应该很是简单。。
当我们看到第一句话的时候，大多数情况下，都这么认为。。
如果x 和a - x 同时存在的话，那么 他们一定属于a集合。。
同理。。。x 和 b -  x 同时存在的话，那么他们一定属于b集合。。。
乍一看，没有什么样的错误。。。。
对于任何的问题，我们需要认真深入的思考。。。。- - 。。
看了题解的思路，以及我们最少应该知道的一些结论。。。
1.如果 x 和 a -  x 同时存在的话， 那么他们不一定是在a集合里面的。。为什么？
比如，如果存在ｘ，ａ－ｘ，ｂ－ｘ，ｂ－ａ＋ｘ，那么他们全部属于ｂ集合。。。这是没有问题的。。。
这就直接的否定了我们上面的结论。。
也就是说，如果ｘ和ａ－ｘ同时存在，那么，也不一定在a或b中。。
2.如果a - x不存在，那么x一定不在a集合，也就一定在b集合里面。。
为什么？？ 因为，在a中没有与之相对应的a - x。。。。...
同样。。如果b -  x不存在，那么x一定不在b集合里面。
并查集做之。。。
code：
#include #include #include #include #include #include using namespace std;const int n = 1e5 + 5;map m;int father[n], arr[n];int find(int x){ if(father[x] == x) return x; else return father[x] = find(father[x]);}void union(int x, int y){ int a = find(x), b = find(y); if(a == b) return ; father[a] = b;}int main(){// freopen(1.txt, r, stdin); int n, a, b; cin >> n >> a >> b; for(int i = 1; i > arr[i]; m[arr[i]] = i;// 离散化一下就好。。 } for(int i = 1; i = 2) printf( ); if(find(i) == find(n + 1)){ printf(0); } else printf(1); } printf(\n); } return 0;}
虽然，不怎么理解这样的做法。。但是，还是感觉很厉害的样子。。。