DZY Loves Chinese
做这题时发现这里原来有第二道题，于是点进去看了看
DZY Loves Chinese II
注意对比两题红字部分
这题的
同样被异或了，然而后面又输入个数字，这样预处理一下，就知道异或的到底是个什么东西了。
于是这题就变成简单的字符串模拟，然后暴力求一下最后一次的并查集即可。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 |
#include<set> #include<map> #include<list> #include<queue> #include<cmath> #include<vector> #include<cstdio> #include<cctype> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define qread(x) x=read() #define lowbit(x) (x&-x) #define mes(x,y) memset(x,y,sizeof(x)) #define mpy(x,y) memcpy(x,y,sizeof(x)) #define Maxn 100000 #define Maxm 500000 #define Maxchar 1024 #define INF 2147483647 inline int read(){ int f=1,x=0;char ch; while(!(ch>='0'&&ch<='9')){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return f*x; } struct Edge{ int x,y; }e[Maxm+1]; int n,m,q,block,fa[Maxn+1],ans[Maxn+1]; bool v[Maxm+1]; char s[Maxchar+1]; int findfa(int x){ if(!fa[x]||fa[x]==x)return fa[x]=x; return fa[x]=findfa(fa[x]); } int fx,fy,tmp,len; int main(){ qread(n),qread(m); for(int i=1;i<=m;i++)qread(e[i].x),qread(e[i].y); qread(q); for(int i=1;i<=q;i++){ scanf("%d",&ans[i]); gets(s+1);len=strlen(s+1); tmp=0; for(int j=1;j<=len;j++){ if((s[j]>='0'&&s[j]<='9')&&!(s[j+1]>='0'&&s[j+1]<='9')){ tmp++; } } ans[i]=ans[i]^tmp; } for(int i=1;i<q;i++){ if(ans[i+1]>ans[i])printf("Connected\n"); else printf("Disconnected\n"); } int tmp=0; mes(v,false); for(int i=1;i<=len+1;i++){ if(s[i]>='0'&&s[i]<='9'){ tmp=tmp*10+s[i]-'0'; } else if(s[i-1]>='0'&&s[i-1]<='9'){ v[tmp^ans[q]]=true; tmp=0; } } block=n; for(int i=1;i<=m;i++){ if(v[i]==false){ fx=findfa(e[i].x);fy=findfa(e[i].y); if(fx!=fy){ fa[fx]=fy; block--; } } } if(block!=1)printf("Disconnected\n"); else printf("Connected\n"); } |