《算法竞赛入门经典（第2版）》代码 Chapter 3

算法竞赛QQ群：210838572，一起进步吧！

后面有些习题不想做了，留着以后做吧。觉得进度好慢啊。

讲解代码

3.1s1 逆序输出

// 3.1s1
#include<stdio.h>
#define MAXN 105
int a[MAXN];
int main()
{
	int x, n = 0;
	while(scanf("%d", &x) == 1)
	{
		a[++n] = x; 
	}
	for(int i = n; i > 1; i--)
	{
		printf("%d ", a[i]);
	}
	printf("%d\n", a[1]);
	return 0;
}

3.1s2 开灯问题

// 3.1s2
#include <stdio.h>
#include <string.h>
#define MAXN 1010
int a[MAXN]; 
int main()
{
	int n, k, first = 1;
	memset(a, 0, sizeof(a));
	scanf("%d%d", &n, &k);
	for(int i = 1; i <= k; i ++)
	{
		for(int j = 1; j <= n; j++)
		{
			if(j%i == 0) a[j] = !a[j];
		}
	}
	for(int i = 1; i <= n; i++)
	{
		if(a[i])
		{
			if(first)
			{
				first = 0;
			}
			else
			{
				printf(" ");
			}
			printf("%d", i);
		}
	}
	printf("\n");
	return 0;
}

3.1s3 蛇形填数

// 3.1s3
#include <stdio.h>
#include <string.h>
#define MAXN 20
int a[MAXN][MAXN];
int main()
{
	int n, x, y, tot = 0;
	scanf("%d", &n);
	memset(a, 0, sizeof(a));
	tot = a[x=0][y=n-1] = 1;
	while(tot < n*n)
	{
		while(x+1<n && !a[x+1][y]) a[++x][y] = ++tot;
		while(y-1>=0 && !a[x][y-1]) a[x][--y] = ++tot;
		while(x-1>=0 && !a[x-1][y]) a[--x][y] = ++tot;
		while(y+1<n && !a[x][y+1]) a[x][++y] = ++tot;
	}
	for(x = 0; x < n; x++)
	{
		for(y = 0; y < n; y++)
		{
			printf("%3d", a[x][y]);
		}
		printf("\n");
	}
	return 0;
}

3.2s1 竖式问题

// 3.2s1
#include <stdio.h>
#include <string.h>
int main()
{
	int count = 0;
	char s[20], buf[99];
	scanf("%s", &s);
	for(int abc = 111; abc <= 999; abc++)
	{
		for(int de = 11; de <= 99; de++)
		{
			int x = abc*(de%10), y = abc*(de/10), z = abc*de;
			sprintf(buf, "%d%d%d%d%d", abc, de, x, y, z);
			int ok = 1;
			for(int i = 0; i < strlen(buf); i++)
			{
				if(strchr(s, buf[i]) == NULL) ok = 0;
			}
			if(ok)
			{
				printf("<%d>\n", ++count);
				printf("%5d\nX%4d\n-----\n%5d\n%4d \n-----\n%5d\n\n", abc, de, x, y, z);
			}
		}
	} 
	printf("The number of solutions = %d\n", count);
	return 0;
}

例题代码

3-1 TeX中的引号（TeX Quotes, UVa 272）

// 3-1
#include <stdio.h>
int main()
{
	int c, q = 1;
	while((c = getchar()) != EOF)
	{
		if(c == '"')
		{
			printf("%s", q ? "“" : "”");
			q = !q;
		}
		else
		{
			printf("%c", c);
		}
	}
	return 0;
}

3-2 WERTYU（WERTYU, UVa 10082）

// 3-2
#include <stdio.h>
char s[] = "`1234567890-=QWERTYUIOP[]\\ASDFGHJKL;'ZXCVBNM,./";
int main()
{
	int i, c;
	while((c = getchar()) != EOF)
	{
		for(i = 1; s[i] && s[i]!=c; i++) {} 
		if(s[i]) // 这点我不理解，但是可以推测出此条语句是在判断s[i]是否超出了字符串s的长度（即在不在字符串s中） 
		{
			putchar(s[i-1]);
		}
		else
		{
			putchar(c);
		}
	}
	return 0;
}

3-3 回文词（Palindromes, UVa 401）

// 3-3
#include <stdio.h>
#include <string.h>
#include <ctype.h>
const char* rev = "A   3  HIL JM O   2TUVWXY51SE Z  8 ";
const char* msg[] = {"not a palindrom", "a regular palindrome", "a mirrored string", "a mirrored palindrome"};
 
char r(char ch)
{
	if(isalpha(ch))
	{
		return rev[ch-'A'];
	}
	return rev[ch-'0'+25];
}
 
int main()
{
	char s[30];
	while(scanf("%s", s) == 1)
	{
		int len = strlen(s);
		int p = 1, m = 1;
		for(int i = 0; i < (len+1)/2; i++)
		{
			if(s[i] != s[len-1-i])
			{
				p = 0; // 不是回文串 
			}
			if(r(s[i]) != s[len-1-i])
			{
				m = 0; // 不是镜像串 
			}
		}
		printf("%s -- is %s.\n\n", s, msg[m*2+p]); // 此处msg[]的设置挺巧妙，很简洁，值得借鉴 
	}
	return 0;
}

3-4 猜数字游戏的提示（Master-Mind Hints, UVa 340）

// 3-4
// 直接统计可得A，为了求B，对于每个数字（1~9），统计二者出现的次数c1和c2，则min(c1,c2)，就是该数字对B的贡献。最后要减去A的部分。 
// 上面这句话不太好理解，好好想一想。 
#include <stdio.h>
#define MAXN 1010
int main()
{
	int n, a[MAXN], b[MAXN];
	int round = 0;
	while(scanf("%d", &n) == 1 && n)
	{
		printf("Game %d:\n", ++round);
		for(int i = 0; i < n; i++)
		{
			scanf("%d", &a[i]);
		}
		for(;;)
		{
			int A = 0, B = 0;
			for(int i = 0; i < n; i++)
			{
				scanf("%d", &b[i]);
				if(a[i] == b[i])
				{
					A++;
				}
			}
			if(b[0] == 0)
			{
				break;
			}
			for(int d = 1; d <= 9; d++)
			{
				int c1 = 0, c2 = 0;
				for(int i = 0; i < n; i++)
				{
					if(a[i] == d) c1++;
					if(b[i] == d) c2++;
				}
				if(c1 < c2)
				{
					B += c1;
				}
				else
				{
					B += c2;
				}
			}
			printf("    (%d, %d)\n", A, B-A);
		}
	} 
	return 0;
}

3-5 生成元（Digit Generator, ACM/ICPC Seoul 2005, UVa 1583）

#include <stdio.h>
#include <string.h>
#define MAXN 10005
int ans[MAXN];
int main()
{
	int T, n;
	memset(ans, 0, sizeof(ans));
	for(int m = 1; m < MAXN ; m++)
	{
		int x = m, y = m;
		while(x > 0)
		{
			y += x%10;
			x /= 10; 
		}
		if(ans[y] == 0 || m < ans[y]) // ans[i]是i的最小生成元 
		{
			ans[y] = m; 
		}
	}
	scanf("%d", &T);
	while(T--) // T应该代表输入数据共有T组 
	{
		scanf("%d", &n);
		printf("%d\n", ans[n]); 
	}
	return 0;
}

3-6 环状序列（Circular Sequence, ACM/ICPC Seoul 2004, UVa 1584）

#include <stdio.h>
#include <string.h>
#define MAXN 105
 
int less(const char* s, int p, int q)
{
	int n = strlen(s);
	for(int i = 0; i < n; i++)
	{
	//	if(s[(p+i)%n] < s[(q+i)%n])
	//		return 1;
	// 上面的代码是不正确的，为什么？不解 
		if(s[(p+i)%n] != s[(q+i)%n])
			return s[(p+i)%n] < s[(q+i)%n];
	}
	return 0;
}
 
int main()
{
	int T;
	char s[MAXN];
	scanf("%d", &T);
	while(T--)
	{
		scanf("%s", s);
		int ans = 0;
		int n = strlen(s);
		for(int i = 1; i < n; i++)
		{
			if(less(s, i, ans)) ans = i;
		}
		for(int i = 0; i < n; i++)
		{
			putchar(s[(i+ans)%n]);
		}
		putchar('\n');
	}
	return 0;
}

习题代码

t3-1 得分（Score, ACM/ICPC Seoul 2005, UVa 1585）

// t3-1
#include <stdio.h>
int main()
{
	char a;
	int score = 0, nu = 0;
	while((a = getchar()) != '\n')
	{
		if(a == 'O')
		{
			score += ++nu;
		}
		else
		{
			nu = 0;
		}
	}
	printf("%d\n", score);
	return 0;
}

t3-2 分子量（Molar Mass, ACM/ICPC Seoul 2007, UVa 1586）

// t3-2
#include <stdio.h>
#include <ctype.h>
#define C 12.01
#define H 1.008
#define O 16.00
#define N 14.01
int main()
{
	int n;
	char c;
	double sum = 0, mas;
	while((c = getchar()) && c != '\n')
	{
		if(isalpha(c))
		{
			if(c == 'C') mas = C;
			if(c == 'H') mas = H;
			if(c == 'O') mas = O;
			if(c == 'N') mas = N;
			n = 1;
			sum += mas;
		}
		else
		{
			n = c-'1';
			sum += mas*n;
		}
	}
	printf("%3fg/mol\n", sum);
	return 0;
}

t3-3 数数字（Digit Counting, ACM/ICPC Danang 2007, UVa 1225）

// t3-3
#include <stdio.h>
#include <string.h>
int main()
{
	int num[10];
	char c;
	memset(num, 0, sizeof(num));
	while((c = getchar()) && c != '\n')
	{
		num[c-'0']++;
	}
	for(int i = 0; i < 9; i++)
	{
		printf("%d ", num[i]);
	}
	printf("%d\n", num[9]);
	return 0;
}

t3-4 周期串（Periodic Strings, UVa 455）

// t3-4 参考了别人的代码
#include <stdio.h>
#include <string.h>
#define MAXN 105
int main()
{
	char s[MAXN];
	scanf("%s", s);
	int len = strlen(s);
	for(int i = 1; i < len; i++)
	{
		int ok = 1;
		if(len%i == 0)
		{
			for(int j = 1; j < len; j++)
			{
				if(s[j] != s[j%i])
				{
					ok = 0;
					break;
				}
			}
			if(ok)
			{
				printf("%d\n", i);
				break;
			}
		}
	}
	return 0;
}