Hash乱搞大法好
我先用一个伪随机序列然后每次排序随便判断
每次记录三个哈希值然后进行奇怪的运算就A掉了
怀疑很容易被卡掉。。。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int Smod=999973;
const long long Lmod1=666666666666667ll,Lmod2=233333333333333ll;
int cnt,en,m,h[1000005],H[55],n;
long long rnd[105],sum[105];
struct Hash{
long long lhash1,lhash2;
int next,v;
}ha[10000005];
void AddHash(int s,long long l1,long long l2,int x){
ha[++cnt].lhash1=l1;
ha[cnt].lhash2=l2;
ha[cnt].v=x;
ha[cnt].next=h[s];
h[s]=cnt;
}
int FindHash(int s,long long l1,long long l2){
for(int i=h[s];i;i=ha[i].next){
if(ha[i].lhash1==l1 && ha[i].lhash2==l2)return i;
}
return 0;
}
struct Edge{
int b,next;
}e[1005];
void AddEdge(int sa,int sb){
e[++en].b=sb;
e[en].next=H[sa];
H[sa]=en;
}
void Dfs(int u,int fa){
long long St[105];
int siz=0;
St[++siz]=233;
for(int i=H[u];i;i=e[i].next){
int v=e[i].b;
if(v==fa)continue;
Dfs(v,u);
St[++siz]=sum[v];
}
sort(St+1,St+siz+1);
sum[u]=0;
for(int i=1;i<=siz;i++)sum[u]+=St[i]*rnd[i];
}
int main(){
freopen("4337.in","r",stdin);
freopen("4337.out","w",stdout);
scanf("%d",&m);
rnd[0]=233;
for(int i=1;i<=100;i++)rnd[i]=rnd[i-1]*99973ll+7;
for(int i=1;i<=m;i++){
en=0;
memset(H,0,sizeof(H));
memset(sum,0,sizeof(sum));
scanf("%d",&n);
for(int j=1;j<=n;j++){
int x;
scanf("%d",&x);
if(x){AddEdge(x,j);AddEdge(j,x);}
}
int ans1=0;
long long ans2=0,ans3=77;
for(int j=1;j<=n;j++){Dfs(j,0);ans1=ans1+sum[j];ans2=ans2^sum[j];ans3=ans3*sum[j];}
ans1=max(ans1,-ans1);
ans1=ans1%Smod+7;
int dx=FindHash(ans1,ans2,ans3);
if(!dx){AddHash(ans1,ans2,ans3,i);printf("%d\n",i);}
else printf("%d\n",ha[dx].v);
}
return 0;
}
评论 (0)
