POJ1635 Subway Tree Systems

题解 算法-哈希
题目链接 编辑文章

题意

用一串 $0/1$ 序列表示一棵树的 $\text{dfs}$ 路径,$0$ 表示远离根节点,$1$ 表示靠近根节点。给出两个序列,判断它们是不是同构的树。

序列长度 $L\le 3000$ 。

题解

对每棵树做 $\text{dfs}$ ,回溯时根据与当前节点相连子树的 $\text{hash}$ 值算出当前子树的 $\text{hash}$ 值,最后比较根节点的 $\text{hash}$ 值即可。

记录 $0$ 的个数 $S_0$ 和 $1$ 的个数 $S_1$ ,如果 $S_0=S_1$ 就表示已经访问过了一棵子树,然后递归求解这个子树即可。

注意访问顺序不同也可能同构,所以应该对子树的 $\text{hash}$ 值进行排序后再计算。

#include<bits/stdc++.h>
#define ha 19260817
#define ull unsigned long long

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

char s[3005];

ull get_hash(int l,int r)
{
    int cnt=0,s0=0,s1=0,st=l,v[(r-l+1)/2+1];
    for (int i=l;i<=r;i++)
    {
        s1+=s[i]=='1';
        s0+=s[i]=='0';
        if (s0!=s1) continue;
        v[++cnt]=get_hash(st+1,i-1);
        st=i+1;
    }
    sort(v+1,v+cnt+1);
    ull ans=1;
    for (int i=1;i<=cnt;i++) ans=ans*ha+v[i];
    return ans;

}

signed main()
{
    int n=read();
    while (n--)
    {
        scanf("%s",s);
        ull a=get_hash(0,strlen(s)-1);
        scanf("%s",s);
        if (get_hash(0,strlen(s)-1)==a) puts("same");
        else puts("different");
    }
    return 0;
}

新评论

称呼不能为空
邮箱格式不合法
网站格式不合法
内容不能为空

第一次提交的评论将在审核后显示。