这题看了PKKJ的wiki才会的,他虚设一个点Xn=0,然后就变得很方便处理了!!!
/**//* 有n(n<=20000)个未知的整数X0,X1,X2Xn-1,有以下Q个(Q<=40000)操作: I p v :告诉你Xp=v I p q v :告诉你Xp Xor Xq=v Q k p1 p2 … pk : 询问 Xp1 Xor Xp2 .. Xor Xpk, k不大于15。 如果当前的I跟之前的有冲突的话,跳出
并查集扩展! 对于I p v ,如果虚设一个点Xn=0,则可以看成 I p n v (与0异或) 所以对于所有那些I,都是a^b=v,两个两个的,连带的效果 所以设val[i]=Xi^Xfa[i] 跟上面一样有连带效果 fa[i]为i的父亲 这样: 1) I p q v 先find 如果p q在同一集合,判断是否有Xp^Xq=v 不是的话矛盾 否则,合并 注意虚设的点n要始终保持为根 2)Q k p1pk Xp1 ^ Xp2 ^ Xpk 转化为: val[p1] ^ val[p2] ^ val[k] ^ (Xfa[p1] ^ Xfa[p2] ^ Xfa[pk]) val[pi]已知,只需判断Xfa[pi]是否已知 由于是异或,奇数个Xfa[pi]才需判断。判断方法为看他的根是不是Xn即可 */ #include<cstdio> #include<cstring> #include<algorithm> #include<vector>
using namespace std;
const int MAXN = 20010;
int fa[MAXN],val[MAXN]; int n,q;
void init(int n) { for(int i=0;i<=n;i++) { val[i]=0; fa[i]=i; } } int find(int a) { if(a!=fa[a]) { int t=fa[a]; fa[a]=find(fa[a]); val[a]^=val[t]; } return fa[a]; }
bool unin(int a,int b,int v) { int ra=find(a); int rb=find(b); if(ra==rb) { return v==(val[a]^val[b]); } if(ra==n)swap(ra,rb); fa[ra]=rb; val[ra]=val[a]^val[b]^v; return true; }
char cmd[MAXN];
int main() { //freopen("in","r",stdin); int t=1; while(scanf("%d%d",&n,&q),n) { printf("Case %d:\n",t++); init(n); int fact = 0; bool err = false; for(int i=0;i<q;i++) { scanf(" %c",&cmd[0]); if(err){gets(cmd);continue;} if(cmd[0]=='I') { gets(cmd);//需要这样子 fact++; int x,y,v; if(sscanf(cmd,"%d%d%d",&x,&y,&v)==2)//sscanf() 直接scanf()会错不知为啥 { swap(y,v); y=n; } if(!unin(x,y,v)) { err = true; printf("The first %d facts are conflicting.\n",fact); } } else { int k,x,ans=0; vector<pair<int,int> >V; scanf("%d",&k); for(int j=0,jj;j<k;j++) { scanf("%d",&x); int rx = find(x); ans^=val[x]; for(jj=0;jj<V.size();jj++) { if(V[jj].first==rx)break; } if(jj==V.size())V.push_back(make_pair(rx,1)); else V[jj].second^=1; } bool flag = true; for(int j=0;j<V.size();j++) { if(V[j].second) { int rx=find(V[j].first); if(rx!=n){flag=false;break;} ans^=val[V[j].first]; } } if(flag)printf("%d\n",ans); else puts("I don't know."); } } puts(""); } return 0; }
|
|
常用链接
随笔分类
Links
搜索
最新评论
|
|