TopCoder SRM 432 Summary

March 9, 2009 — gnarlycow

LampsGrid
枚举(思维难度大)
每次操作改变一整列的状态，所以如果初始时某两行状态相同，那么经过任意次操作后这两行的状态仍然相同；如果初始时某两行状态不相同，那么经过任意次操作后这两行的状态仍然不相同。枚举每一行，考虑能否把它通过K次操作变为全亮，如果能的话再数一数有多少行和这一行初始状态相同，它们也能通过同样的K次操作变为全亮。找出能变为全亮的且与之状态相同的行数最多的行即可。

?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

#include <cmath>
#include <ctime>
#include <iostream>
#include <sstream>
#include <map>
#include <algorithm>
#include <string>
#include <vector>
 
using namespace std;
 
class LampsGrid
{
public:
	int mostLit(vector <string> initial, int K)
	{
		int ans=0;
		for(int i=0;i<initial.size();++i)
		{
			int num=0;
			for(int j=0;j<initial[i].size();++j) num+=initial[i][j]=='0';
			if(num>K||(K-num)%2) continue;
			num=0;
			for(int j=0;j<initial.size();++j) num+=initial[i]==initial[j];
			ans=max(ans,num);
		}
		return ans;
	}
};
Posted in SRM, TopCoder, Uncategorized. Tags: , . No Comments »

OI Summary Bird’s-eye View

March 8, 2009 — gnarlycow

TopCoder

SRM435 (完成度2/3，第三题待实现)

SRM433 (完成度2/3，第三题待实现)

SRM432 (完成度1/3，第二题待思考，第三题待实现)

SRM431 (完成度2/3，第三题待思考)

SRM429 (完成度3/3，DONE!)

USACO Contest

FEB09 Gold (完成度3/3，DONE!)

JAN09 Gold (完成度3/3，DONE!)

Posted in General. Tags: , . No Comments »

CQTSC2009 Summary

March 4, 2009 — gnarlycow

中位数(median)
简单统计题

?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

#include <cstdio>
 
const int BASE=100000;
int d[100001],f[100001],h[200002];
 
int main()
{
	freopen("median.in","r",stdin);
	freopen("median.out","w",stdout);
	int n,b,s;
	scanf("%d%d",&n,&b);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",d+i);
		if(d[i]==b) s=i;
	}
	h[BASE]=1;
	for(int i=s-1;i;--i)
	{
		if(d[i]>d[s]) f[i]=f[i+1]+1;
		else f[i]=f[i+1]-1;
		++h[BASE+f[i]];
	}
	int ans=h[BASE];
	for(int i=s+1;i<=n;++i)
	{
		if(d[i]>d[s]) f[i]=f[i-1]+1;
		else f[i]=f[i-1]-1;
		ans+=h[BASE-f[i]];
	}
	printf("%d\n",ans);
	return 0;
}

跳舞(dance)
二分答案+网络流
经典的拆点构图模型，这里不加说明地直接给出构图方法：将每个人都拆成两个点，分别表示喜欢和不喜欢。从源向每个男喜欢连一条边，容量为二分枚举的曲子数。每个男孩从喜欢向不喜欢连一条容量为k的边，每个女孩从不喜欢向喜欢连一条容量为k的边。从每个女喜欢向汇连一条为容量为二分枚举的曲子数的边。对于每对相互喜欢的男女，从男喜欢向女喜欢连一条为容量为1的边；对于相互不喜欢的男女，从男不喜欢向女不喜欢连一条为容量为1的边。如果最大流恰为此时枚举的曲子数的n倍则可行。

?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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136

#include <iostream>
 
using namespace std;
 
const int MAXNODE=444,MAXEDGE=30000;
struct network
{
	int S,T,len;
	int v[MAXEDGE],capacity[MAXEDGE],flow[MAXEDGE],head[MAXNODE],next[MAXEDGE];
	void initialize();
	void insertEdge(int,int,int);
	bool makeLevelGraph();
	bool changeFlow(int,int);
	void makeMaxFlow();
	int getMaxFlow();
} g;
int q[MAXNODE],h[MAXNODE],cur[MAXNODE],mark[MAXNODE];
bool used[MAXNODE],flag[MAXNODE];
char fancy[55][55];
 
void network::initialize()
{
	len=0;
	memset(head,0,sizeof(head));
	memset(flow,0,sizeof(flow));
	next[0]=0;
}
 
void network::insertEdge(int a,int b,int c)
{
	len++;
	v[len]=b;
	capacity[len]=c;
	next[len]=head[a];
	head[a]=len;
	len++;
	v[len]=a;
	capacity[len]=0;
	next[len]=head[b];
	head[b]=len;
}
 
bool network::makeLevelGraph()
{
	memset(h,0,sizeof(h));
	memset(used,false,sizeof(used));
	used[S]=true;
	q[0]=S;
	for(int headQ=0,tailQ=1;headQ<tailQ;++headQ)
		for(int i=head[q[headQ]];i;i=next[i])
			if(capacity[i]>flow[i]&&!used[v[i]])
			{
				h[v[i]]=h[q[headQ]]+1;
				if(v[i]==T) return true;
				used[v[i]]=true;
				q[tailQ++]=v[i];
			}
	return false;
}
 
inline bool network::changeFlow(int k,int w)
{
	if(k&1) flow[k+1]-=w;
	else flow[k-1]-=w;
	return (flow[k]+=w)==capacity[k];
}
 
void network::makeMaxFlow()
{
	while(makeLevelGraph())
	{
		memcpy(cur,head,sizeof(head));
		memset(used,false,sizeof(used));
		q[0]=cur[S]+1;
		for(int num=0;!used[S];)
			if(v[q[num]]==T)
			{
				int delta=INT_MAX;
				for(int i=1;i<=num;i++) delta<?=capacity[q[i]]-flow[q[i]];
				for(int i=num;i;--i)
					if(changeFlow(q[i],delta))
						num=i-1;
			}
			else
			{
				int &i=cur[v[q[num]]];
				for(;i;i=next[i])
					if(!used[v[i]]&&h[v[i]]==h[v[q[num]]]+1&&capacity[i]>flow[i])
					{
						q[++num]=i;
						break;
					}
				if(!i) used[v[q[num--]]]=true;
			}
	}
}
 
int network::getMaxFlow()
{
	makeMaxFlow();
	int res=0;
	for(int i=head[S];i;i=next[i]) res+=flow[i];
	return res;
}
 
int main()
{
	freopen("dance.in","r",stdin);
	freopen("dance.out","w",stdout);
	int n,k;
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;++i) scanf("\n%s",&fancy[i][1]);
	int L=0,R=n+1;
	while(L+1<R)
	{
		int M=(L+R)>>1;
		g.initialize();
		g.S=0;
		g.T=4*n+1;
		for(int i=1;i<=n;++i)
		{
			g.insertEdge(g.S,i,M);
			g.insertEdge(3*n+i,g.T,M);
			g.insertEdge(i,n+i,k);
			g.insertEdge(2*n+i,3*n+i,k);
		}
		for(int i=1;i<=n;++i)
			for(int j=1;j<=n;++j)
				if(fancy[i][j]=='Y') g.insertEdge(i,3*n+j,1);
				else g.insertEdge(n+i,2*n+j,1);
		if(g.getMaxFlow()==M*n) L=M;
		else R=M;
	}
	printf("%d\n",L);
	return 0;
}
Posted in 省选. Tags: , , . No Comments »

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 »

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 »

[IPSC 2008](I. Inventing Test Data) Summary

February 20, 2009 — gnarlycow

Inventing Test Data
图论
完全图中任意两个结点间都有边，为方便起见我们把属于生成树的边称为树边，其它的边称为余边，用w(a,b)表示边(a,b)的权。我们的任务是给所有余边的赋予尽可能小的权，使得给定的生成树为完全图的唯一最小生成树。考虑某条余边(a,b)，(a,b)显然不属于生成树。对于a、b在生成树中的路径path(a,b)上的任意一条边(u,v)，一定有w(u,v)=w(a,b)，那么将(u,v)从生成树中删去，再将(a,b)加入生成树会形成合法的生成树，并且新生成树的所有边劝和不会大于给定生成树，这与原生成树为唯一最小生成树矛盾。这样我们得到结论：所有余边(a,b)的权一定大于生成树中连接(a,b)的路径上每条边的权。类似的，容易证明这个结论的逆命题成立。现在思路已经很清晰了：对于每个余边(a,b)，为它赋予生成树中连接a与b的路径上最大边权值加一，即满足条件的最小权值。借助初始化，这个算法朴素实现的时间复杂度为O(n2)，显然不能满足要求。
我们可以模仿Kruskal算法来得到一个时间复杂度为O(nlogn)的算法。初始时把所有边都去掉，每个结点独为一个连通分量，然后按照边权从小到大的顺序处理输入数据给出的生成树的每一条边，这个过程中不必像Kruskal算法那样判断是否产生环，因为本题中我们所处理的边本身就形成生成树。这样所处理的每条边(a,b)一定连接两个不同的连通分量p、q，由于我们是按照边权从小到大的顺序处理的，因此w(a,b)一定大于任何p或q中边的权，所有的余边(u,v)(u属于p且v属于q)都应该被赋予权值w(a,b)+1。借助并查集，很容易维护所有连通分量之间的关系。这个O(nlogn)的算法常数较小，完全可以承受极限数据。

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12

#include 
 
using namespace std;
 
const int MAXN=100001;
int father[MAXN],size[MAXN];
struct edge
{
	int a,b,w;
	bool operator&lt;(const edge &amp;other) const
	{
		return w
Posted in IPSC. Tags: , . No Comments »

USACO FEB09 Gold Summary

February 18, 2009 — gnarlycow

shuttle
贪心
本题看似动态规划题，但实际上存在如下贪心策略：将所有区间按照终点排序，优先让终点靠前的牛上车。直观上看，我们只需要让尽可能多的牛乘车，而不关心具体哪些牛乘车，让路途远的牛乘车和路途近的牛乘车对于我们来说是一样的。这样，终点靠前意味着早下车，可以让出座位留给后面的牛。本题数据量较大，可能需要借助一些高级数据结构来实现空座维护过程。

?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

/*
ID: lipeiqi1
LANG: C++
PROB: shuttle
*/
#include <iostream>
#include <algorithm>
#include <map>
 
using namespace std;
 
struct segment
{
	int s,e,m;
	bool operator<(const segment &other) const
	{
		return s<other.s;
	}
} d[50005];
 
int main()
{
	freopen("shuttle.in","r",stdin);
	freopen("shuttle.out","w",stdout);
	int k,n,c,ans=0,cur=0;
	map <int,int> h;
	scanf("%d %d %d",&k,&n,&c);
	for(int i=0;i<k;++i) scanf("%d %d %d",&d[i].s,&d[i].e,&d[i].m);
	sort(d,d+k);
	for(int i=0;i<k;++i)
	{
		for(map <int,int>::iterator t=h.begin();t!=h.end()&&t->first<=d[i].s;h.erase(t++))
		{
			ans+=t->second;
			cur-=t->second;
		}
		h[d[i].e]+=d[i].m;
		cur+=d[i].m;
		map <int,int>::iterator t=h.end();
		for(--t;cur>c;)
			if(cur-t->second>c)
			{
				cur-=t->second;
				h.erase(t--);
			}
			else
			{
				t->second-=cur-c;
				cur=c;
			}
	}
	printf("%d\n",ans+cur);
	return 0;
}

stock
贪心+动态规划
在第3天购买某种股票然后在第5天卖，可以看成第3天购买，第4天卖出，第4天再购买，第5天再卖出。我们只关心低价购买，高价卖出，而股票的获利于你持股的时间没有关系，每天的买卖也没有限制，因此我们可以依次考虑每相邻的两天我们如何购买前一天的股票然后在后一天全部卖出。这样我们得到一个贪心算法，依次考虑每相邻两天，前一天买入后一天全部卖出所能得到的最大收益，而这正是个简单的背包问题：股票就是物品，花费就是前一天的价格，收益就是后一天的价格，背包就是资金。

?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++
PROG: stock
*/
#include <iostream>
 
using namespace std;
 
int p[55][11],f[500005];
 
int main()
{
    freopen("stock.in","r",stdin);
    freopen("stock.out","w",stdout);
    int s,d,m;
    scanf("%d %d %d",&s,&d,&m);
    for(int i=0;i<s;++i)
        for(int j=0;j<d;++j)
            scanf("%d",&p[i][j]);
    for(int i=1;i<d;++i)
    {
        for(int j=0;j<=m;++j) f[j]=j;
		for(int j=0;j<s;++j)
			if(p[j][i]>p[j][i-1])
			{
				int prev=p[j][i-1],curr=p[j][i];
				for(int k=prev;k<=m;++k)
				{
					int t=f[k-prev]+curr;
					if(t>f[k]) f[k]=t;
				}
			}
		m=f[m];
    }
    printf("%d\n",m);
    return 0;
}

revamp
图论
按照如下方法构造新图：新图中结点用有序数对(i,j)表示，其中1<=i<=n且0<=j<=k。对于原图中的无向边(a,b)，在新图中加入(a,u)与(b,u)之间的无向边(0<=u<=k)，加入(a,u)与(b,u+1)之间的权为０的无向边(0<=u<k)。除此之外，对于所有的u(0<=u<k)加入(a,u)与(a,u+1)之间权为0的无向边。显然新图中点(1,0)到(n,k)的最短路径就是所求答案。我们可以使用Dijkstra和堆来快速求最短路径。

?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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102

/*
ID: lipeiqi1
LANG: C++
PROG: revamp
*/
#include <cstdio>
#include <cstring>
 
const int MAX_NODE_NUM=210012;
struct edge
{
	int v,w;
	edge *next;
	edge(int v,int w,edge *next):v(v),w(w),next(next) {}
} *e[10001];
struct THeap
{
	int v,d;
} heap[MAX_NODE_NUM];
int heapsize,k,n,pos[MAX_NODE_NUM];
 
void heapInit()
{
	heapsize=0;
	memset(pos,0,sizeof(pos));
}
 
void downMaintain(int k)
{
	int i=k;
	THeap x=heap[k];
	for(int j=k<<1;j<=heapsize;)
	{
		if(j<heapsize&&heap[j].d>heap[j+1].d) j++;
		if(x.d<=heap[j].d) break;
		heap[i]=heap[j];
		pos[heap[j].v]=i;
		i=j;
		j=i<<1;
	}
	heap[i]=x;
	pos[heap[i].v]=i;
}
 
void heapUpdate(int v,int dis)
{
	int i=pos[v];
	if(i&&heap[i].d<=dis) return;
	if(!i) i=++heapsize;
	for(;i!=1&&dis<heap[i>>1].d;i>>=1) heap[i]=heap[i>>1],pos[heap[i>>1].v]=i;
	heap[i].v=v;
	heap[i].d=dis;
	pos[v]=i;
}
 
void deleteMin()
{
	pos[heap[1].v]=0;
	heap[1]=heap[heapsize--];
	downMaintain(1);
}
 
int dijkstra(int vstart)
{
	bool visited[MAX_NODE_NUM]={false};
	int pv,pdis,vend=n*(k+1);
	heapInit();
	heapUpdate(vstart,0);
	for(int i=0;i<vend;i++)
	{
		do
		{
			pv=heap[1].v,pdis=heap[1].d;
			deleteMin();
		} while(visited[pv]);
		if(pv==vend) return pdis;
		visited[pv]=true;
		int comp=(pv-1)/n;
		for(edge *t=e[pv-n*comp];t;t=t->next)
		{
			if(!visited[t->v+n*comp]) heapUpdate(t->v+n*comp,pdis+t->w);
			if(comp<k&&!visited[t->v+n*(comp+1)]) heapUpdate(t->v+n*(comp+1),pdis);
		}
		if(comp<k&&!visited[pv+n]) heapUpdate(pv+n,pdis);
	}
}
 
int main()
{
	freopen("revamp.in","r",stdin);
	freopen("revamp.out","w",stdout);
	int m,a,b,w;
	scanf("%d %d %d",&n,&m,&k);
	for(int i=0;i<m;++i)
	{
		scanf("%d %d %d",&a,&b,&w);
		e[a]=new edge(b,w,e[a]);
		e[b]=new edge(a,w,e[b]);
	}
	printf("%d\n",dijkstra(1));
	return 0;
}
Posted in Gold Division, USACO. Tags: , , . 3 Comments »

TopCoder SRM 435 Summary

February 14, 2009 — gnarlycow

CellRemoval
简单题

?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

#include <iostream>
#include <cmath>
#include <ctime>
#include <string>
#include <sstream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <map>
#include <algorithm>
#include <vector>
 
using namespace std;
 
int c[55][55],num[55];
 
void dfs(int v)
{
	if(c[v][0]==0)
	{
		num[v]=1;
		return;
	}
	dfs(c[v][1]);
	dfs(c[v][2]);
	num[v]=num[c[v][1]]+num[c[v][2]];
}
 
class CellRemoval
{
public:
    int cellsLeft(vector <int> parent, int deletedCell)
    {
		memset(c,0,sizeof(c));
		memset(num,0,sizeof(num));
		int n=parent.size();
		int root=-1;
		for(int i=0;i<n;++i)
			if(parent[i]==-1) root=i;
			else c[parent[i]][++c[parent[i]][0]]=i;
		dfs(root);
		return num[root]-num[deletedCell];
    }
};

DNADeletion
本题难度比通常的Division1 500要大。num[i]表示前i个字符构成的字符串一定要用上最后一个字符时的答案数目，初始时num[0]=1。每个氨基酸可能对应多个“三碱基”，而我们在递推时，要尽可能用前面的碱基，这样能使后面的碱基得到充分利用，得到更长的蛋白质，还可以避免重复。把所有的num值加在一起，去掉空蛋白质的情况就可得到正确结果。

?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

#include <iostream>
#include <cmath>
#include <ctime>
#include <string>
#include <sstream>
#include <cstdlib>
#include <cstdio>
#include <map>
#include <climits>
#include <cstring>
#include <algorithm>
#include <vector>
 
using namespace std;
 
int next[3333][4],num[3333];
 
class DNADeletion
{
public:
    int differentProteins(vector <string> DNASequence, vector <string> codonTable)
    {
		const string S="AGCT";
		const int M=1000000007;
		string s,t,str;
		int n=codonTable.size();
		map <string,vector<vector<int> > > d;
		for(int i=0;i<DNASequence.size();++i) str+=DNASequence[i];
		for(int i=0;i<n;++i)
		{
			istringstream sin(codonTable[i]);
			sin>>s>>t;
			vector <int> m;
			for(int j=0;j<3;++j) m.push_back(S.find(s[j]));
			d[t].push_back(m);
		}
		int len=str.size();
		for(int i=0;i<4;++i) next[len][i]=-2;
		for(int i=len-1;i>=0;--i)
		{
			for(int j=0;j<4;++j) next[i][j]=next[i+1][j];
			next[i][S.find(str[i])]=i;
		}
		memset(num,0,sizeof(num));
		num[0]=1;
		for(int i=0;i<len;++i)
			for(map<string,vector<vector<int> > >::iterator it=d.begin();it!=d.end();++it)
			{
				int minP=INT_MAX;
				for(int j=0;j<it->second.size();++j)
				{
					int p=i;
					for(int k=0;k<3&&p>-1;++k) p=next[p][it->second[j][k]]+1;
					if(p>-1) minP=min(minP,p);
				}
				if(minP!=INT_MAX) num[minP]=(num[minP]+num[i])%M;
			}
		int ans=0;
		for(int i=1;i<=len;++i) ans=(ans+num[i])%M;
		return ans;
    }
};
Posted in SRM, TopCoder. Tags: , , . No Comments »

TopCoder SRM433 Summary

February 11, 2009 — gnarlycow

MagicWords
枚举+优化
如果直接枚举全排列，然后朴素判断拼接成的字符串是不是magicword会超时。如何优化呢？不难证明如下定理：如果一个长度为L的字符串s为magicword，那么s一定为K个相同子串拼接而成，并且s不能分割成i(i>K)个相同子串。这样，判断s是否为magicword时，我们需要先判断s是否由K个相同子串拼接而成。如果是，就枚举L的大于K的约数i，依次判断s是否由i个相同子串拼接而成，如果都不是，则s为magicword。L的约数个数大约为sqrt(n)个，时间复杂度约为O(n!*L*sqrt(L))。

?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

#include <iostream>
#include <cmath>
#include <ctime>
#include <string>
#include <sstream>
#include <cstdlib>
#include <cstdio>
#include <map>
#include <algorithm>
#include <vector>
 
using namespace std;
 
int g[111];
 
class MagicWords
{
public:
    int count(vector <string> S, int K)
    {
		int ans=0,n=S.size(),L=0,d[11];
		for(int i=0;i<n;++i) d[i]=i,L+=S[i].size();
		if(L%K) return 0;
		int len=0;
		for(int i=L;i>=K;--i)
			if(L%i==0)
				g[len++]=L/i;
		do
		{
			string s="";
			for(int i=0;i<n;++i) s+=S[d[i]];
			int i,j;
			for(i=0;i<len;++i)
			{
				for(j=g[i];j<L;++j)
					if(s[j]!=s[j%g[i]])
						break;
				if(j==L) break;
			}
			if(i==len-1) ++ans;
		} while(next_permutation(d,d+n));
		return ans;
    }
};

SettingTents
枚举+优化
本题解法分为两步：1、枚举出所有菱形的形状，确保不重不漏；2、对于每种形状的菱形，算出有多少个位置可以将其放进网格中。为枚举菱形的形状，我们先确定一个顶点，比如菱形最左边的顶点（如果菱形的左边是一条竖直的边就取下边的那个顶点），以它为原点(0,0)，从这里开始引边。如果我们枚举到两条边对应的顶点分别为(x1,y1)和(x2,y2)，则第四个顶点坐标为(x1+x2,y1+y2)。直接枚举会超时，但是注意到x1*x1+y1*y1==x2*x2+y2*y2，所以我们可以先将边长相同的所有(x,y)预处理到一个表中，这样计算时直接提取边长相同的边可以大大加快速度。最后，如果已确定菱形形状，找出这个菱形的“横平竖直”的外接矩形，设这个外接矩形长W宽H，则放置方案数为(N-W+1)*(M-H+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

#include <iostream>
#include <cmath>
#include <ctime>
#include <string>
#include <sstream>
#include <cstdlib>
#include <cstdio>
#include <map>
#include <algorithm>
#include <vector>
 
using namespace std;
 
int min(int a,int b,int c,int d)
{
	return min(min(min(a,b),c),d);
}
 
int max(int a,int b,int c,int d)
{
	return max(max(max(a,b),c),d);
}
 
class SettingTents
{
public:
	int countSites(int r,int c)
	{
		int ans=0;
		map <int,vector<pair<int,int> > > h; 
		for(int i=0;i<=r;++i)
			for(int j=-c;j<=c;++j)
				if(!(i==0&&j<=0))
					h[i*i+j*j].push_back(make_pair(i,j));
		for(int L=1;L<=r*r+c*c;++L)
			for(int i=0;i<h[L].size();++i)
				for(int j=i+1;j<h[L].size();++j)
				{
					int minx=min(0,h[L][i].first,h[L][j].first,h[L][i].first+h[L][j].first);
					int maxx=max(0,h[L][i].first,h[L][j].first,h[L][i].first+h[L][j].first);
					int miny=min(0,h[L][i].second,h[L][j].second,h[L][i].second+h[L][j].second);
					int maxy=max(0,h[L][i].second,h[L][j].second,h[L][i].second+h[L][j].second);
					int x=maxx-minx,y=maxy-miny;
					if(x>r||y>c) continue;
					ans+=(r-x+1)*(c-y+1);
				}
		return ans;
    }
};

BarbarianInvasion
网络流
将入侵部队看成源，首都看成汇，其它方格看成中间结点，相邻方格对应的结点间连边，这样构造出了一个网络。注意到本题的限制条件不在边上而在方格（也就是结点）上，用拆点解决这个问题，即将所有结点拆成两个结点并在其间连一条边，容量限制为破坏这个方格的花费，所有原来的边的容量都设为无穷大。我们希望删除尽可能少的容量小的边使得源到汇不连通，容易联想到最小割。这个网络的最小割能保证所有删除的边容量和最小，但是本题要求删除的边数最小，其次容量和最小，因此我们需要改造网络使得多删除一条边的代价很高：将所有方格的花费都加上一个非常大的整数即可。

Posted in SRM, TopCoder. Tags: , , . No Comments »

USACO JAN09 Gold Summary

February 9, 2009 — gnarlycow

damage
构造
不错的图论基础题。首先，如果第i头牛报告它所在的结点未损坏但无法返回牛棚，那么所有地震后与i连通的结点都不能与牛棚连通，否则牛i就可以先到这个结点再返回牛棚。由于我们希望与牛棚不连通的结点数尽可能少，于是我们尽可能让结点与牛棚连通。如果第i头牛报告它所在的结点未损坏但无法返回牛棚，由于地震不破坏边，所以与结点i相邻的结点地震后一定仍能到达结点i，因此它们一定不与牛棚连通。除此之外，其它结点都可能与牛棚连通，这样对于每个报告，我们将与之相邻的结点标记为与牛棚不连通。最后从牛棚开始在剩余结点上floodfill，能到达的结点为真正能于牛棚连通的结点。

?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

/*
ID: lipeiqi1
LANG: C++
PROB: damage
*/
#include <cstdio>
 
struct edge
{
	int v;
	edge *next;
	edge(int v,edge *next):v(v),next(next) {}
} *e[30003];
bool u[30003];
int ans;
 
void dfs(int v)
{
	if(u[v]) return;
	u[v]=true;
	--ans;
	for(edge *t=e[v];t;t=t->next) dfs(t->v);
}
 
int main()
{
	freopen("damage.in","r",stdin);
	freopen("damage.out","w",stdout);
	int p,c,n,a,b;
	scanf("%d %d %d",&p,&c,&n);
	for(int i=0;i<c;++i)
	{
		scanf("%d %d",&a,&b);
		e[a]=new edge(b,e[a]);
		e[b]=new edge(a,e[b]);
	}
	for(int i=0;i<n;++i)
	{
		scanf("%d",&b);
		for(edge *t=e[b];t;t=t->next) u[t->v]=true;
	}
	ans=p;
	dfs(1);
	printf("%d\n",ans);
	return 0;
}

baric

动态规划

f[i][j]表示前i个数中选出j个数作为子集并且第i个数一定入选子集的最小错误值，那么题中计算错误值的条件1对f[i][1]进行初始化，利用条件2进行状态转移求出f[i][j]，最后对于每个f[i][j]，将[i+1..n]造成的错误值考虑进来加到f[i][j]上去，枚举可求得错误值不超过限制的最小子集大小以及最小错误值。

?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

/*
ID: lipeiqi1
LANG: C++
PROB: baric
*/
#include <iostream>
 
using namespace std;
 
int d[101],f[101][101],s[101][101];
 
int main()
{
	freopen("baric.in","r",stdin);
	freopen("baric.out","w",stdout);
	int n,e;
	scanf("%d %d",&n,&e);
	for(int i=1;i<=n;++i) scanf("%d",d+i);
	for(int i=1;i<=n;++i)
		for(int j=1;j<i;++j)
			f[i][1]+=abs(d[i]-d[j])<<1;
	for(int i=1;i<n;++i)
		for(int j=i+2;j<=n;++j)
			for(int k=i+1;k<j;++k)
				s[i][j]+=abs((d[k]<<1)-d[i]-d[j]);
	for(int i=2;i<=n;++i)
		for(int j=2;j<=i;++j)
		{
			f[i][j]=f[i-1][j-1];
			for(int k=i-2;k>0;--k) f[i][j]=min(f[i][j],f[k][j-1]+s[k][i]);
		}
	for(int i=1;i<=n;++i)
		for(int j=1;j<=i;++j)
			for(int k=i+1;k<=n;++k)
				f[i][j]+=abs(d[i]-d[k])<<1;
	int minNum=n,minErr=INT_MAX;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=i;++j)
			if(f[i][j]<=e)
				if(j<minNum) minNum=j,minErr=f[i][j];
				else if(j==minNum) minErr=min(minErr,f[i][j]);
	printf("%d %d\n",minNum,minErr);
	return 0;
}

travel
图论综合题
由于题目保证从结点1到其它任何结点的最短路径唯一，结点1到其它结点的最短路径一定构成唯一的一棵最短路生成树。借助Dijkstra+普通二项堆可以在O(mlogm)的时间内构造最短路生成树。
接下来我们要做的就是求不经过最后一条边的次短路。从根(结点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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153

/*
ID: lipeiqi1
LANG: C++
PROG: travel
*/
#include <iostream>
#include <set>
 
using namespace std;
 
const int MAXN=100011;
struct edge
{
	int v,w;
	edge *next;
	edge(int v,int w,edge *next):v(v),w(w),next(next) {}
} *e[MAXN],*child[MAXN];
struct THeap
{
	int v,d;
} heap[MAXN];
int heapsize,k,n,timestamp,pos[MAXN],dis[MAXN],f[MAXN],num[MAXN],father[MAXN],ans[MAXN];
bool visited[MAXN];
multiset < pair<int,int> > d[MAXN];
 
inline int findRoot(int v)
{
	while(f[v]!=v) v=f[v]=f[f[v]];
	return v;
}
 
void unite(int x,int y)
{
	x=findRoot(x),y=findRoot(y);
	if(x==y) return;
	if(d[x].size()<d[y].size())
	{
		d[y].insert(d[x].begin(),d[x].end());
		d[x].clear();
		f[x]=y;
	}
	else
	{
		d[x].insert(d[y].begin(),d[y].end());
		d[y].clear();
		f[y]=x;
	}
}
 
void downMaintain(int k)
{
	int i=k;
	THeap x=heap[k];
	for(int j=k<<1;j<=heapsize;)
	{
		if(j<heapsize&&heap[j].d>heap[j+1].d) j++;
		if(x.d<=heap[j].d) break;
		heap[i]=heap[j];
		pos[heap[j].v]=i;
		i=j;
		j=i<<1;
	}
	heap[i]=x;
	pos[heap[i].v]=i;
}
 
void heapUpdate(int v,int dis)
{
	int i=pos[v];
	if(i&&heap[i].d<=dis) return;
	if(!i) i=++heapsize;
	for(;i!=1&&dis<heap[i>>1].d;i>>=1) heap[i]=heap[i>>1],pos[heap[i>>1].v]=i;
	heap[i].v=v;
	heap[i].d=dis;
	pos[v]=i;
}
 
void deleteMin()
{
	pos[heap[1].v]=0;
	heap[1]=heap[heapsize--];
	downMaintain(1);
}
 
void dijkstra(int vstart=1)
{
	int pv,pdis;
	heapUpdate(vstart,0);
	for(int i=0;i<n;i++)
	{
		do
		{
			pv=heap[1].v,pdis=heap[1].d;
			deleteMin();
		} while(visited[pv]);
		visited[pv]=true;
		dis[pv]=pdis;
		for(edge *t=e[pv];t;t=t->next)
			if(!visited[t->v])
				heapUpdate(t->v,pdis+t->w);
	}
}
 
void dfs(int v)
{
	num[v]=++timestamp;
	for(edge *t=child[v];t;t=t->next)
	{
		dfs(t->v);
		unite(v,t->v);
	}
	int c=findRoot(v);
	for(edge *t=e[v];t;t=t->next)
		if(t->v!=father[v])
		{
			if(!visited[t->v]||num[t->v]<num[v]) d[c].insert(make_pair(dis[v]+dis[t->v]+t->w,t->v)); 
			else
			{
				multiset<pair<int,int> >::iterator p=d[c].find(make_pair(dis[v]+dis[t->v]+t->w,v));
				if(p!=d[c].end()) d[c].erase(p);
			}
		}
	visited[v]=true;
	while(!d[c].empty()&&(visited[d[c].begin()->second]&&num[d[c].begin()->second]>num[v])) d[c].erase(d[c].begin());
	if(d[c].empty()) ans[v]=-1;
	else ans[v]=d[c].begin()->first;
}
 
int main()
{
	freopen("travel.in","r",stdin);
	freopen("travel.out","w",stdout);
	int m,a,b,w;
	for(scanf("%d %d",&n,&m);m;--m)
	{
		scanf("%d %d %d",&a,&b,&w);
		e[a]=new edge(b,w,e[a]);
		e[b]=new edge(a,w,e[b]);
	}
	dijkstra();
	for(int i=1;i<=n;++i)
		for(edge *t=e[i];t;t=t->next)
			if(dis[i]+t->w==dis[t->v])
			{
				father[t->v]=i;
				child[i]=new edge(t->v,t->w,child[i]);
			}
	for(int i=1;i<=n;++i) f[i]=i;
	memset(visited,false,sizeof(visited));
	dfs(1);
	for(int i=2;i<=n;++i) printf("%d\n",ans[i]==-1?-1:ans[i]-dis[i]);
	return 0;
}
Posted in Gold Division, USACO. Tags: , , . 5 Comments »
«
Newer posts » »