题解【[BJOI2015]树的同构】

切了省选题+紫题，来写个题解

这题其实挺水，才120行代码

该题写了我一天（上午1.5h，晚上10min = 一天）

hash，对于节点A，$$hashval[A] = {hashval[i]\times2333^{num} | i \in son[A] }$$ ，并且hashval[i]大于任何在他前面加的数，num为目前加到第几个

写成代码就是

function Hash(int n){

    vector V ;

    for_each(i in son[n]) do

        HV[i] = Hash(i) ;

        V.pushback(HV[i]) ;

    V.sort()

    for_each(i in V)

        HV[n] = HV[n]*2333+HV[i] ;

    return HV[n]*2333+1002 ;

    //HV[i]初值为1

}

那么对于树中的每个节点做一遍Hash，时间复杂度为$$O(N \times (N+NlogN+N))$$

所以总的的时间复杂度为$$O(M \times N \times NlogN) == O(N^3logN)$$

说人话：$$O(\text{能过})$$

\[\]

Talk is free , show me the code

#include<iostream>

#include<vector>

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std ;

inline void read(int &x) {

    char ch=getchar();

    int s=0,f=1;

    while (!(ch>='0'&&ch<='9')) {

        if (ch=='-') f=-1;

        ch=getchar();

    }

    while (ch>='0'&&ch<='9') {

        s=(s<<3)+(s<<1)+ch-'0';

        ch=getchar();

    }

    x=s*f;

}

class TREE{

	private:

		vector<int> son[55] ;

		int hashval[55] ;

		int H[55] ;

		bool inq[55] ;

		int size[55] ;

		int root ;

		int n ;

		int check(vector<int> N){

			int S = N.size() ;

			for(int j:N) {

				if(inq[j]) --S ;

			}

			return S ;

		}

	public:

                //这个MIAOMIAOMIAO函数就是Hash啦喵~

		int MIAOMIAOMIAO(int n,int f){

			inq[n] = true ;

			vector<int> V ;

			for(const int & i : son[n]){

				if(i==f) continue ;

				//cout<<"dfs in dot "<<i<<endl ;

				hashval[i] = MIAOMIAOMIAO(i,n) ;

				//cout<<"HashVal["<<i<<"] = "<<hashval[i]<<endl ;

				V.push_back(hashval[i]) ;

				//cout<<"HashVal["<<n<<"] = "<<hashval[n]<<endl ;

			}

			sort(V.begin(),V.end()) ;

			for(const int& i : V)

				hashval[n] = hashval[n]*2333 + i ;

			//hashval[n] = 2333*hashval[n] + 1001 ;

			return hashval[n]*2333+1002 ;

		}

		void getsize(int n,int f){

			inq[n] = true ;

			if(!check(son[n])) size[n] = 1 ;

			for(int i:son[n]){

				if(i!=f) getsize(i,n) ;

				size[n] += size[i] ;

			}

		}

		bool comp(const int& a,const int& b){

			return a>b ;

		}

		int sZ() {return this->n ;}

		void init(){

			read(n) ;

			for(int i=1;i<=n;++i){

				int x ;

				read(x) ;

				if(x==0) { root=i ; continue ; }

				son[x].push_back(i) , son[i].push_back(x) ;

			}

			//cout<<"Root = "<<root<<endl ;

			getsize(root,root) ;

			memset(inq,0,sizeof(inq)) ;

			for(int i=1;i<=n;++i){

				sort(son[i].begin() , son[i].end() , [this](int a, int b) -> bool { return size[a] < size[b]; }) ;

			}

			for(int j=1;j<=n;++j) hashval[j] = 1 ;

			for(int i=1;i<=n;++i){

				MIAOMIAOMIAO(i,i) ;

				H[i] = hashval[i] ;

				memset(inq,0,sizeof(inq)) ;

				for(int j=1;j<=n;++j) hashval[j] = 1 ;

			}

			//for(int i=1;i<=n;++i) cout<<H[i]<<" ";

			//cout<<endl ;

		}

		int gethashval(int DI){

			return H[DI] ;

		}

} ;

TREE Index[55] ;

int m ;

int HVL[55] ;

int ans[55][55] ;

int main(){

	read(m) ;

	for(int i=1;i<=m;++i){

		//cout<<"TREE "<<i<<endl ;

		Index[i].init() ;

		HVL[i] = i ;

		int n = Index[i].sZ() ;

		for(int j=1;j<=n;++j){

			ans[i][j] = Index[i].gethashval(j) ;

		}

		sort(ans[i]+1,ans[i]+n+1) ;

		for(int j=1;j<=i;++j){

			int k = 0 ;

			while(k<=n)

				if(ans[i][++k]!=ans[j][k])

					break ;

			if(k>n) { HVL[i] = j ; break ; }

		}

	}

	for(int i=1;i<=m;++i) {

		printf("%d\n",HVL[i]) ;

	}

}

Oh对了

本代码使用C++11标准并对每棵树封装

提交时注意~~（我不会告诉你我因为这个WA了一次喵_）~

还有说下那个for

for(const int& i : vector1) -> 对于每个vector1中的元素i，按vector1中的存放顺序访问

所以这个写起来省力~~（我不会告诉你还可以写for(auto& i:vector1)但是我忘了写喵_）~

巴特西

题解【[BJOI2015]树的同构】

最新文章

热门文章