Description
动物王国中有三类动物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 <= N <= 50,000）和K句话（0 <= K <= 100,000），输出假话的总数。Input
第一行是两个整数N和K，以一个空格分隔。 以下K行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中D表示说法的种类。 若D=1，则表示X和Y是同类。 若D=2，则表示X吃Y。Output
只有一个整数，表示假话的数目。Sample Input
100 7 1 101 1 2 1 2 2 2 3 2 3 3 1 1 3 2 3 1 1 5 5Sample Output
3Source
代码AC情况：
北京POJ：
南阳ACM：
代码<C>：
# include <stdio.h> # define N 150000 int QQ[2][N]; int sum,n,K,xx,yy,T; int FRoot(int QQ[][N],int X);//寻找X个根 void Link(int QQ[][N],int X,int Y);//合并X Y所在的集合 int main(){ for(n=0;n<N;n++) QQ[1][n]=n; //初始化 每一个QQ[i]节点都初始化为根 // freopen("AAA.txt","r",stdin); scanf("%d %d",&n,&K); while(K--){ scanf("%d %d %d",&T,&xx,&yy); xx--;yy--; if(xx<0||xx>=n||yy<0||yy>=n) //如果X Y范围不合法 编号不对 { sum++; continue; } if(T==1)//如果是第一种类型 X Y 为同类 { if(FRoot(QQ,xx)==FRoot(QQ,yy+n)||FRoot(QQ,xx)==FRoot(QQ,yy+2*n))// sum++; else { Link(QQ,xx,yy); Link(QQ,xx+n,yy+n); Link(QQ,xx+2*n,yy+2*n); } } else//如果捕食关系 { if(FRoot(QQ,xx)==FRoot(QQ,yy)||FRoot(QQ,xx)==FRoot(QQ,yy+2*n)) sum++; else { Link(QQ,xx,yy+n); Link(QQ,xx+n,yy+n<<1); Link(QQ,xx+n<<1,yy); } } } printf("%d\n",sum); return 0; } int FRoot(int QQ[][N],int X) { return QQ[1][X]!=X?FRoot(QQ,QQ[1][X]):X; } void Link(int QQ[][N],int X,int Y) { X=FRoot(QQ,X); Y=FRoot(QQ,Y); if(X==Y) return; if(QQ[0][X]<QQ[0][Y]) QQ[1][X]=Y; else { QQ[1][Y]=X; if(QQ[0][X]==QQ[0][Y])QQ[0][X]++; } }/* 题目:有N只动物 编号为1 2 3……N 所有的动物都属于 A B C 中的一种 A B C 这三种 动物 为 A吃B B吃C C吃A 给出信息K条 这些信息有两种 a：X Y属于同一种类 b：X吃Y 这些信息中 有的可能和之前的信息矛盾 有的信息 X Y可能不在给定的范围[1,N]中 这些信息 一旦检测错误 就忽视掉这条信息 输出K条信息中错误的信息的个数 范围 N∈[1,5000] K∈[0,10000] 限制 Time limit 1s EG： T N=100 K=7 | a 1: X=101 Y=1 | 2: X=1 Y=2 | 3: X=2 Y=3 | 4: X=3 Y=3 | 5: X=1 Y=3 | 6: X=3 Y=1 | 7: X=5 Y=5 | 输出3 解: a：X Y属于同一种类 b：X吃Y 输入N=100 K=7 | _____内容______|_______种类_________ 1: X=101 Y=1 | a 2: X=1 Y=2 | b 3: X=2 Y=3 | b 4: X=3 Y=3 | b 5: X=1 Y=3 | a 6: X=3 Y=1 | b 7: X=5 Y=5 | a 输出 3 <1,4,5错> 因为N K很大 必须高效的判断 并维护动物之间的关系 并查集^!^ 并查集的概念 并查集是用来管理元素分组情况的数据结构 可以高效的进行两种操作 1：查询A B两个元素是否在同一组 2：合并A B 两个元素所在的组 优化后的并查集复杂度很低 比O(logN)还要低 并查集 用树形结构实现的 但不是二叉树 确切的说 并查集为多个树 即 森林 如果两个数经若干个父节点 走到了一起 则说明这两个元素是属于同一组否则为不同组 合并A B两个元素所在的组时，将一个元素所在的组的根连接到另一组的根 就完成了合并 不过 如果要维护其复杂度 需要做两个方面的优化 1：对于每棵树记录其高度 合并的时候 高度小的连接到高度高的地方 2：保存记录 每次查询时 向上经过的所有的点 都直接连接到根上 这样就可以放便下次使用 即使输得高度变化的 也无须再改变我们记录的树的高度 下面用数组模拟并查集 int QQ[2][N] QQ[1][i]记录父亲 当QQ[1][X]=X时->X为树所在的根 QQ[0][i]记录树的高度 代码: # include <stdio.h> # define N 100 int FRoot(int QQ[][N],int X);//寻找X个根 void Link(int QQ[][N],int X,int Y);//合并X Y所在的集合 int main(){ int QQ[2][N]={0},i; for(i=0;i<N;i++) QQ[1][i]=i;//初始化 每一个QQ[i]节点都为根 return 0; } int FRoot(int QQ[][N],int X) { return QQ[1][X]!=X?FRoot(QQ,QQ[1][X]):X; } void Link(int QQ[][N],int X,int Y) { X=FRoot(QQ,X); Y=FRoot(QQ,Y); if(X==Y)return; if(QQ[0][X]<QQ[0][Y]) QQ[1][X]=Y; else { QQ[1][Y]=X; if(QQ[0][X]==QQ[0][Y]) QQ[0][X]++; } } 回到题目: 对于每个动物i创建3个元素 i-A,i-B,i-C; 并用这三个元素创建并查集 i-X 表示 i属于种类X 并查集的每一组元素都是 全发生或者不发生 for example ： 如果i-A j-B在同一个组 就表示 如果i属于A 则j一定属于B 就表示 如果j属于B 则i一定属于A 因此对于每一个信息 只需做以下操作 第一种a：X Y同类 合并X-A,Y-A X-B,Y-B X-C,Y-C; 第二种b: X吃Y 合并X-A,Y-B X-B,Y-C X-C,Y-A。 在合并之前 要判断合并是否会产生矛盾 代码： int QQ[2][3*N] 0----N N+1----2*N 2*N+1-----3*N 这三段表示 A B C三个组 */ # include <stdio.h> # define N 15000 # define MAXK 10000 int FRoot(int QQ[][N],int X);//寻找X个根 void Link(int QQ[][N],int X,int Y);//合并X Y所在的集合 int main(){ int QQ[2][N]={0},T[MAXK]={0},A[MAXK]={0},B[MAXK]={0}; int i,sum=0,n,K,xx,yy,Flag[N/3]={0}; for(i=0;i<N;i++) QQ[1][i]=i; //初始化 每一个QQ[i]节点都初始化为根 scanf("%d %d",&n,&K); for(i=0;i<K;i++) { scanf("%d %d %d",&T[i],&A[i],&B[i]); xx=A[i]-1; //和数组对应 yy=B[i]-1; if(xx<0||xx>=n||yy<0||yy>=n) //如果X Y范围不合法 编号不对 { Flag[sum++]=i+1; continue; } if(T[i]==1)//如果是第一种类型 X Y 为同类 { if(FRoot(QQ,xx)==FRoot(QQ,yy+n)||FRoot(QQ,xx)==FRoot(QQ,yy+2*n))// Flag[sum++]=i+1; else { Link(QQ,xx,yy); Link(QQ,xx+n,yy+n); Link(QQ,xx+2*n,yy+2*n); } } else//如果捕食关系 { if(FRoot(QQ,xx)==FRoot(QQ,yy)||FRoot(QQ,xx)==FRoot(QQ,yy+2*n)) Flag[sum++]=i+1; else { Link(QQ,xx,yy+n); Link(QQ,xx+n,yy+2*n); Link(QQ,xx+2*n,yy); } } } printf("一共有%d处信息错误\n错误的信息编号:",sum); for(i=0;i<sum;i++) printf(" %d ",Flag[i]); return 0; } int FRoot(int QQ[][N],int X) { return QQ[1][X]!=X?FRoot(QQ,QQ[1][X]):X; } void Link(int QQ[][N],int X,int Y) { X=FRoot(QQ,X); Y=FRoot(QQ,Y); if(X==Y) return; if(QQ[0][X]<QQ[0][Y]) QQ[1][X]=Y; else { QQ[1][Y]=X; if(QQ[0][X]==QQ[0][Y]) QQ[0][X]++; } } /* 给定长度为N的字符串S 要构造一个长度为N的字符串T。起初，T是一个空串 随后反复进行如下操作 1：从S的头部删除一个字符串，加到T的末尾 2:从S的尾部删除一个字符串 将其加到T的末尾 其要求就是构造字典序尽可能小的字符串 例如 S="ACDBCB" 》 S="CDBCB" 》 S=""S="CDBC" 》 S="CDB" 》S="CD" 》S="D" 》S="" T="" 》T="A" 》T="AB" 》T="ABC" 》T="ABCB" 》T="ABCBC" 》T="ABCBCD" 以上过程中 T得到了ABC BCD 两组字典序 且是最小的字典序组 以上过程可以看出 S在选择进入T中的过程中 总是比较S的开头和末尾的较小的字符串放到T末尾 但是对于S的开头和末尾相同的情形还没有定义 在这种情况下 我们需要继续比较 S的第二位 与倒数第二位 如果相同继续比较 直到两者相遇之前如果能比较出来则直接比较 如果两者相也是相同的 则哪边都可以 贪心算法的代码长的不多 但是里面的思想却很重要 */ # include <stdio.h> void ZIDIAN(char S[],char T[]); # define N 100 int main(){ char S[N],T[N]={"\0"}; gets(S); ZIDIAN(S,T); printf("%s",T); return 0; } void ZIDIAN(char S[],char T[]) { int i=0,A=0,B=-1,Flag=0,k=0; while(S[(++B)+1]);//求S的字符串长度-1 while(A<=B) { while(S[A+i]==S[B-i])i++; T[k++]=(S[A+i]<S[B-i]?S[A++]:S[B--]); i=0; } }
