题解 P2814 【家谱】

Iowa_BattleShip

2017-09-28 19:25:01

Solution

**看我的无敌0ms代码(不用map!!!)** 用map映射是很方便,但我忘记怎么用了= =,所以就试了个不用map的代码,原本后面两个点是超时的,但突然发现这个搜索的循环可以分开循环,因为一般情况是在要搜的人的上面,所以先往上搜,没有再搜下面,然后竟然0ms够了(233) ```cpp #include<iostream> #include<cstdio> using namespace std; int a[50010];//并查集的记录父亲点 char b[50010][10]; int find(int o) { while(a[o]!=o)//并查集的找父亲,因为我是一个一个记录上来的,然后就懒得用压缩路径了(反正0ms,AC就好233) o=a[o]; return o; } int main() { int i,j,n=0,s=0,k,p,u=0,l; while(1) { n++; scanf("%s",&b[n]);//b[n][0]储存类型('+','$','?','#'),后面储存人名 if(b[n][0]=='$') break; if(b[n][0]=='?') { if(u==0) l=n-1;//l记录一共输入的人名个数 if(u==0) for(k=1;k<=l;k++)//开始一个一个搜过去 { p=0; if(b[k][0]=='#') { for(j=k;j>=1;j--)//二分for循环,因为一般情况在上面,但有些特殊的在下面,这个可以减时间 { s=0; if(b[j][0]=='+') { for(u=1;u<=6;u++) if(b[k][u]==b[j][u]) s++; if(s==6) { a[k]=j;//把搜到的人名对应上,就是扔到一个集合里 p=1; break; } } } if(p!=1) for(j=k;j<=l;j++)//如果上面没搜到就往下搜 { s=0; if(b[j][0]=='+') { for(u=1;u<=6;u++) if(b[k][u]==b[j][u]) s++; if(s==6) { a[k]=j;//同上 break; } } } } u=1; } p=0; for(i=l;i>=1;i--)//从下往上搜问的人名 { s=0; if(p==1) break; for(j=1;j<=6;j++) if(b[n][j]==b[i][j]) { s++; if(s==6) { p=1; k=i; break; } } } for(i=1;i<=6;i++) printf("%c",b[n][i]); printf(" "); for(i=1;i<=6;i++) printf("%c",b[find(k)][i]); printf("\n"); } a[n]=n;//一边输入一般初始化并查集 if(b[n][0]=='+')//把儿子和父亲对应起来 for(j=n;j>=1;j--) if(b[j][0]=='#') { a[n]=j;//并查集 break; } } return 0; } ```