动物王国中有三类动物A,B,C,这三类动物的食物链构成了有趣的环形.A吃B,B吃C,C吃A.现有N个动物,以1-N编号.每个动物都是A,B,C中的一种,但是我们并不知道它到底是哪一种.有人用两种说法对这N
来源:学生作业帮助网 编辑:六六作业网 时间:2024/12/25 00:14:50
动物王国中有三类动物A,B,C,这三类动物的食物链构成了有趣的环形.A吃B,B吃C,C吃A.现有N个动物,以1-N编号.每个动物都是A,B,C中的一种,但是我们并不知道它到底是哪一种.有人用两种说法对这N
动物王国中有三类动物A,B,C,这三类动物的食物链构成了有趣的环形.A吃B,B吃C,C吃A.
现有N个动物,以1-N编号.每个动物都是A,B,C中的一种,但是我们并不知道它到底是哪一种.
有人用两种说法对这N个动物所构成的食物链关系进行描述:
第一种说法是"1 X Y",表示X和Y是同类.
第二种说法是"2 X Y",表示X吃Y.
此人对N个动物,用上述两种说法,一句接一句地说出K句话,这K句话有的是真的,有的是假的.当一句话满足下列三条之一时,这句话就是假话,否则就是真话.
1) 当前的话与前面的某些真的话冲突,就是假话;
2) 当前的话中X或Y比N大,就是假话;
3) 当前的话表示X吃X,就是假话.
你的任务是根据给定的N(1 >x>>y;
\x05\x05 if(x>n || y>n)
\x05\x05 {
\x05\x05\x05 count++;
\x05\x05\x05 continue;
\x05\x05 }
\x05\x05 switch(d)
\x05\x05 {
\x05\x05 case 1:
\x05\x05\x05 if(find(x)==find(y)){
\x05\x05\x05\x05 if(r[x]!=r[y])
\x05\x05\x05\x05\x05 count++;
\x05\x05\x05 }
\x05\x05\x05 else
\x05\x05\x05\x05 merge(x,y,0);
\x05\x05\x05 break;
\x05\x05 case 2:
\x05\x05\x05 if(find(x)==find(y) ){
\x05\x05\x05\x05 if(r[x] = (r[y]+1)%3)
\x05\x05\x05\x05\x05 count++;
\x05\x05\x05 }
\x05\x05\x05 else
\x05\x05\x05\x05 merge(x,y,1);
\x05\x05\x05 break;
\x05\x05 }
\x05 }
\x05 cout
动物王国中有三类动物A,B,C,这三类动物的食物链构成了有趣的环形.A吃B,B吃C,C吃A.现有N个动物,以1-N编号.每个动物都是A,B,C中的一种,但是我们并不知道它到底是哪一种.有人用两种说法对这N
您的算法写的不对……
并查集:
三个集合{元素|1~3*n}其中对于任意一个集合,集合中元素(1~n)吃(n+1~2*n),(n+1~2*n)吃(2*n+1~3*n),(2*n+1~3*n)吃(1~n).
对于x和y 是同类.并且x和y不再一个结合的情况下,判断(y+n)、(y+2n)是否和x在一个集合,若都不是,那么(x,y)并成一个集合.(x+n,y+n)并成一个集合.(x+2*n,y+2*n)并成一个集合.
对于x 吃 y.如果x 和 (y+n)不再一个结合的情况下,判断 y、(y+2*n) 是否和 x 是在一个集合,若都不是,那么(x,y+n)并成一个集合.(x+n,y+2*n)并成一个集合.(x+2*n,y)并成一个集合.