首页 > 代码库 > 玻璃球游戏
玻璃球游戏
【题目描述】
小x的业余生活中，有一项是玩滚玻璃球游戏。
某天，小x想到了一种很无趣的玩法，当然，这种玩法就是为了玩看题的你们。
小x首先建立了一个单向轨道，这个单向轨道可以抽象成一个有向图，每个顶点的出度都是1，也就是由每个点出发，只有一条边连向其他的点。
小x的游戏最初规则是这样的：让玻璃球从某一个点出发，沿着有向边的方向，移动到它的下一个顶点，如果还能移动，就继续移动，直到没有相邻的边，当然会存在在一个环里不停运动的情况。
为了增加难度，小x决定将游戏规则增强，他会提出一系列问题，让你回答：
1） 格式：1 X.查询玻璃球由编号为X的点出发，最终在哪个点停下来，如果能停下来，输出最后的点的编号，如果停不下来，输出”CIKLUS”.
2） 格式：2 X.删除由X出发的那条有向边。
【题解】
这题出的很有意思。
首先是逆向思维，把所有询问存下来，然后倒着往并查集里加边，这样就避免了删边。
然后是并查集的两个优化：
（1）按秩合并
描述：就是在对两个不同子集连接时，按照rank来连，也就是rank低的连在rank高的下面。rank高的做父亲节点。
作用，这样类似维护了一棵树，树是rank高的在上。
（2）路径压缩
描述：假如fa数组已经嵌套了N层，那么传统的做法去找祖先要做N次，当N很大时，这种做法很没效率。
路径压缩代码：
int find(int x) {return f[x]==x?x:f[x]=find(f[x]);}
十分简洁，十分好记，十分有效。
最后注意，这题来自JZYZOJ1823，要想AC必须汇编开栈。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<cmath> 6 #include<ctime> 7 #include<algorithm> 8 using namespace std; 9 struct node{int flag,x;}qu[300010];10 int n,q,a[300010],f[300010],vis[300010],ans[300010];11 inline int read()12 {13 int x=0,f=1; char ch=getchar();14 while(!isdigit(ch)) {if(ch==‘-‘) f=-1; ch=getchar();}15 while(isdigit(ch)) {x=x*10+ch-‘0‘; ch=getchar();}16 return x*f;17 }18 int find(int x) {if(x==-1)return -1;return f[x]==x?x:f[x]=find(f[x]);}19 int main()20 {21 //freopen("cin.in","r",stdin);22 //freopen("cout.out","w",stdout);23 int __size__=20<<20;24 char *__p__=(char*)malloc(__size__)+__size__;25 __asm__("movl %0, %%esp\n"::"r"(__p__));//汇编开栈26 n=read(); 27 for(int i=1;i<=n;i++) a[i]=read();28 q=read();29 for(int i=1;i<=q;i++)//逆向思维，变删边为加边30 {31 qu[i].flag=read(); qu[i].x=read();32 if(qu[i].flag==2) vis[qu[i].x]=1; ans[i]=-2;33 }34 for(int i=1;i<=n;i++) f[i]=i;35 for(int i=1;i<=n;i++)36 if(!vis[i]&&a[i])37 {38 int y=find(a[i]);39 if(i==y) f[a[i]]=-1;40 f[i]=a[i];41 }42 for(int i=q;i;i--)43 {44 if(qu[i].flag==1) ans[i]=find(qu[i].x);45 else 46 {47 int x=qu[i].x;48 int y=find(a[x]);49 if(x==y) f[a[x]]=-1;50 f[x]=a[x];51 }52 }53 for(int i=1;i<=q;i++)54 if(ans[i]==-1) printf("CIKLUS\n");55 else if(ans[i]!=-2) printf("%d\n",ans[i]);56 return 0;57 }
玻璃球游戏
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。