《算法竞赛入门经典》读书笔记 第3章 数组和字符串

运行环境：Visual Studio2019

目录

• 第3章 数组和字符串

第3章 数组和字符串

3.1 数组

程序3-1 逆序输出

#include <stdio.h>
#define maxn 105

int a[maxn];

int main()
{
	int x, n = 0;
	while (scanf_s("%d", &x) == 1)
		a[n++] = x;
	for (int i = n - 1; i >= 1; i--)
		printf("%d ", a[i]);
	printf("%d\n", a[0]);
	return 0;
}

运行结果：

1
2
3
4
5
6
7
8
9
^Z
^Z
^Z
9 8 7 6 5 4 3 2 1

---

---

---

---

开灯问题

程序3-2 开灯问题

#include <stdio.h>
#include <string.h>
#define maxn 1010

int a[maxn];

int main()
{
	int n, k;
	int first = 1;
	memset(a, 0, sizeof(a));
	scanf_s("%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;
}

运行结果：

7 3
1 5 6 7

蛇形填数

程序3-3 蛇形填数

#include <stdio.h>
#include <string.h>
#define maxn 20

int a[maxn][maxn];

int main()
{
	int n, x, y, tot = 0;
	scanf_s("%d", &n);
	memset(a, 0, sizeof(a));
	tot = a[x = 0][y = n - 1] = 1;
	while (tot < n * n) {
		//while(没越界 && 没填过)
		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;
}

运行结果：

5
 13 14 15 16  1
 12 23 24 17  2
 11 22 25 18  3
 10 21 20 19  4
  9  8  7  6  5

---

---

3.2 字符数组

竖式问题

---

---

---

程序3-4 竖式问题

#include <stdio.h>
#include <string.h>
int main()
{
	int count = 0;
	char s[20], buf[99];
	//scanf("%s", s, 20);
	//修改以便在Visual Studio 2019上运行
	scanf_s("%s", s, 20 - 1);
	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_s(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\n", abc);
				printf("X%4d\n", de);
				printf("-----\n");
				printf("%5d\n", x);
				printf("%4d\n", y);
				printf("-----\n");
				printf("%5d\n\n", z);
			}
		}
	}
	printf("The number of solutions = %d.\n", count);
	return 0;
}

运行结果：

2357
<1>
  775
X  33
-----
 2325
2325
-----
25575

The number of solutions = 1.

---

---

---

3.3 竞赛题目选讲

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

---

---

---

---

---

---

---

---

程序3-5 TeX中的引号

#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;
}

运行结果：

"To be or not to be," quoth the Bard, "that
``To be or not to be,'' quoth the Bard, ``that
is the question".
is the question''.
^Z

例题3-2 WERTYU（WERTYU, UVa10082）

程序3-6 WERTYU

#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])
			putchar(s[i - 1]);
		else
			putchar(c);
	}
	return 0;
}

运行结果：

O S, GOMR YPFSU/
I AM FINE TODAY.
^Z

例题3-3 回文词（Palindromes, UVa401）