首页 / 算法 / 洛谷P5018 对称二叉树——hash

洛谷P5018 对称二叉树——hash

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了洛谷P5018 对称二叉树——hash，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1234字，纯文字阅读大概需要2分钟。

内容图文

给一手链接 https://www.luogu.com.cn/problem/P5018

这道题其实就是用hash水过去的，我们维护两个hash

一个是先左子树后右子树的h1

一个是先右子树后左子树的h2

如果一个点，他的左子树的h1==右子树的h2

那么以这个点为根的树就是对称二叉树了

TIPS：hash的顺序至关重要！

技术分享图片 技术分享图片 
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<iostream>
#define LL long long
usingnamespace std;
constint M=2e6+7,mod=19260817;
int read(){
    int ans=0,f=1,c=getchar();
    while(c<‘0‘||c>‘9‘){if(c==‘-‘) f=-1; c=getchar();}
    while(c>=‘0‘&&c<=‘9‘){ans=ans*10+(c-‘0‘); c=getchar();}
    return ans*f;
}
int n,ans=1;
int l[M],r[M],h[M];
LL v1[M],v2[M];
void dfs(int x){
    if(l[x]!=-1){
        dfs(l[x]); h[x]+=h[l[x]];
        v1[x]=(v1[x]*2333+v1[l[x]]*233)%mod;
    }
    if(r[x]!=-1){
        dfs(r[x]); h[x]+=h[r[x]]; 
        v1[x]=(v1[x]*2333+v1[r[x]]*1007)%mod;
        v2[x]=(v2[x]*2333+v2[r[x]]*233)%mod;
    }
    if(l[x]!=-1) v2[x]=(v2[x]*2333+v2[l[x]]*1007)%mod;
    if(l[x]!=-1&&r[x]!=-1&&v1[l[x]]==v2[r[x]]) ans=max(ans,h[x]);
}
int main(){
    //freopen("1.txt","r",stdin);
    n=read();
    for(int i=1;i<=n;i++) h[i]=1,v1[i]=read(),v2[i]=v1[i];
    for(int i=1;i<=n;i++) l[i]=read(),r[i]=read();
    dfs(1); 
    printf("%d\n",ans);
    return0;
}
View Code

 

原文：https://www.cnblogs.com/yourinA/p/12000315.html

内容总结

以上是互联网集市为您收集整理的洛谷P5018 对称二叉树——hash全部内容，希望文章能够帮你解决洛谷P5018 对称二叉树——hash所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1065469.html

来源：【匿名】