POI 2000 Skiers

May 19, 2009 — gnarlycow

贪心策略、深度优先搜索

网络流模型理论上可以解决此题，把除1和n以外的每个结点都拆成两个结点，中间用一条容量为1的边连接，结点1为源，结点n为汇求最大流。无奈本题数据规模较大，最多有5000个结点，而且边数未知。

注意到题目给出的图具有特殊的性质：边是按从东到西的顺序给出的，而且所有边不相交。这样我们可以采取如下贪心策略：用深度优先搜索从结点1出发找一条尽可能靠东（或尽可能靠西）的路径，让一个运动员沿此路径滑雪，把此路径上的除起点和终点外的所有结点从图中删去，然后重复此过程。这个策略显然正确，由于所有边都不相交，每次找最靠东（或最靠西）的路径可以给后面要找的路径腾出最大的空间。

?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

#include <iostream>
 
using namespace std;
 
struct edge
{
	int v;
	edge *next;
	edge(int v,edge *next):v(v),next(next) {}
} *e[5005];
int n;
bool u[5005];
 
bool dfs(int v)
{
	if(v==n) return true;
	u[v]=true;
	for(edge *t=e[v];t;t=t->next)
		if(!u[t->v]&&dfs(t->v))
			return true;
	return false;
}
 
int main()
{
	freopen("nar.in","r",stdin);
	freopen("nar.out","w",stdout);
	scanf("%d",&n);
	int t,v,ans=0;
	for(int i=1;i<n;++i)
		for(scanf("%d",&t);t;--t)
		{
			scanf("%d",&v);
			e[i]=new edge(v,e[i]);
		}
	for(edge *p=e[1];p;p=p->next)
		if(!u[p->v]&&dfs(p->v))
			++ans;
	printf("%d\n",ans);
	return 0;
}
Posted in POI. Tags: , . No Comments »

POI 1999 Water

May 18, 2009 — gnarlycow

优先队列

注意到边界上的格子一定不能存水，否则会流到外面去。现在考虑与边界相邻的格子。注满水后，对于某个与边界相邻的格子来水，它的积水状态只与它自己的恶高度和相邻边界格子的最低高度有关。这样，我们可以取边界格子中高度最低的格子，然后来得到与之相邻的内部格子的水位。假设边界格子中高度最低的为格子(x,y)，那么对于(x,y)的任意一个相邻非边界格子(x’,y’)来说，只要h(x,y)>h(x’,y’)” />，格子(x’,y’)就会有高度为<img src=的积水，这时我们可以把h(x,y)-h(x',y')累加到答案中去，然后把h(x',y')赋为h(x,y)并把(x’,y’)看作边界格子。如果h(x,y)<=h(x',y')，我们可以直接把(x’,y’)看作边界格子。当处理完所有(x,y)的相邻非边界格子后，把(x,y)从边界格子中删去。重复这个过程，直至边界格子集合为空为止。显然，用一个小根堆来维护边界格子集合是在适合不过了。

?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

#include <iostream>
 
using namespace std;
 
const int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
bool u[111][111];
int ans,heapsize,h[111][111];
struct node
{
	int x,y,v;
} heap[11111];
 
void insert(int x,int y,int v)
{
	node key={x,y,v};
	int p=++heapsize;
	while(p>1&&heap[p>>1].v>v)
	{
		heap[p]=heap[p>>1];
		p>>=1;
	}
	heap[p]=key;
}
 
void deleteMin()
{
	int p=1;
	while((p<<1)<heapsize)
	{
		int i=p<<1;
		if(i+1<heapsize&&heap[i+1].v<heap[i].v) ++i;
		if(heap[i].v<heap[heapsize].v)
		{
			heap[p]=heap[i];
			p=i;
		}
		else break;
	}
	heap[p]=heap[heapsize--];
}
 
int main()
{
	freopen("wod.in","r",stdin);
	freopen("wod.out","w",stdout);
	int r,c;
	scanf("%d%d",&r,&c);
	for(int i=0;i<r;++i)
		for(int j=0;j<c;++j)
			scanf("%d",&h[i][j]);
	for(int i=0;i<c;++i)
	{
		u[0][i]=u[r-1][i]=true;
		insert(0,i,h[0][i]);
		insert(r-1,i,h[r-1][i]);
	}
	for(int i=1;i+1<r;++i)
	{
		u[i][0]=u[i][c-1]=true;
		insert(i,0,h[i][0]);
		insert(i,c-1,h[i][c-1]);
	}
	while(heapsize)
	{
		int x=heap[1].x,y=heap[1].y;
		deleteMin();
		for(int i=0;i<4;++i)
		{
			int tx=x+dx[i],ty=y+dy[i];
			if(tx>-1&&tx<r&&ty>-1&&ty<c&&!u[tx][ty])
			{
				u[tx][ty]=true;
				if(h[tx][ty]<h[x][y])
				{
					ans+=h[x][y]-h[tx][ty];
					h[tx][ty]=h[x][y];
				}
				insert(tx,ty,h[tx][ty]);
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}
Posted in POI. Tags: , . No Comments »

POI 2003 Monkeys

May 18, 2009 — gnarlycow

并查集

这是一道很棒的并查集类问题，具有较高的思维难度。注意到题目中所描述的猴子的连接方式，有可能猴子a抓住猴子b的尾巴，也有可能b抓住a的尾巴，也有可能a和b互相抓住对方的尾巴。其实我们只关心两个猴子是否相连，以上三种情况都是猴子a和b相连。现在题目要求的就是每只猴子第一次直接或间接脱离猴子1的时间。看起来好像和并查集的操作是相反的，那我们就反过来求解。首先求出时刻m所有放手行为都执行后猴子们的连接情况，然后从时刻m往前反过来执行“抓尾巴”行为，这样问题转化为求每个猴子第一次直接或间接与猴子1相连的时刻。这正是并查集所支持的操作，只是每次将猴子1所在集合与其它集合合并时，需要把那个集合的所有猴子的答案都设置为这个时刻。我们可以另外对每个集合维护一个链表，包含这个集合的所有猴子，合并时将链表合并。这样总的时间复杂度不变，问题成功解决。

?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

#include <iostream>
 
using namespace std;
 
struct node
{
	int v;
	node *next;
	node(int v,node *next):v(v),next(next) {}
} *first[200002],*last[200002];
int d[400004][2],holdOrig[200002][2],holdCur[200002][2],ans[200002],f[200002];
 
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)
	{
		f[x]=y;
		last[y]->next=first[x];
		last[y]=last[x];
	}
}
 
void uniteAndUpdateAns(int a,int b,int moment)
{
	int x=getRoot(a),y=getRoot(b);
	if(x!=y)
	{
		if(x==getRoot(1))
			for(node *t=first[y];t;t=t->next)
				ans[t->v]=moment;
		else if(y==getRoot(1))
			for(node *t=first[x];t;t=t->next)
				ans[t->v]=moment;
		f[x]=y;
		last[y]->next=first[x];
		last[y]=last[x];
	}
}
 
int main()
{
	int n,m;
	memset(ans,-1,sizeof(ans));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)
	{
		scanf("%d%d",&holdOrig[i][0],&holdOrig[i][1]);
		holdCur[i][0]=holdOrig[i][0];
		holdCur[i][1]=holdOrig[i][1];
	}
	for(int i=0;i<m;++i)
	{
		scanf("%d%d",&d[i][0],&d[i][1]);
		--d[i][1];
		holdCur[d[i][0]][d[i][1]]=-1;
	}
	for(int i=1;i<=n;++i)
	{
		f[i]=i;
		first[i]=last[i]=new node(i,NULL);
	}
	for(int i=1;i<=n;++i)
	{
		if(holdCur[i][0]>-1) unite(i,holdCur[i][0]);
		if(holdCur[i][1]>-1) unite(i,holdCur[i][1]);
	}
	for(int i=m-1;i>-1;--i)
		if(holdOrig[d[i][0]][d[i][1]]>-1)
			uniteAndUpdateAns(d[i][0],holdOrig[d[i][0]][d[i][1]],i);
	for(int i=1;i<=n;++i) printf("%d\n",ans[i]);
	return 0;
}
Posted in POI. Tags: , . No Comments »

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 »

POI 1998 Frogman, SPOJ 181 Scuba diver Summary

March 31, 2009 — gnarlycow

动态规划

本题中的物品涉及两个价值，属于背包问题的简单变形，氧气和氮气各占一维即可。和普通的一维背包问题一样，这里可以通过调整状态转移的顺序来实现空间降维。

?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

#include <cstdio>
#include <cstring>
 
int f[80][80];
 
int main()
{
    int m,n,a,b,w,num,T;
    for(scanf("%d",&T);T;--T)
    {
        memset(f,-1,sizeof(f));
        f[0][0]=0;
        scanf("%d%d%d",&m,&n,&num);
        for(int k=0;k<num;++k)
        {
            scanf("%d%d%d",&a,&b,&w);
            for(int i=79;i>=a;--i)
                for(int j=79;j>=b;--j)
                    if(f[i-a][j-b]>-1&&(f[i][j]==-1||f[i][j]>f[i-a][j-b]+w))
                        f[i][j]=f[i-a][j-b]+w;
        }
        int ans=-1;
        for(int i=m;i<80;++i)
            for(int j=n;j<80;++j)
                if(f[i][j]>-1&&(ans==-1||ans>f[i][j]))
                    ans=f[i][j];
        printf("%d\n",ans);
    }
    return 0;
}
Posted in SPOJ. Tags: , , . No Comments »