USACO DEC08 Gold Summary

February 24, 2009 — gnarlycow

treat
不错的图论基础题。
本题中涉及到的图是一种特殊的有向图：每个结点都有且仅有一条出边。这样的有向图有一个很实用的性质：在每个连通分量中有且仅有一个环，而这个连通分量中的其它结点以树形连接到环上。对于环上的结点来说，题目要我们求的答案就是这个环的长度；而对于非环上的结点来说，答案就是它到环的距离再加上环的长度。这样，很容易想到一个线性算法解决问题。

?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

/*
ID: lipeiqi1
LANG: C++
PROB: treat
*/
#include <cstdio>
#include <cstring>
 
int next[100001],p[100001],ans[100001],mark[100001];
 
int main()
{
	freopen("treat.in","r",stdin);
	freopen("treat.out","w",stdout);
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;++i) scanf("%d",next+i);
	for(int i=1;i<=n;++i)
		if(ans[i]==0)
		{
			int j=i,k=0;
			for(;ans[j]==0;j=next[j])
			{
				mark[j]=k;
				p[k++]=j;
				ans[j]=-1;
			}
			if(ans[j]==-1)
			{
				for(int v=k-1;v>=mark[j];--v) ans[p[v]]=k-mark[j];
				for(int v=mark[j]-1;v>=0;--v) ans[p[v]]=k-v;
			}
			else
				for(int v=k-1;v>=0;--v) ans[p[v]]=ans[j]+k-v;
		}
	for(int i=1;i<=n;++i) printf("%d\n",ans[i]);
	return 0;
}

sec
字符串处理
输入数据给我们两组字符串A和B，我们只要先对A组中的字符串进行适当的预处理，就能快速找出B组中每一个字符串与A中多少个字符串相匹配。对于B组中每一个字符串s来说，我们需要知道A组中有多少个字符串是s的前缀和A组中有多少个字符串以s为前缀，一般情况下这两者之和即为所求结果。有一种特殊情况是A中有与s完全相同的字符串，这时注意不要重复计数。容易想到利用Trie树这种数据结构来解决问题，字典树可以很方便提供我们所需要的功能。

?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

/*
ID: lipeiqi1
LANG: C++
PROB: sec
*/
#include <cstdio>
 
struct node
{
	int end,part;
	node *c[2];
	node():end(0),part(0)
	{
		c[0]=c[1]=NULL;
	}
} *root=new node();
 
int main()
{
	freopen("sec.in","r",stdin);
	freopen("sec.out","w",stdout);
	int m,n,k,v;
	scanf("%d %d",&m,&n);
	for(int i=0;i<m;++i)
	{
		node *t=root;
		for(scanf("%d",&k);k;--k)
		{
			scanf("%d",&v);
			if(!t->c[v]) t->c[v]=new node();
			t=t->c[v];
			++t->part;
		}
		++t->end;
	}
	for(int i=0;i<n;++i)
	{
		node *t=root;
		int ans=0;
		for(scanf("%d",&k);k;--k)
		{
			scanf("%d",&v);
			if(t)
			{
				ans+=t->end;
				t=t->c[v];
			}
		}
		if(t) ans+=t->part;
		printf("%d\n",ans);
	}
	return 0;
}
Posted in Gold Division, USACO. Tags: , , . No Comments »
«
»