小X有n个互不相同的整数：
· 如果x属于A，那么a-x也肯定属于A。
· 如果x属于B，那么b-x也肯定属于B。
判断一下是否存在一种方案来分配这些数字到集合A，B中。
注意：如果一个集合为空也是可以的。
Input单组测试数据。第一行有三个整数n,a,b (1≤n≤10^5; 1≤a,b≤10^9)。第二行有n个不一样的整数 p1,p2,...,pn (1≤pi≤10^9).Output如果可行，那么输出YES，否则输出NO。Input示例样例输入14 5 92 3 4 5Output示例样例输出1YES此题的思路与 hiho一下 第一百三十四周 #1468 : 2-SAT·hihoCoder新春晚会 【2-SAT 之 枚举--搜索】 类似
都是从头开始枚举这个点的两个情况---然后收到这个枚举影响的点加入队列继续枚举----看情况是否成立。
可以先预处理出来每个数的A连点和B连点。
当考虑 i 为A时 ，判断 i 和 i的A连点是否可以为A --可以的话将 i和i的A连点 放入队列并标记---
当从队列中取时 ， 判断 i 是否有 B连点， 当有B连点j的话，因为 i 已进入A ，那么 j 就不能进入B --- 即只能进入A -------- （如果有矛盾的情况，则枚举失败，所有此次枚举标记的点恢复未标记状态。）
考虑 i 为 B 的方法与上面一致-.- ------------- 飘过-.-
代码：
#include<stdio.h>#include<string.h>#include<queue>#include<stack>#include<iostream>#include<algorithm>using namespace std;int n,a[100100],b[100100][2],ans[100100];queue<int > qa;stack<int > sa;void my_clear(){ while (!qa.empty()) qa.pop();}void myjinA(int x){ qa.push(x); sa.push(x);}int main(){ int t,A,B,k,x,y; cin>>n>>A>>B; for (int i=0;i<n;i++) cin>>a[i]; sort(a,a+n); memset(b,-1,sizeof(b)); memset(ans,-1,sizeof(ans)); bool fafe=true; for (int i=0;i<n;i++) { k=lower_bound(a,a+n,A-a[i])-a; if (k>=0&&k<n&&a[k]==A-a[i]) b[i][0]=k; k=lower_bound(a,a+n,B-a[i])-a; if (k>=0&&k<n&&a[k]==B-a[i]) b[i][1]=k; if (b[i][0]==b[i][1]&&b[i][0]==-1) fafe=false; } if (!fafe) { PRintf("NO/n"); return 0; } for (int i=0;i<n;i++) { if (ans[i]==-1) { //---------入A if (b[i][0]!=-1&&ans[i]==-1&&ans[b[i][0]]==-1) { my_clear(); x=i;y=b[x][0]; myjinA(x); myjinA(y); ans[x]=0; ans[y]=0; while (!qa.empty()) { x=qa.front(); qa.pop(); if (b[x][1]!=-1&&ans[b[x][1]]==-1) { x=b[x][1]; if (b[x][0]!=-1&&ans[b[x][0]]==-1) { y=b[x][0]; myjinA(x); myjinA(y); ans[x]=0; ans[y]=0; } else { fafe=false; } } if (!fafe) break; } if (!fafe) { while (!sa.empty()) { x=sa.top(); sa.pop(); ans[x]=-1; } } } //入B if (b[i][1]!=-1&&ans[i]==-1&&ans[b[i][1]]==-1) { fafe=true; my_clear(); x=i;y=b[x][1]; myjinA(x); myjinA(y); ans[x]=1; ans[y]=1; while (!qa.empty()) { x=qa.front(); qa.pop(); if (b[x][0]!=-1&&ans[b[x][0]]==-1) { x=b[x][0]; if (b[x][1]!=-1&&ans[b[x][1]]==-1) { y=b[x][1]; myjinA(x); myjinA(y); ans[x]=1; ans[y]=1; } else { fafe=false; } } if (!fafe) break; } if (!fafe) { while (!sa.empty()) { x=sa.top(); sa.pop(); ans[x]=-1; } } } if (!fafe) break; } if (ans[i]==-1) { fafe=false;break; } } if (fafe) printf("YES/n"); else printf("NO/n"); return 0;}/*3 11 124 7 83 5 62 3 4*/
新闻热点
疑难解答
