算法竞赛入门经典（第二版）学习笔记
本文是《算法竞赛入门经典（第二版）》这本书中的学习总结，如有不足欢迎提出宝贵意见。
第一章 程序设计入门1.1 算数表达式
实验1 ~ 4
int main(){ printf("%d\n", 3 - 4); // 实验1 printf("%d\n", 5 * 6); // 实验2 printf("%d\n", 8 / 4); // 实验3 printf("%d\n", 8 / 5); // 实验4 return 0;}/*执行结果-13021*/实验5 ~ 6
#includeint main(){ printf("%.2f\n", 8.0 / 5.0); // 实验5: 1的含义是小数点后保留1位小数，%f的含义是输出浮点数 printf("%.1f\n", 8 / 5); // 实验6 printf("%d\n", 8.0 / 5.0); // 实验7 return 0;}/*执行结果1.600.0-1717986918*/实验6与实验7的结果不必深究。
1.5 注解与习题
实验A1
int main(){ printf("%d\n", 11111 * 111111); // 5个1 printf("%d\n", 111111 * 111111); // 6个1 printf("%d\n", 111111111 * 111111111); // 9个1 return 0;}/*执行结果1234554321-539247567 溢出1653732529 溢出*/实验A2
#include#includeint main(){ printf("%f\n", 11111.0 * 111111.0); // 5个1 printf("%f\n", 111111.0 * 111111.0); // 6个1 printf("%f\n", 111111111.0 * 111111111.0); // 9个1 return 0;}/*执行结果1234554321.00000012345654321.00000012345678987654320.000000 double在此环境表示16位有效数字*/实验A3
#include#includeint main(){ printf("%f\n", sqrt(-10)); return 0;}/*执行结果nan*/实验A4
#include#includeint main(){ printf("%f\n", 1.0 / 0.0); printf("%f\n", 0.0 / 0.0); return 0;}/*执行结果infnan*/实验A5
#include#includeint main(){ printf("%d\n", 1 / 0); return 0;}/*执行结果*/实验B1 ~ B4
略.
习题1-1
#includeint main(){ int a, b, c; scanf("%d%d%d", &a, &b, &c); printf("%0.3f\n", (a + b + c) / 3.0); return 0;}习题1-2
#includeint main(){ double f; scanf("%lf", &f); printf("%.3f\n", 5 * (f - 32) / 9); return 0;}/*执行结果1 输入-17.222 输出*/习题1-3
#includeint main(){ int n; scanf("%d", &n); printf("%d\n", n * (n + 1) / 2); return 0;}/*执行结果100 输入5050 输出*/习题1-4
#include#include#define PI acos(-1)int main(){ int n; scanf("%d", &n); printf("%f\n", sin(n * PI / 180)); // 三角函数的参数是弧度值而不是角度值 printf("%f\n", cos(n * PI / 180)); return 0;}/*执行结果0.866025 输入0.500000 输出*/习题1-5
#includeint main(){ const double PRICE = 95.0, DISCOUNT = 0.95; int cnt; scanf("%d", &cnt); if(cnt * PRICE >= 300){ printf("%.2f\n", cnt * PRICE * DISCOUNT); }else{ printf("%.2f\n", cnt * PRICE); } return 0;}/*执行结果4361.00*/习题1-6
#includevoid swap(int *a, int *b){ int t = *a; *a = *b; *b = t;}int main(){ int a, b, c; scanf("%d%d%d", &a, &b, &c); if(a > b) swap(&a, &b); if(a > c) swap(&a, &c); if(b > c) swap(&b, &c); if(a + b <= c){ puts("not a triangle"); return 0; } if(a * a + b * b == c * c){ puts("yes"); }else{ puts("no"); } return 0;}/*执行结果5 4 3yes*/习题1-7
#includeint main(){ int year; scanf("%d", &year); if(year % 4 == 0 && year % 100 != 0 || year % 400 == 0){ puts("yes"); }else{ puts("no"); } return 0;}/*执行结果2000yes*/问题1
int类型的最大值为：2147483647，最小值为：-2147483648
问题2
C语言标准规定：float类型至少能表示6位有效数字，double至少能保持10位有效数字，但是64位系统至少能保存13位有效数字。
问题3
#include#includeint main(){ printf("float_true_min: %ef\n", FLT_TRUE_MIN); printf("float_min: %ef\n", FLT_MIN); printf("float_max: %ef\n", FLT_MAX); printf("double_true_min: %ef\n", DBL_TRUE_MIN); printf("double_min: %ef\n", DBL_MIN); printf("double_max: %ef\n", DBL_MAX); printf("long_double_true_min: %Lef\n", LDBL_TRUE_MIN); printf("long_double_min: %Lef\n", LDBL_MIN); printf("long_double_max: %Lef\n", LDBL_MAX); return 0;}/*执行结果float_true_min: 1.401298e-45ffloat_min: 1.175494e-38ffloat_max: 3.402823e+38fdouble_true_min: 4.940656e-324fdouble_min: 2.225074e-308fdouble_max: 1.797693e+308flong_double_true_min: 3.645200e-4951flong_double_min: 3.362103e-4932flong_double_max: 1.189731e+4932f*/问题4
逻辑运算符优先级! > && > ||
问题5
#includeint main(){ int a = 0, b = 0, x = 0, y = 0; if(a){ if(b){ x ++ ; }else{ y ++ ; } } return 0;}第二章 循环程序设计
输出结果文件快速对比:
cmdfc命令说明文档
fc file1 file2powershellCompare-Object的别名是diffCompare-Object命令说明文档
Compare-Object -ReferenceObject (Get-Content -encoding utf8 -Path ~/Desktop/hello.c) -DifferenceObject (Get-Content -encoding utf8 -Path ~/Desktop/hello.cpp)linux
diff file1 file2以上命令中linux中的diff命令相当好用，可以在Windows环境下安装Git然后在Git Bash中使用.
1.5 注解与习题
习题2-1：水仙花数
#includeint main(){ for(int i = 100; i <= 999; i ++ ){ int a = i / 100, b = i / 10 % 10, c = i % 10; if(i == a * a * a + b * b * b + c * c * c){ printf("%d\n", i); } } return 0;}/*执行结果153370371407*/习题2-2：韩信点兵
#includeint main(){ int a, b, c, cnt = 0; while(scanf("%d%d%d", &a, &b, &c) == 3){ for(int i = 10; i <= 100; i ++ ){ if(i % 3 == a && i % 5 == b && i % 7 == c){ printf("Case %d: %d\n", ++cnt, i); goto loop; } } printf("Case %d: No answer\n", ++cnt); loop:; // continue } return 0;}/*执行结果2 1 62 1 3Case 1: 41Case 2: No answer*/习题2-3：倒三角形
#includeint main(){ int n; scanf("%d", &n); for(int i = 0; i < n; i ++ ){ for(int j = 0; j < i; j ++ ) putchar(' '); for(int j = 0; j < 2 * (n - i) - 1; j ++ ){ putchar('*'); } puts(""); } return 0;}/*执行结果5********* ******* ***** *** **/习题2-4：子序列的和
#includeint main(){ int n, m, cnt = 0; while(scanf("%d%d", &n, &m) == 2 && (n || m)){ float sum = 0; for(int i = n; i <= m; i ++ ){ sum += 1.0 / i / i; } printf("Case %d: %.5f\n", ++cnt, sum); } return 0;}/*执行结果2 465536 6553600 0Case 1: 0.42361Case 2: 0.00001*/习题2-5：分数化小数
#includeint main(){ int a, b, c, cnt = 0; while(scanf("%d%d%d", &a, &b, &c) == 3 && (a || b || c)){ printf("Case %d: %.*f\n", ++cnt, c, (double)a / b); } return 0;}/*执行结果1 6 40 0 0Case 1: 0.1667*/习题2-6：排列
#include#includebool check(int x, int y, int z){ if(z > 987) return false; int a = x / 100, b = x / 10 % 10, c = x % 10; int d = y / 100, e = y / 10 % 10, f = y % 10; int g = z / 100, h = z / 10 % 10, i = z % 10; if(a == 0 || b == 0 || c == 0 || d == 0 || e == 0 || f == 0 || g == 0 || h == 0 || i == 0 || a == b || a == c || b == c || d == e || d == f || e == f || g == h || g == i || h == i){ return false; } return true;}int main(){ for(int i = 123; i <= 333; i ++ ){ int x = i, y = i * 2, z = i * 3; if(check(x, y, z)){ printf("%d %d %d\n", x, y, z); } } return 0;}/*执行结果123 246 369124 248 372127 254 381128 256 384129 258 387132 264 396139 278 417142 284 426143 286 429156 312 468157 314 471162 324 486163 326 489164 328 492173 346 519176 352 528178 356 534179 358 537182 364 546187 374 561189 378 567192 384 576193 386 579197 394 591198 396 594213 426 639214 428 642216 432 648218 436 654219 438 657231 462 693238 476 714241 482 723243 486 729246 492 738256 512 768263 526 789264 528 792271 542 813273 546 819281 562 843284 568 852287 574 861289 578 867291 582 873293 586 879297 594 891298 596 894312 624 936314 628 942316 632 948317 634 951319 638 957321 642 963324 648 972326 652 978327 654 981329 658 987*/题目1
// 任务1#includeint main(){ int n; scanf("%d", &n); for(int i = 1; i <= n; i ++ ){ printf("%d\n", i * 2); } return 0;}// 任务2#includeint main(){ int n; scanf("%d", &n); for(int i = 2; i <= 2 * n; i += 2){ printf("%d\n", i); } return 0;}题目2
#includeint main(){ for(double i = 0; i != 10; i += 0.1){ printf("%.1f\n", i); if(i > 10) break; } return 0;}/*输出结果0.00.10.20.30.40.5...10.010.1*/第三章 竞赛题目选讲
例题3-1
UVA-272 TeX中的引号
#include#includeint main(){ int c; bool q = true; while((c = getchar()) != EOF){ if(c == '"'){ printf("%s", q ? "``" : "''"); q = !q; }else{ printf("%c", c); } } return 0;}例题3-2
UVA-10082 WERTYU
#include#includeusing namespace std;int main(){ char s[] = "`1234567890-=QWERTYUIOP[]\\ASDFGHJKL;'ZXCVBNM,./"; char c; while((c = getchar()) != EOF){ auto i = strchr(s, c); if(i){ putchar(s[i - s - 1]); }else{ putchar(c); } }}例题3-3
UVA-401 回文词
#includeusing namespace std;const char *rev = "A 3 HIL JM O 2TUVWXY51SE Z008 "; const char *msg[] = {"is not a palindrome."/* 不是一个回文字符串 */, "is a regular palindrome."/* 回文字符串 */, "is a mirrored string.", "is a mirrored palindrome."};char r(char c){ if(isalpha(c)){ return rev[c - 'A']; } return rev[c - '0' + 25];}int main(){ char s[30]; while(scanf("%s", s) == 1){ int isPalindrome = 1, isMirrored = 1; int n = strlen(s); for(int i = 0; i < (n + 1) / 2; i ++ ){ if(s[i] != s[n - i - 1]) isPalindrome = 0; if(r(s[i]) != s[n - i - 1]) isMirrored = 0; } printf("%s -- %s\n\n", s, msg[2 * isMirrored + isPalindrome]); }}例题3-4
UVA-340 猜数字游戏的提示
#includeusing namespace std;const int N = 1e3 + 10;int a[N], b[N];int main(){ int n, cnt = 0; while(scanf("%d", &n), n){ printf("Game %d:\n", ++cnt); for(int i = 0; i < n; i ++ ) { scanf("%d", &a[i]); } while(true){ 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 k = 1; k <= 9; k ++ ){ int c1 = 0, c2 = 0; for(int i = 0; i < n; i ++ ){ if(a[i] == k) c1 ++ ; if(b[i] == k) c2 ++ ; } B += min(c1, c2); } printf(" (%d,%d)\n", A, B - A); } } return 0;}例题3-5
UVA-1583 生成元
#includeusing namespace std;const int N = 1e5 + 10;int a[N];int main(){ for(int i = 1; i < N; i ++ ){ int x = i, y = i; while(x){ y += x % 10; x /= 10; } if(a[y] == 0){ // 没被放过才可以放， a[y] = i; } } int n, m; scanf("%d", &n); while(n -- ){ scanf("%d", &m); printf("%d\n", a[m]); } return 0;}例题3-6
UVA-1583 环状序列
#includeusing namespace std;const int N = 1e2 + 10;char s[N];bool compare(int n, int p, int q){ 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 false;}int main(){ int T; scanf("%d", &T); while(T -- ){ scanf("%s", s); int n = strlen(s), ans = 0; for(int i = 1; i < n; i ++ ){ if(compare(n, i, ans)) ans = i; } for(int i = 0; i < n; i ++ ){ putchar(s[(i + ans) % n]); } puts(""); } return 0;}3.4 注解与习题
题目1：
输入一些数，统计个数
#includeusing namespace std;int main(){ int a, cnt = 0; while(scanf("%d", &a)){ cnt ++ ; } printf("%d", cnt); return 0;}// 不需要数组输入一些数，求最大值、最小值和平均数
#includeusing namespace std;int main(){ int a, mi = INT_MAX, ma = INT_MIN, sum = 0, cnt = 0; while(scanf("%d", &a) == 1){ mi = min(mi, a); ma = max(ma, a); sum += a; cnt ++ ; } printf("mi: %d, ma: %d, avg: %.2f", mi, ma, (double)sum / cnt); return 0;}// 不需要数组输入一些数，哪两个数最接近
#includeusing namespace std;const int N = 1e6 + 10;int a[N];int main(){ int cnt = 0, num1, num2, diff = INT_MAX; while(scanf("%d", &num1) == 1){ a[cnt ++ ] = num1; } printf("cnt: %d\n", cnt); for(int i = 0; i < cnt; i ++ ){ printf("%d ", a[i]); } puts(""); for(int i = 0; i < cnt; i ++ ){ for(int j = i + 1; j < cnt; j ++ ){ if(abs(a[i] - a[j]) < diff){ diff = abs(a[i] - a[j]); num1 = a[i], num2 = a[j]; } } } printf("num1: %d, num2: %d", num1, num2); return 0;}// 需要数组输入一些数，求第二大的数
#includeusing namespace std;int main(){ int mx = INT_MIN, secMax = mx, a; while(scanf("%d", &a) == 1){ if(a > mx){ secMax = mx; mx = a; }else{ secMax = max(secMax, a); } } printf("mx: %d, secMax: %d\n", mx, secMax); return 0;}// 不需要数组输入一些数，求它们的方差
#includeusing namespace std;const int N = 1e6 + 10;double a[N];int main(){ double s2, avg, t, sum = 0; int cnt = 0; while(scanf("%lf", &t) == 1){ a[cnt ++ ] = t; sum += t; } avg = sum / cnt; for(int i = 0; i < cnt; i ++ ){ s2 += (a[i] - avg) / cnt * (a[i] - avg); } printf("avg: %.2f, s2: %.2f\n", avg, s2); return 0;}// 需要数组输入一些数，统计不超过平均数的个数
#includeusing namespace std;const int N = 1e6 + 10;double a[N];int main(){ double avg, t, sum = 0; int cnt = 0, ans = 0; while(scanf("%lf", &t) == 1){ a[cnt ++ ] = t; sum += t; } avg = sum / cnt; for(int i = 0; i < cnt; i ++ ){ if(a[i] <= avg) ans ++ ; } printf("%d\n", ans); return 0;}// 需要数组题目2：
#include#include#define N (int)(1e7 + 10)char s[N]; // 导致程序无法运行int main(){ scanf("%s", s); int cnt = 0, n = strlen(s); // 导致程序效率低下 for(int i = 0; i < n; i ++ ){ if(s[i] == '1') cnt ++ ; // 导致结果不正确 } printf("%d\n", cnt); return 0;}习题3-1
UVA-1585 得分
#includeusing namespace std;const int N = 1e2 + 10;char s[N];int main(){ int T, n; scanf("%d", &T); while(T -- ){ scanf("%s", s); n = strlen(s); int ans = 0, cnt = 0; for(int i = 0; i < n; i ++ ){ if(s[i] == 'O'){ ans += ++cnt; }else{ cnt = 0; } } printf("%d\n", ans); } return 0;}习题3-2
UVA-1586 分子量
#includeusing namespace std;const int N = 1e2 + 10;char s[N];double m[] = {12.01, 1.008, 16.00, 14.01}; double getMol(char c){ switch(c){ case 'C': return m[0]; case 'H': return m[1]; case 'O': return m[2]; case 'N': return m[3]; } return m[0];}int main(){ int T, n; scanf("%d", &T); while(T -- ){ scanf("%s", s); n = strlen(s); double sum = 0; for(int i = 0; i < n; i ++ ){ int num = 0, j = i + 1; while(j = '0' && s[j] <= '9'){ num = num * 10 + (s[j] - '0'); j ++ ; } if(num == 0){ sum += getMol(s[i]); }else{ sum += getMol(s[i]) * num; } i = j - 1; } printf("%.3f\n", sum); } return 0;}习题3-3
UVA-1225 数数字
#includeusing namespace std;int main(){ int T, n, a[10]; scanf("%d", &T); while(T -- ){ memset(a, 0, sizeof a); scanf("%d", &n); for(int i = 1; i <= n; i ++ ){ int t = i; while(t){ a[t % 10] ++ ; t /= 10; } } for(int i = 0; i < 9; i ++ ){ printf("%d ", a[i]); } printf("%d\n", a[9]); } return 0;}习题3-4
UVA-455 周期串
#includeusing namespace std;const int N = 1e2;char s[N];int main(){ int T; scanf("%d", &T); while(T -- ){ scanf("%s", s); int n = strlen(s); for(int i = 1; i <= n; i ++ ){ if(n % i == 0){ for(int j = i; j < n; j += i){ for(int k = 0; k < i; k ++ ){ if(s[k] != s[j + k]){ goto loop; // continue } } } printf("%d\n%c", i, T ? '\n' : '\0'); goto l; // break; } if(i == n) { printf("%d\n%c", i, T ? '\n' : '\0'); break; } loop:; } l:; } return 0;}习题3-5
UVA-227 谜题
#includeusing namespace std;const int N = 10;char s[N][N];bool move(char c){ // 找空格 int i = 0, j = 0; for(i = 0; i < 5; i ++ ){ for(j = 0; j < 5; j ++ ){ if(s[i][j] == ' ') goto loop; } } loop:; // i, j坐标就是空格 switch(c){ case 'A': // 上 if(i - 1 = 5) return false; swap(s[i][j], s[i + 1][j]); return true; case 'L': // 左 if(j - 1 = 5) return false; swap(s[i][j], s[i][j + 1]); return true; } return false;}void print(){ for(int i = 0; i < 5; i ++ ){ printf("%c", s[i][0]); for(int j = 1; j < 5; j ++ ){ printf(" %c", s[i][j]); } puts(""); }}void format(){ for(int i = 0; i < 5; i ++ ){ for(int j = 0; j PQRS\10 format(); if(T) puts(""); printf("Puzzle #%d:\n", ++T); char c; while((c = getchar()) && c != '0'){ if(c == '\n' || c == '\r') continue; if(!move(c)){ printf("This puzzle has no final configuration.\n"); cnt = -1; while((c = getchar()) && c != '0') continue; getchar(); goto loop; } } print(); cnt = -1; getchar(); } loop:; } return 0;}这题真的很烦😡
习题3-6
UVA-227 谜题
TODO