USACO NOV08 Gold Summary

February 23, 2009 — gnarlycow

mixup2
动态规划
假设p是n头牛所构成的集合的某个子集，last是p中的某头牛，f[p][last]表示集合p中的牛排队时满足last排在最后时的不同排队方案数。那么f[p][last]等于所有f[p-prev][prev]的和，其中prev为p中的另外一头牛并且满足prev和last两头牛的号码差的绝对值大于K。用二进制实现上述集合操作，时间复杂度O((2^n)*(n^2))。

?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

/*
ID: lipeiqi1
LANG: C++
PROB: mixup2
*/
#include <cstdio>
#include <cstdlib>
 
int limit,d[16];
long long f[1<<16][16];
 
bool check(int a,int b)
{
	return abs(d[a]-d[b])>limit;
}
 
int main()
{
	freopen("mixup2.in","r",stdin);
	freopen("mixup2.out","w",stdout);
	int n;
	scanf("%d %d",&n,&limit);
	for(int i=0;i<n;++i) scanf("%d",d+i);
	for(int i=0;i<n;++i) f[1<<i][i]=1;
	for(int p=0;p<(1<<n);++p)
		for(int i=0;i<n;++i)
			if(p&(1<<i))
				for(int j=0;j<n;++j)
					if((p&(1<<j))&&check(i,j))
						f[p][i]+=f[p-(1<<i)][j];
	long long ans=0;
	for(int i=0;i<n;++i) ans+=f[(1<<n)-1][i];
	printf("%lld\n",ans);
	return 0;
}

cheer
图论，生成树变形
题目要求我们找出一颗生成树，并求出最小遍历代价。先考虑简单一些的问题：假设给定生成树和根，如何计算最小遍历代价。显然从根结点开始按照DFS顺序遍历代价最小，这时每条边都被经过两次，每个非根结点经过的次数等于它的度数，根结点比度数多一次。我们可以发现，如果不考虑根结点多出来的那一次花费，总花费实际上和根结点的选择无关，只和生成树有关。找代价最小的结点作为根结点把多余的那次花费算上，然后考虑找个代价最小的生成树。很容易想到最小生成树，其实这里无非就是多了个点代价而已。每个结点的经过次数等于度数，也就是与之相邻的边的数目，换个角度我们可以把代价放在边上。这样，让所有边的边权变为原来二倍再加上两个端点的代价，问题转化为标准最小生成树问题。

?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

/*
ID: lipeiqi1
LANG: C++
PROB: cheer
*/
#include <iostream>
#include <algorithm>
 
using namespace std;
 
struct edge
{
	int a,b,w;
	bool operator<(const edge &other) const
	{
		return w<other.w;
	}
} e[100001];
int c[10001],f[10001],s[10001];
 
inline int getRoot(int v)
{
	while(f[v]!=v) v=f[v]=f[f[v]];
	return v;
}
 
bool merge(int a,int b)
{
	a=getRoot(a),b=getRoot(b);
	if(a==b) return true;
	if(s[a]<s[b]) s[b]+=s[a],f[a]=b;
	else s[a]+=s[b],f[b]=a;
	return false;
}
 
int main()
{
	freopen("cheer.in","r",stdin);
	freopen("cheer.out","w",stdout);
	int n,p,j=0,ans=INT_MAX;
	scanf("%d%d",&n,&p);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",c+i);
		ans=min(ans,c[i]);
	}
	for(int i=0;i<p;++i)
	{
		scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].w);
		e[i].w=(e[i].w<<1)+c[e[i].a]+c[e[i].b];
	}
	sort(e,e+p);
	for(int i=1;i<=n;++i) f[i]=i;
	for(int i=1;i<n;++i)
	{
		for(;merge(e[j].a,e[j].b);++j);
		ans+=e[j].w;
	}
	printf("%d\n",ans);
	return 0;
}

lites
线段树
本题是线段树的基础题。线段树每个区间除了记录端点等必要信息外，还应根据需要记录一些额外信息，具体到本题就是每个区间中亮着的灯的数目。在取反操作中，如遇整个区间取反，只需在这个区间上加个取反标志，而不必立即修改子区间。为保证正确性，在以后的取反或询问操作中，如果遇到已经标记取反的区间，不要忘记把取反遗传到子区间。

?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

/*
ID: lipeiqi1
LANG: C++
PROB: lites
*/
#include <iostream>
#include <algorithm>
 
using namespace std;
 
int n,sum[2000000];
bool rev[2000000];
 
void modify(int id,int L,int R,int a,int b)
{
	if(L==a&&R==b)
	{
		rev[id]=!rev[id];
		sum[id]=R-L+1-sum[id];
		return;
	}
	int M=(L+R)>>1;
	if(rev[id])
	{
		rev[id]=false;
		rev[id<<1]=!rev[id<<1];
		rev[(id<<1)+1]=!rev[(id<<1)+1];
		sum[id<<1]=M-L+1-sum[id<<1];
		sum[(id<<1)+1]=R-M-sum[(id<<1)+1];
	}
	if(b<=M) modify(id<<1,L,M,a,b);
	else if(a>M) modify((id<<1)+1,M+1,R,a,b);
	else
	{
		modify(id<<1,L,M,a,M);
		modify((id<<1)+1,M+1,R,M+1,b);
	}
	sum[id]=sum[id<<1]+sum[(id<<1)+1];
}
 
int getSum(int id,int L,int R,int a,int b)
{
	if(L==a&&R==b) return sum[id];
	int M=(L+R)>>1;
	if(rev[id])
	{
		rev[id]=false;
		rev[id<<1]=!rev[id<<1];
		rev[(id<<1)+1]=!rev[(id<<1)+1];
		sum[id<<1]=M-L+1-sum[id<<1];
		sum[(id<<1)+1]=R-M-sum[(id<<1)+1];
	}
	if(b<=M) return getSum(id<<1,L,M,a,b);
	else if(a>M) return getSum((id<<1)+1,M+1,R,a,b);
	else return getSum(id<<1,L,M,a,M)+getSum((id<<1)+1,M+1,R,M+1,b);
}
 
int main()
{
	freopen("lites.in","r",stdin);
	freopen("lites.out","w",stdout);
	int m,type,a,b;
	for(scanf("%d%d",&n,&m);m;--m)
	{
		scanf("%d%d%d",&type,&a,&b);
		if(type) printf("%d\n",getSum(1,1,n,a,b));
		else modify(1,1,n,a,b);
	}
	return 0;
}
Posted in Gold Division, USACO. Tags: , , . No Comments »
«
»