首页 > 代码库 > BZOJ3563 DZY Loves Chinese
BZOJ3563 DZY Loves Chinese
本文版权归ljh2000和博客园共有,欢迎转载,但须保留此声明,并给出原文链接,谢谢合作。
本文作者:ljh2000
作者博客:http://www.cnblogs.com/ljh2000-jump/
转载请注明出处,侵权必究,保留最终解释权!
题目链接:BZOJ3563
正解:并查集
解题报告:
这道题真是有趣…
直接通过读入的数的个数一路推出每次做完之后的$ans$,只需要暴力做最后一次,然后回答询问就可以了,并查集维护…
$BZOJ$的字符串读入真是各种鬼畜,调了好久才没$RE$…
//It is made by ljh2000 //有志者,事竟成,破釜沉舟,百二秦关终属楚;苦心人,天不负,卧薪尝胆,三千越甲可吞吴。 #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <cmath> #include <algorithm> #include <ctime> #include <vector> #include <queue> #include <map> #include <set> #include <string> #include <complex> #include <bitset> using namespace std; typedef long long LL; typedef long double LB; typedef complex<double> C; const double pi = acos(-1); const int MAXN = 300011; const int MAXM = 1000011; int n,m,q,a[MAXN],ans[MAXN],b[MAXN],stop[MAXN],father[MAXN]; char ch[MAXN]; struct edge{ int x,y; }e[MAXM]; inline int find(int x){ if(father[x]!=x) father[x]=find(father[x]); return father[x]; } inline bool ok(char c){ if(c<=‘9‘ && c>=‘0‘) return true; return false; } inline int getint(){ int w=0,q=0; char c=getchar(); while((c<‘0‘||c>‘9‘) && c!=‘-‘) c=getchar(); if(c==‘-‘) q=1,c=getchar(); while (c>=‘0‘&&c<=‘9‘) w=w*10+c-‘0‘,c=getchar(); return q?-w:w; } inline void work(){ n=getint(); m=getint(); for(int i=1;i<=m;i++) { e[i].x=getint(); e[i].y=getint(); } q=getint(); int len,now,r1,r2; for(int i=1;i<=q;i++) { a[i]=getint(); gets(ch); len=strlen(ch); ch[len+1]=‘ ‘; for(int j=0;j<len;j++) if(ok(ch[j]) && !ok(ch[j+1])) b[i]++; } for(int i=q-1;i>=1;i--) ans[i]=b[i+1]^a[i+1]; for(int i=1;i<q;i++) if(ans[i]==ans[i-1])/*!!!*/ puts("Disconnected"); else puts("Connected"); now=0; for(int i=0;i<len;i++) { if(ok(ch[i])) now=now*10+ch[i]-‘0‘; else if(ok(ch[i-1])) stop[now^ans[q-1]]=1,now=0; } stop[now^ans[q-1]]=1;//!!! for(int i=1;i<=n;i++) father[i]=i; for(int i=1;i<=m;i++) { if(stop[i]) continue; r1=find(e[i].x); r2=find(e[i].y); if(r1==r2) continue;//!!! father[r1]=r2; } for(int i=2;i<=n;i++) if(find(1)!=find(i)) { puts("Disconnected"); return ; } puts("Connected"); } int main() { work(); return 0; } //有志者,事竟成,破釜沉舟,百二秦关终属楚;苦心人,天不负,卧薪尝胆,三千越甲可吞吴。
BZOJ3563 DZY Loves Chinese
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。