POI 1998 Word Equations

May 17, 2009 — gnarlycow

并查集

本题中不同的变量可以表示不同长度的01串，这给解题带来了麻烦。我们可以把所有长度为p的变量拆成p个长度为1的变量，以简化问题。这样，所有拆分后得到的变量都只能表示一个0或1。假设等号两边的长度都为L，如果把0和1本身也看成特殊的变量的话，等式告诉我们的就是L个相等关系，即某两个变量相等。用并查集维护这些相等关系：初始时每个变量自成一个集合，每遇到一个相等关系，把相等的变量所在集合合并。如果某一时刻0和1所在的集合被合并，则说明出现矛盾，输出0；否则，没有矛盾出现，假设最终除0和1所在集合外共有r个集合，则答案为2^{r}。

注意测试数据中存在展开后等式两边长度不等的情况。

?View Code CPP
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

#include <iostream>
 
using namespace std;
 
char s1[10011],s2[10011];
int total,len[33],s[10011],f[10011],size[10011],ans[11111111];
 
int getRoot(int v)
{
	if(f[v]==v) return v;
	else return f[v]=getRoot(f[v]);
}
 
void unite(int a,int b)
{
	int x=getRoot(a),y=getRoot(b);
	if(x!=y)
	{
		if(size[x]<size[y])
		{
			size[x]+=size[y];
			f[y]=x;
		}
		else
		{
			size[y]+=size[x];
			f[x]=y;
		}
		--total;
	}
}
 
int main()
{
	freopen("row.in","r",stdin);
	freopen("row.out","w",stdout);
	int T;
	for(scanf("%d",&T);T;--T)
	{
		int num,l1,l2;
		scanf("%d",&num);
		for(int i=0;i<num;++i) scanf("%d",len+i);
		scanf("%d\n%s\n%d\n%s",&l1,s1,&l2,s2);
		for(int i=1;i<num;++i) len[i]+=len[i-1];
		for(int i=num;i>0;--i) len[i]=len[i-1]+2;
		len[0]=2;
		int top=0;
		for(int i=0;i<l1;++i)
			if(s1[i]>='a'&&s1[i]<='z')
				for(int j=len[s1[i]-'a'];j<len[s1[i]-'a'+1];++j)
					s[top++]=j;
			else s[top++]=s1[i]-'0';
		for(int i=0;i<10005;++i) f[i]=i,size[i]=1;
		int firstTop=top;
		top=0;
		total=len[num]-2;
		for(int i=0;i<l2;++i)
		{
			if(s2[i]>='a'&&s2[i]<='z')
				for(int j=len[s2[i]-'a'];j<len[s2[i]-'a'+1];++j)
					unite(s[top++],j);
			else unite(s[top++],s2[i]-'0');
		}
		if(getRoot(0)==getRoot(1)||top!=firstTop) puts("0");
		else
		{
			memset(ans,0,sizeof(ans));
			int m=1;
			ans[0]=1;
			for(;total;--total)
			{
				int x=0;
				for(int i=0;i<m;++i)
				{
					ans[i]=(ans[i]<<1)+x;
					if(ans[i]>9) x=1,ans[i]-=10;
					else x=0;
				}
				if(x) ans[m++]=1;
			}
			for(int i=m-1;i>=0;--i) putchar('0'+ans[i]);
			putchar('\n');
		}
	}
	return 0;
}
Posted in POI. Tags: , . No Comments »

POI 1999 Three-coloring of Binary Trees

May 17, 2009 — gnarlycow

树型动态规划

首先根据给出的先序遍历序列建树，然后用两遍树型动态规划求出最大和最小值。假设绿色用0表示，1、2表示另外两种颜色。fmax(v,c)表示以v为根的子树中根结点v的颜色为c时的绿色结点数最大值。当v为叶结点时，fmax(v,0)=1而fmax(v,1)=fmax(v,2)=0；当v为非叶结点时，我们要给v的孩子结点分配不同于c的颜色，并在所有方案中去最大值，还有不要忘记当c为0时把根结点v自己加进去。求最小值与之类似，只要把所有的max都变为min即可。

?View Code CPP
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

#include <iostream>
 
using namespace std;
 
int m,p,num[10011],cleft[10011],cright[10011],f[10011][3];
char s[10011];
 
int max(int a,int b,int c)
{
	return max(max(a,b),c);
}
 
int min(int a,int b,int c)
{
	return min(min(a,b),c);
}
 
void buildTree()
{
	num[m]=s[p++]-'0';
	if(num[m]==1)
	{
		cleft[m]=m+1;
		cright[m]=-1;
		++m;
		buildTree();
		return;
	}
	if(num[m]==2)
	{
		int t=m;
		cleft[t]=m+1;
		++m;
		buildTree();
		cright[t]=m;
		buildTree();
		return;
	}
	if(num[m]==0) cleft[m]=cright[m++]=-1;
}
 
int getMax(int v,int c)
{
	if(f[v][c]>-1) return f[v][c];
	int r=(c==0);
	if(num[v]==1) r+=max(getMax(cleft[v],(c+1)%3),getMax(cleft[v],(c+2)%3));
	else if(num[v]==2) r+=max(getMax(cleft[v],(c+1)%3)+getMax(cright[v],(c+2)%3),getMax(cleft[v],(c+2)%3)+getMax(cright[v],(c+1)%3));
	return f[v][c]=r;
}
 
int getMin(int v,int c)
{
	if(f[v][c]>-1) return f[v][c];
	int r=(c==0);
	if(num[v]==1) r+=min(getMin(cleft[v],(c+1)%3),getMin(cleft[v],(c+2)%3));
	else if(num[v]==2) r+=min(getMin(cleft[v],(c+1)%3)+getMin(cright[v],(c+2)%3),getMin(cleft[v],(c+2)%3)+getMin(cright[v],(c+1)%3));
	return f[v][c]=r;
}
 
int main()
{
	freopen("trot.in","r",stdin);
	freopen("trot.out","w",stdout);
	gets(s);
	buildTree();
	memset(f,-1,sizeof(f));
	printf("%d ",max(getMax(0,0),getMax(0,1),getMax(0,2)));
	memset(f,-1,sizeof(f));
	printf("%d\n",min(getMin(0,0),getMin(0,1),getMin(0,2)));
	return 0;
}
Posted in POI. Tags: , , . No Comments »
«
»