《算法竞赛入门经典训练指南》思维的体操

思维的体操

例题1 勇者斗恶龙（The Dragon of Loowater，Uva 11292）

贪心水题

Uva 11292view raw
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
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int d[20005],x[20005];
int main()
{
	int n,m;
	while(scanf("%d%d",&n,&m),n||m)
	{
		int i,j,k;
		for(i=0;i<n;i++)
			scanf("%d",&d[i]);
		for(i=0;i<m;i++)
			scanf("%d",&x[i]);

		sort(d,d+n);
		sort(x,x+m);

		j=0;
		int sum=0;
		for(i=0;i<n;i++)
		{
			while(j<m&&x[j]<d[i])
				j++;
			if(j==m)
				break;
			if(j!=m)
				sum+=x[j++];
		}

		if(i!=n)
			printf("Loowater is doomed!\n");
		else
			printf("%d\n",sum);
	}
	return 0;
}

例题2 突击战（Commando War，Uva 11729）

比较简单的贪心题

Uva 11729view raw
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
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct prog{
	int b,j;
}a[1005];
bool cmp(prog a,prog b)
{
	if(a.j==b.j)
		return a.b>b.b;
	return a.j>b.j;
}
int main()
{
	int n,cnt=1;;
	while(scanf("%d",&n),n)
	{
		int i,j,k;
		for(i=0;i<n;i++)
		{
			scanf("%d%d",&a[i].b,&a[i].j);
		}
		sort(a,a+n,cmp);

		int ans=0;
		int tmp=0;
		for(i=0;i<n;i++)
		{
			ans=max(ans,tmp+a[i].b+a[i].j);
			tmp+=a[i].b;
		}
		printf("Case %d: %d\n",cnt++,ans);
	}
	return 0;
}

例题3 分金币（Spreading the Wealth，Uva 11300）

这题有点意思，初看起来不知道怎么下手，但可以发现一个人得到的金币来自于其两边的人，或者他只能将金币转手给旁边的人，于是我们就可以假设${A}{i}从{A}{i-1}处得到{x}{i-1}的金币，并转手给{A}{i+1}有{x}{i}的金币（注意是圆桌），于是就有{A}{i}+{x}{i-1}-{x}{i}=average，最后可以得出{x}{i}关于{x}{1}的表达式，依据题意，求的是\sum_{1}^{n}|{x}_{i}|$的和，就可以借助数轴解决问题

Uva 11300view raw
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 <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

#define zero(a) memset(a,0,sizeof(a))
#define one(a) memset(a,1,sizeof(a))
#define fone(a) memset(a,-1,sizeof(a))
#define pow2(a) ((a)*(a))
#define pow3(a) ((pow2(a))*(a))

long long money[1000005];
long long tmp[1000005];
int main()
{
	int n;
	while(~scanf("%d",&n))
	{
		long long sum=0;
		int i,j;
		for(i=0;i<n;i++)
		{
			scanf("%lld",&money[i]);
			sum+=money[i];
		}
		int ave=sum/n;
		for(i=0;i<n;i++)
		{
			money[i]=money[i]-ave;
		//	printf("%d\n",money[i]);
		}
		tmp[0]=0;
		for(i=1;i<n;i++)
			tmp[i]=tmp[i-1]-money[i];
		sort(tmp,tmp+n);
		int mid=n/2;

		long long ans=0;
		for(i=0;i<n;i++)
		{
			ans+=abs(-tmp[i]+tmp[mid]);
		}
		printf("%lld\n",ans);
	}
    return 0;
}

例题4 墓地雕塑（Graveyard，LA3708，POJ3154）

比较简单的一题，算出每个点的初始位置和移动后的位置，每个点向最近的地方移动即可。lrj书上介绍的方法更巧妙

poj 3154view raw
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
#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

double old_place[1005];
double new_place[2010];
int main()
{
	int n,m;
	while(~scanf("%d%d",&n,&m))
	{
		int mk=m+n;
		double old=10000.0/n;
		double now=10000.0/mk;
		int i;
		for(i=0;i<n;i++)
			old_place[i]=old*i;

		for(i=0;i<=mk;i++)
			new_place[i]=now*i;
		int j=0;
		double sum=0.0;
		for(i=0;i<n;i++)
		{
			while(fabs(old_place[i]-new_place[j])>fabs(old_place[i]-new_place[j+1]))
				j=j+1;
			sum+=fabs(old_place[i]-new_place[j]);
		}
		printf("%.4lf\n",sum);
	}
    return 0;
}

例题5 蚂蚁（Piotr’s Ants，Uva10881）

如果能注意到蚂蚁“碰撞”实际上是没有改变蚂蚁最终的位置，只是改变了蚂蚁的序号的话，那这题就很容易了

Uva 10881view raw
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
#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

#define zero(a) memset(a,0,sizeof(a))
#define one(a) memset(a,1,sizeof(a))
#define fone(a) memset(a,-1,sizeof(a))
#define pow2(a) ((a)*(a))
#define pow3(a) ((pow2(a))*(a))

struct prog
{
	int x,i;
	char f;
	int rank;
}x[10010],y[10010];
bool operator<(prog a,prog b)
{
	return a.x<b.x;
}
bool cmpi(prog a,prog b)
{
	return a.i<b.i;
}
int main()
{
	int TTT;
	scanf("%d",&TTT);
	int cas=1;
	while(TTT--)
	{
		int l,t,n;
		scanf("%d%d%d",&l,&t,&n);
		int i,j;
		for(i=0;i<n;i++)
		{
			int a;
			char b[5];
			scanf("%d%s",&a,b);
			x[i].x=a;
			x[i].i=i;
			if(b[0] == 'L')
			{
				x[i].f=b[0];
				y[i].x=a-t;
			}
			else
			{
				x[i].f=b[0];
				y[i].x=a+t;
			}
			y[i].f=x[i].f;
			y[i].i=x[i].i;
		}
		sort(x,x+n);
		sort(y,y+n);
		for(i=0;i<n;i++)
		{
			x[i].rank=i;
			y[i].rank=i;
		}

		sort(x,x+n,cmpi);
		printf("Case #%d:\n",cas++);
		for(i=0;i<n;i++)
		{
			int k=x[i].rank;
			if(y[k].x<0||y[k].x>l)
			{
				printf("Fell off\n");
			}
			else
			{
				if((k>0&&y[k].x==y[k-1].x)||(k<n-1&&y[k].x==y[k+1].x))
					printf("%d Turning\n",y[k].x);
				else
					printf("%d %c\n",y[k].x,y[k].f);
			}
		}
		puts("");
	}
    return 0;
}

例题6 立方体成像（Image Is Everything，LA2995）

较麻烦的一道模拟题，看了lrj的白书后才过的，书上讲的较详细，此处略过

LA 2995view raw
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
#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

#define zero(a) memset(a,0,sizeof(a))
#define one(a) memset(a,1,sizeof(a))
#define fone(a) memset(a,-1,sizeof(a))
#define pow2(a) ((a)*(a))
#define pow3(a) ((pow2(a))*(a))

int n;
char tx[15][15][15];
char kan[10][15][15];
void xyz(int k,int i,int j,int len,int& x,int& y , int& z)
{
	switch(k)
	{
	case 0:
		x=len;
		y=j;
		z=i;
		break;
	case 1:
		x=n-1-j;
		y=len;
		z=i;
		break;
	case 2:
		x=n-1-len;
		y=n-1-j;
		z=i;
		break;
	case 3:
		x=j;
		y=n-1-len;
		z=i;
		break;
	case 4:
		x=n-1-i;
		y=j;
		z=len;
		break;
	case 5:
		x=i;
		y=j;
		z=n-1-len;
		break;
	default:break;
	}
}

int main()
{
	while(scanf("%d",&n),n)
	{
		int i,j,k,p,q;
		for(i=0;i<n;i++)
			for(j=0;j<n;j++)
				for(k=0;k<n;k++)
					tx[i][j][k]='#';

		for(i=0;i<n;i++)
			for(j=0;j<6;j++)
				scanf("%s",kan[j][i]);
/*
		for(k=0;k<6;k++)
		{
			for(i=0;i<n;i++)
			{
				for(j=0;j<n;j++)
					cout<<kan[k][i][j];
				cout<<endl;
			}
			cout<<endl;
		}
*/

		for(k=0;k<6;k++)
		{
			for(i=0;i<n;i++)
				for(j=0;j<n;j++)
					if(kan[k][i][j]=='.')
					{
						for(p=0;p<n;p++)
						{
							int x,y,z;
							xyz(k,i,j,p,x,y,z);
							tx[x][y][z]='.';
					//		cout<<x<<' '<<y<<' '<<z<<endl;
						}
					//	cout<<endl;
					}

		}
		while(1)
		{
			bool ok=true;
			for(k=0;k<6;k++)
			{
				for(i=0;i<n;i++)
					for(j=0;j<n;j++)
						if(kan[k][i][j]!='.')
						{
							for(p=0;p<n;p++)
							{
								int x,y,z;
								xyz(k,i,j,p,x,y,z);
								//cout<<x<<y<<z<<endl;
								//cout<<tuxing<<endl;
								if(tx[x][y][z]=='.')
									continue;
								if(tx[x][y][z]=='#')
								{
									tx[x][y][z]=kan[k][i][j];
									break;
								}
								if(tx[x][y][z]==kan[k][i][j])
								{
									break;
								}
								tx[x][y][z]='.';
								ok=false;
							}
						}
			}
			if(ok==true)
				break;
		}
		int sum=0;
		for(i=0;i<n;i++)
			for(j=0;j<n;j++)
				for(k=0;k<n;k++)
					if(tx[i][j][k]!='.')
						sum++;

		printf("Maximum weight: %d gram(s)\n",sum);

	}
    return 0;
}

扫一扫，分享到微信

微信分享二维码