题解 P2814 【家谱】
Iowa_BattleShip
2017-09-28 19:25:01
**看我的无敌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;
}
```