NKOJ 3458 （POJ 1635）地铁系统 （树哈希）

发表于 |
字数统计: 791字 | 阅读时长 ≈ 3min

P3458地铁系统

问题描述

一些大城市的地铁线路呈一棵树状，一条树枝就是一条双向地铁道路，它直接连接两个站点。任意两个站点间，有且仅有一条路径可以到达。
大多数这样的城市都有一个中央地铁站，你是一个地铁迷，假设你现在就在一座这样的城市，你想要探索所有的地铁站。你从中央地铁站出发，随机选了一条地铁线就出发了。每到一个地铁站，你都会选一条没走过的道路继续乘地铁旅行。如果当前你所在的地铁站连接的所有道路你都探索过了，那么你会回到上一个车站，继续探索，直到你探索玩所有地铁站，也就是每条道路来回走过两次（其实就是深度优先搜索遍历一棵树的过程）。那时，你会身处中央车站，你凭记忆写下了一串由0和1构成的数字，来表示整个旅行的过程，其中0表示你离中央车站远了一点，1表示你离中央车站近了一点(0表示向下搜索，1表示回溯)。
这里写图片描述
如上图所示，中间的大黑圆点表示中央车站，从它出法，遍历整棵树的顺序可以有很多种，右侧给出了其中的3中顺序。它们都表示遍历同一棵树。
你的记事本上记下了两次探索过程，问这两次探索的是否是相同的地铁系统？

输入格式

两行，每行一个由0和1构成的字符串，字符串的长度不超过3000.

输出格式

如果两个字符串表示的是相同的地铁系统，输出“same”，否则输出”different”

样例输入

样例1：
0010011101001011
0100011011001011
样例2：
0100101100100111
0011000111010101

样例输出

样例1：
same
样例2：
different

用栈模拟递归过程来连边，连完边之后直接树哈希。

关于树哈希，这道题我用的是，令父亲节点的哈希值为

$Hash[fa]=(a\times p \bigoplus Hash[son_1] ) \% q\times p\bigoplus Hash[son_2] \% q……\times b \% q$

递归计算即可。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#define N 5005
using namespace std;
const int a=233;
const int p=1223;
const int mod=1000007;
const int b=1926;
int T,S[N],top,tot;
vector<int>to[N];
char s[N];
int Hash(int x)
{
	int i,y,ans=a;
	vector<int>tmp;
	if(!to[x].size())return 1;
	for(i=0;i<to[x].size();i++)tmp.push_back(Hash(to[x][i]));
	sort(tmp.begin(),tmp.end());
	for(i=0;i<tmp.size();i++)ans=(ans*p^tmp[i])%mod;
	return ans*b%mod;
}
int Work()
{
	int i,j,k,l=strlen(s);
	S[top=1]=tot=1;
	to[1].clear();
	for(i=0;i<l;i++)
	{
		if(s[i]=='0')
		{
			to[S[top]].push_back(++tot);
			S[++top]=tot;to[tot].clear();
		}
		else top--;
	}
	return Hash(1);
}
int main()
{
	int x,y;
	scanf("%d",&T);
	while(T--)
	{
		scanf("\n%s",s);x=Work();
		scanf("\n%s",s);y=Work();
		if(x==y)puts("same");
		else puts("different");
	}
}