3.1 数组
读入一些整数，逆序输出到一行中。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19// 程序3-1 逆序输出
int a[maxn];
int x, n = 0;
while (scanf("%d", &x) == 1) {
a[n++] = x;
}
for (int i = n - 1; i >= 1; i--) {
printf("%d ", a[i]);
}
printf("%d\n", a[0]);
//测试的时候可以改为这样，方便中断程序
while (scanf("%d", &x) == 1 && x != -1)
1 2 3 4 5 6 -1
6 5 4 3 2 1
有n盏灯，编号为1～n。 第1个人把所有灯打开，第2个人按下所有编号为2的倍数的开关（这些灯将被关掉），第3个人按下所有编号为3的倍数的开关（其中关掉的灯将被打开，开着的灯将被关闭），依此类推。 一共有k个人，问最后有哪些灯开着？输入n和k，输出开着的灯的编号。 k≤n≤1000。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23// 程序3-2 开灯问题
int a[maxn];
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");
7 3
1 5 6 7
蛇形填数。 在n×n方阵里填入1，2，…，n×n，要求填成蛇形。 例如，n＝4时方阵为：1
2
3
410 11 12 1
9 16 13 2
8 15 14 3
7 6 5 4
1 | // 程序3-3 蛇形填数 |
3.2 字符数组
找出所有形如abc*de（三位数乘以两位数）的算式，使得在完整的竖式中，
所有数字都属于一个特定的数字集合。 输入数字集合（相邻数字之间没有空格），输出所有竖式。 每个竖式前应有编 号，之后应有一个空行。 最后输出解的总数。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// 程序3-4 竖式问题
int cnt = 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", ++cnt);
printf("%5d\nX%4d\n-----\n%5d\n%4d\n-----\n%5d\n\n", abc, de, x, y, z);
}
}
}
printf("The number of solution = %d\n", cnt);
2357
<1>
775
X 33
-----
2325
2325
-----
25575
The number of solution = 1
3.3 竞赛题目选讲
3-1 UVa272 Tex Quotes
在TeX中，左双引号是“”，右双引号是“’’”。 输入一篇包含双引号的文章，你的任务是
把它转换成TeX的格式。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16int 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 is the question".
``To be or not to be,'' quoth the Bard, ``that is the question''.
3-2 UVa10082 WERTYU
把手放在键盘上时，稍不注意就会往右错一位。这样，输入Q会变成输入W，输入J会变成输入K等。键盘如图3-2所示。输入一个错位后敲出的字符串（所有字母均大写），输出打字员本来想打出的句子。
输入保证合法，即一定是错位之后的字符串。例如输入中不会出现大写字母A。1
2
3
4
5
6
7
8
9
10
11
12
13char 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);
}
}
O S, GOMR YPFSU/
I AM FINE TODAY.
for (i = 1; s[i] && s[i] != c; i++);
c是键盘上打不出的字符（c不在s字符数组里）,直接输出c。
else putchar(c);
如果c = s[i],找出c在键盘中的位置,s的下标,然后输出前一个字符.
if (s[i]) putchar(s[i - 1]);
3-3 UVa401 Palindromes
输入一个字符串，判断它是否为回文串以及镜像串。输入字符串保证不含数字0。所谓回文串，就是反转以后和原串相同，如abba和madam。 所有镜像串，就是左右镜像之后和原串相同，如2S和3AIAE。注意，并不是每个字符在镜像之后都能得到一个合法字符。在本题中，每个字符的镜像如图3-3所示（空白项表示该字符镜像后不能得到一个合法字符）。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
31const char* res = "A 3 HIL JM O 2TUVWXY51SE Z 8 ";
const char* msg[] = {"not a palindrome","a regular palindrome","a mirrored string","a mirrored palindrome"};
char r(char ch) {
if (isalpha(ch)) return res[ch - 'A'];
return res[ch - '0' + 25];
}
int main() {
char s[300];
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 - i - 1]) p = 0; // 不是回文串
if (r(s[i]) != s[len - i - 1]) m = 0; // 不是镜像串
}
printf("%s -- is %s.\n\n", s, msg[m * 2 + p]);
}
}
NOTAPALINDROME
NOTAPALINDROME -- is not a palindrome.
ISAPALINILAPASI
ISAPALINILAPASI -- is a regular palindrome.
2A3MEAS
2A3MEAS -- is a mirrored string.
ATOYOTA
ATOYOTA -- is a mirrored palindrome.
3-4 UVa340 Master-Mind Hints
实现一个经典”猜数字”游戏。 给定答案序列和用户猜的序列，统计有多少数字位置正确（A），有多少数字在两个序列都出现过但位置不对（B）。
输入包含多组数据。每组输入第一行为序列长度n，第二行是答案序列，接下来是若干猜测序列。猜测序列全0时该组数据结束。n=0时输入结束。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
int main() {
int n, a[maxn], b[maxn];
int kase = 0;
while (scanf("%d", &n) == 1 && n) {
printf("Game %d:\n", ++kase);
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 UVa1583 Digit Generator
如果x加上x的各个数字之和得到y，就说x是y的生成元。 给出n（1≤n≤100000），求最小生成元。 无解输出0。 例如，n=216，121，2005时的解分别为198，0，1979。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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 = y + x % 10;
x = x / 10;
}
if (ans[y] == 0 || m < ans[y]) ans[y] = m;
}
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
printf("%d\n", ans[n]);
}
}
3-6 UVa1584 Circular Sequence
长度为n的环状串有n种表示法，分别为从某个位置开始顺时针得到。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
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 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 j = 0; j < n; j++) {
putchar(s[(j + ans) % n]);
}
putchar('\n');
}
}