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

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

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

讲解代码

3.1s1 逆序输出

[cpp] view plain copy

1. // 3.1s1  
2. #include<stdio.h>  
3. #define MAXN 105  
4. int a[MAXN];  
5. int main()  
6. {  
7.     int x, n = 0;  
8.     while(scanf("%d", &x) == 1)  
9.     {  
10.         a[++n] = x;   
11.     }  
12.     for(int i = n; i > 1; i--)  
13.     {  
14.         printf("%d ", a[i]);  
15.     }  
16.     printf("%d\n", a[1]);  
17.     return 0;  
18. }  

3.1s2 开灯问题

[cpp] view plain copy

1. // 3.1s2  
2. #include <stdio.h>  
3. #include <string.h>  
4. #define MAXN 1010  
5. int a[MAXN];   
6. int main()  
7. {  
8.     int n, k, first = 1;  
9.     memset(a, 0, sizeof(a));  
10.     scanf("%d%d", &n, &k);  
11.     for(int i = 1; i <= k; i ++)  
12.     {  
13.         for(int j = 1; j <= n; j++)  
14.         {  
15.             if(j%i == 0) a[j] = !a[j];  
16.         }  
17.     }  
18.     for(int i = 1; i <= n; i++)  
19.     {  
20.         if(a[i])  
21.         {  
22.             if(first)  
23.             {  
24.                 first = 0;  
25.             }  
26.             else  
27.             {  
28.                 printf(" ");  
29.             }  
30.             printf("%d", i);  
31.         }  
32.     }  
33.     printf("\n");  
34.     return 0;  
35. }  

3.1s3 蛇形填数

[cpp] view plain copy

1. // 3.1s3  
2. #include <stdio.h>  
3. #include <string.h>  
4. #define MAXN 20  
5. int a[MAXN][MAXN];  
6. int main()  
7. {  
8.     int n, x, y, tot = 0;  
9.     scanf("%d", &n);  
10.     memset(a, 0, sizeof(a));  
11.     tot = a[x=0][y=n-1] = 1;  
12.     while(tot < n*n)  
13.     {  
14.         while(x+1<n && !a[x+1][y]) a[++x][y] = ++tot;  
15.         while(y-1>=0 && !a[x][y-1]) a[x][--y] = ++tot;  
16.         while(x-1>=0 && !a[x-1][y]) a[--x][y] = ++tot;  
17.         while(y+1<n && !a[x][y+1]) a[x][++y] = ++tot;  
18.     }  
19.     for(x = 0; x < n; x++)  
20.     {  
21.         for(y = 0; y < n; y++)  
22.         {  
23.             printf("%3d", a[x][y]);  
24.         }  
25.         printf("\n");  
26.     }  
27.     return 0;  
28. }  

3.2s1 竖式问题

[cpp] view plain copy

1. // 3.2s1  
2. #include <stdio.h>  
3. #include <string.h>  
4. int main()  
5. {  
6.     int count = 0;  
7.     char s[20], buf[99];  
8.     scanf("%s", &s);  
9.     for(int abc = 111; abc <= 999; abc++)  
10.     {  
11.         for(int de = 11; de <= 99; de++)  
12.         {  
13.             int x = abc*(de%10), y = abc*(de/10), z = abc*de;  
14.             sprintf(buf, "%d%d%d%d%d", abc, de, x, y, z);  
15.             int ok = 1;  
16.             for(int i = 0; i < strlen(buf); i++)  
17.             {  
18.                 if(strchr(s, buf[i]) == NULL) ok = 0;  
19.             }  
20.             if(ok)  
21.             {  
22.                 printf("<%d>\n", ++count);  
23.                 printf("%5d\nX%4d\n-----\n%5d\n%4d \n-----\n%5d\n\n", abc, de, x, y, z);  
24.             }  
25.         }  
26.     }   
27.     printf("The number of solutions = %d\n", count);  
28.     return 0;  
29. }  

例题代码

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

[cpp] view plain copy

1. // 3-1  
2. #include <stdio.h>  
3. int main()  
4. {  
5.     int c, q = 1;  
6.     while((c = getchar()) != EOF)  
7.     {  
8.         if(c == '"')  
9.         {  
10.             printf("%s", q ? "“" : "”");  
11.             q = !q;  
12.         }  
13.         else  
14.         {  
15.             printf("%c", c);  
16.         }  
17.     }  
18.     return 0;  
19. }  

3-2 WERTYU（WERTYU, UVa 10082）

[cpp] view plain copy

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

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

[cpp] view plain copy

1. // 3-3  
2. #include <stdio.h>  
3. #include <string.h>  
4. #include <ctype.h>  
5. const char* rev = "A   3  HIL JM O   2TUVWXY51SE Z  8 ";  
6. const char* msg[] = {"not a palindrom", "a regular palindrome", "a mirrored string", "a mirrored palindrome"};  
7.   
8. char r(char ch)  
9. {  
10.     if(isalpha(ch))  
11.     {  
12.         return rev[ch-'A'];  
13.     }  
14.     return rev[ch-'0'+25];  
15. }  
16.   
17. int main()  
18. {  
19.     char s[30];  
20.     while(scanf("%s", s) == 1)  
21.     {  
22.         int len = strlen(s);  
23.         int p = 1, m = 1;  
24.         for(int i = 0; i < (len+1)/2; i++)  
25.         {  
26.             if(s[i] != s[len-1-i])  
27.             {  
28.                 p = 0; // 不是回文串   
29.             }  
30.             if(r(s[i]) != s[len-1-i])  
31.             {  
32.                 m = 0; // 不是镜像串   
33.             }  
34.         }  
35.         printf("%s -- is %s.\n\n", s, msg[m*2+p]); // 此处msg[]的设置挺巧妙，很简洁，值得借鉴   
36.     }  
37.     return 0;  
38. }  

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

[cpp] view plain copy

1. // 3-4  
2. // 直接统计可得A，为了求B，对于每个数字（1~9），统计二者出现的次数c1和c2，则min(c1,c2)，就是该数字对B的贡献。最后要减去A的部分。   
3. // 上面这句话不太好理解，好好想一想。   
4. #include <stdio.h>  
5. #define MAXN 1010  
6. int main()  
7. {  
8.     int n, a[MAXN], b[MAXN];  
9.     int round = 0;  
10.     while(scanf("%d", &n) == 1 && n)  
11.     {  
12.         printf("Game %d:\n", ++round);  
13.         for(int i = 0; i < n; i++)  
14.         {  
15.             scanf("%d", &a[i]);  
16.         }  
17.         for(;;)  
18.         {  
19.             int A = 0, B = 0;  
20.             for(int i = 0; i < n; i++)  
21.             {  
22.                 scanf("%d", &b[i]);  
23.                 if(a[i] == b[i])  
24.                 {  
25.                     A++;  
26.                 }  
27.             }  
28.             if(b[0] == 0)  
29.             {  
30.                 break;  
31.             }  
32.             for(int d = 1; d <= 9; d++)  
33.             {  
34.                 int c1 = 0, c2 = 0;  
35.                 for(int i = 0; i < n; i++)  
36.                 {  
37.                     if(a[i] == d) c1++;  
38.                     if(b[i] == d) c2++;  
39.                 }  
40.                 if(c1 < c2)  
41.                 {  
42.                     B += c1;  
43.                 }  
44.                 else  
45.                 {  
46.                     B += c2;  
47.                 }  
48.             }  
49.             printf("    (%d, %d)\n", A, B-A);  
50.         }  
51.     }   
52.     return 0;  
53. }  

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

[cpp] view plain copy

1. #include <stdio.h>  
2. #include <string.h>  
3. #define MAXN 10005  
4. int ans[MAXN];  
5. int main()  
6. {  
7.     int T, n;  
8.     memset(ans, 0, sizeof(ans));  
9.     for(int m = 1; m < MAXN ; m++)  
10.     {  
11.         int x = m, y = m;  
12.         while(x > 0)  
13.         {  
14.             y += x%10;  
15.             x /= 10;   
16.         }  
17.         if(ans[y] == 0 || m < ans[y]) // ans[i]是i的最小生成元   
18.         {  
19.             ans[y] = m;   
20.         }  
21.     }  
22.     scanf("%d", &T);  
23.     while(T--) // T应该代表输入数据共有T组   
24.     {  
25.         scanf("%d", &n);  
26.         printf("%d\n", ans[n]);   
27.     }  
28.     return 0;  
29. }  

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

[cpp] view plain copy

1. #include <stdio.h>  
2. #include <string.h>  
3. #define MAXN 105  
4.   
5. int less(const char* s, int p, int q)  
6. {  
7.     int n = strlen(s);  
8.     for(int i = 0; i < n; i++)  
9.     {  
10.     //  if(s[(p+i)%n] < s[(q+i)%n])  
11.     //      return 1;  
12.     // 上面的代码是不正确的，为什么？不解   
13.         if(s[(p+i)%n] != s[(q+i)%n])  
14.             return s[(p+i)%n] < s[(q+i)%n];  
15.     }  
16.     return 0;  
17. }  
18.   
19. int main()  
20. {  
21.     int T;  
22.     char s[MAXN];  
23.     scanf("%d", &T);  
24.     while(T--)  
25.     {  
26.         scanf("%s", s);  
27.         int ans = 0;  
28.         int n = strlen(s);  
29.         for(int i = 1; i < n; i++)  
30.         {  
31.             if(less(s, i, ans)) ans = i;  
32.         }  
33.         for(int i = 0; i < n; i++)  
34.         {  
35.             putchar(s[(i+ans)%n]);  
36.         }  
37.         putchar('\n');  
38.     }  
39.     return 0;  
40. }  

习题代码

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

[cpp] view plain copy

1. // t3-1  
2. #include <stdio.h>  
3. int main()  
4. {  
5.     char a;  
6.     int score = 0, nu = 0;  
7.     while((a = getchar()) != '\n')  
8.     {  
9.         if(a == 'O')  
10.         {  
11.             score += ++nu;  
12.         }  
13.         else  
14.         {  
15.             nu = 0;  
16.         }  
17.     }  
18.     printf("%d\n", score);  
19.     return 0;  
20. }  

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

[cpp] view plain copy

1. // t3-2  
2. #include <stdio.h>  
3. #include <ctype.h>  
4. #define C 12.01  
5. #define H 1.008  
6. #define O 16.00  
7. #define N 14.01  
8. int main()  
9. {  
10.     int n;  
11.     char c;  
12.     double sum = 0, mas;  
13.     while((c = getchar()) && c != '\n')  
14.     {  
15.         if(isalpha(c))  
16.         {  
17.             if(c == 'C') mas = C;  
18.             if(c == 'H') mas = H;  
19.             if(c == 'O') mas = O;  
20.             if(c == 'N') mas = N;  
21.             n = 1;  
22.             sum += mas;  
23.         }  
24.         else  
25.         {  
26.             n = c-'1';  
27.             sum += mas*n;  
28.         }  
29.     }  
30.     printf("%3fg/mol\n", sum);  
31.     return 0;  
32. }  

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

[cpp] view plain copy

1. // t3-3  
2. #include <stdio.h>  
3. #include <string.h>  
4. int main()  
5. {  
6.     int num[10];  
7.     char c;  
8.     memset(num, 0, sizeof(num));  
9.     while((c = getchar()) && c != '\n')  
10.     {  
11.         num[c-'0']++;  
12.     }  
13.     for(int i = 0; i < 9; i++)  
14.     {  
15.         printf("%d ", num[i]);  
16.     }  
17.     printf("%d\n", num[9]);  
18.     return 0;  
19. }  

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

[cpp] view plain copy

1. // t3-4 参考了别人的代码  
2. #include <stdio.h>  
3. #include <string.h>  
4. #define MAXN 105  
5. int main()  
6. {  
7.     char s[MAXN];  
8.     scanf("%s", s);  
9.     int len = strlen(s);  
10.     for(int i = 1; i < len; i++)  
11.     {  
12.         int ok = 1;  
13.         if(len%i == 0)  
14.         {  
15.             for(int j = 1; j < len; j++)  
16.             {  
17.                 if(s[j] != s[j%i])  
18.                 {  
19.                     ok = 0;  
20.                     break;  
21.                 }  
22.             }  
23.             if(ok)  
24.             {  
25.                 printf("%d\n", i);  
26.                 break;  
27.             }  
28.         }  
29.     }  
30.     return 0;  
31. }