CSDN

《算法竞赛入门经典（第二版）》学习笔记

2024-01-01 22:34 由 爱情丶眨眼而去 发表于 #其他

算法竞赛入门经典（第二版）学习笔记

本文是《算法竞赛入门经典（第二版）》这本书中的学习总结，如有不足欢迎提出宝贵意见。

第一章 程序设计入门

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;
}
/*
执行结果
-1
30
2
1
*/

实验5 ~ 6

#include<stdio.h>
int 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.60
0.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<stdio.h>
#include<math.h>
int 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.000000
12345654321.000000
12345678987654320.000000 double在此环境表示16位有效数字
*/

实验A3

#include<stdio.h>
#include<math.h>
int main(){
        printf("%f\n", sqrt(-10));
        return 0;
}
/*
执行结果
nan
*/

实验A4

#include<stdio.h>
#include<math.h>
int main(){
        printf("%f\n", 1.0 / 0.0);
        printf("%f\n", 0.0 / 0.0);
        return 0;
}
/*
执行结果
inf
nan
*/

实验A5

#include<stdio.h>
#include<math.h>
int main(){
        printf("%d\n", 1 / 0);
        return 0;
}
/*
执行结果
*/

实验B1 ~ B4
略.
习题1-1

#include<stdio.h>
int 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

#include<stdio.h>
int main(){
        double f;
        scanf("%lf", &f);
        printf("%.3f\n", 5 * (f - 32) / 9);
        return 0;
}
/*
执行结果
1         输入
-17.222   输出
*/

习题1-3

#include<stdio.h>
int main(){
        int n;
        scanf("%d", &n);
        printf("%d\n", n * (n + 1) / 2);
        return 0;
}
/*
执行结果
100    输入
5050   输出
*/

习题1-4

#include<stdio.h>
#include<math.h>
#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

#include<stdio.h>
int 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;
}
/*
执行结果
4
361.00
*/

习题1-6

#include<stdio.h>
void 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 3
yes
*/

习题1-7

#include<stdio.h>
int main(){
        int year;
        scanf("%d", &year);
        if(year % 4 == 0 && year % 100 != 0 || year % 400 == 0){
                puts("yes");
        }else{
                puts("no");
        }
        return 0;
}
/*
执行结果
2000
yes
*/

问题1
int类型的最大值为：2147483647，最小值为：-2147483648
问题2
C语言标准规定：float类型至少能表示6位有效数字，double至少能保持10位有效数字，但是64位系统至少能保存13位有效数字。
问题3

#include<stdio.h>
#include<float.h>
int 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-45f
float_min: 1.175494e-38f
float_max: 3.402823e+38f
double_true_min: 4.940656e-324f
double_min: 2.225074e-308f
double_max: 1.797693e+308f
long_double_true_min: 3.645200e-4951f
long_double_min: 3.362103e-4932f
long_double_max: 1.189731e+4932f
*/

问题4
逻辑运算符优先级! > && > ||
问题5

#include<stdio.h>
int main(){
        int a = 0, b = 0, x = 0, y = 0;
        if(a){
                if(b){
                        x ++ ;
                }else{
                        y ++ ;
                }
        }
    return 0;
}

第二章 循环程序设计

输出结果文件快速对比:

  1. cmd
    fc命令说明文档
fc file1 file2
  1. powershell
    Compare-Object的别名是diff
    Compare-Object命令说明文档
Compare-Object -ReferenceObject (Get-Content -encoding utf8 -Path ~/Desktop/hello.c) -DifferenceObject (Get-Content -encoding utf8 -Path ~/Desktop/hello.cpp)
  1. linux
diff file1 file2

以上命令中linux中的diff命令相当好用，可以在Windows环境下安装Git然后在Git Bash中使用.

1.5 注解与习题

习题2-1：水仙花数

#include<stdio.h>
int 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;
}
/*
执行结果
153
370
371
407
*/

习题2-2：韩信点兵

#include<stdio.h>
int 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 6
2 1 3
Case 1: 41
Case 2: No answer
*/

习题2-3：倒三角形

#include<stdio.h>
int 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：子序列的和

#include<stdio.h>
int 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 4
65536 655360
0 0
Case 1: 0.42361
Case 2: 0.00001
*/

习题2-5：分数化小数

#include<stdio.h>
int 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 4
0 0 0
Case 1: 0.1667
*/

习题2-6：排列

#include<stdio.h>
#include<stdbool.h>
bool 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 369
124 248 372
127 254 381
128 256 384
129 258 387
132 264 396
139 278 417
142 284 426
143 286 429
156 312 468
157 314 471
162 324 486
163 326 489
164 328 492
173 346 519
176 352 528
178 356 534
179 358 537
182 364 546
187 374 561
189 378 567
192 384 576
193 386 579
197 394 591
198 396 594
213 426 639
214 428 642
216 432 648
218 436 654
219 438 657
231 462 693
238 476 714
241 482 723
243 486 729
246 492 738
256 512 768
263 526 789
264 528 792
271 542 813
273 546 819
281 562 843
284 568 852
287 574 861
289 578 867
291 582 873
293 586 879
297 594 891
298 596 894
312 624 936
314 628 942
316 632 948
317 634 951
319 638 957
321 642 963
324 648 972
326 652 978
327 654 981
329 658 987
*/

题目1

// 任务1
#include<stdio.h>
int main(){
        int n;
        scanf("%d", &n);
        for(int i = 1; i <= n; i ++ ){
                printf("%d\n", i * 2);
        }
    return 0;
}
// 任务2
#include<stdio.h>
int main(){
        int n;
        scanf("%d", &n);
        for(int i = 2; i <= 2 * n; i += 2){
                printf("%d\n", i);
        }
    return 0;
}

题目2

#include<stdio.h>
int main(){
        for(double i = 0; i != 10; i += 0.1){
                printf("%.1f\n", i);
                if(i > 10) break;
        }
    return 0;
}
/*
输出结果
0.0
0.1
0.2
0.3
0.4
0.5
...
10.0
10.1
*/

第三章 竞赛题目选讲

例题3-1
UVA-272 TeX中的引号

#include<stdio.h>
#include<stdbool.h>
int 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<cstdio>
#include<cstring>
using 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 回文词

#include<bits/stdc++.h>
using 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 猜数字游戏的提示

#include<bits/stdc++.h>
using 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 生成元

#include<bits/stdc++.h>
using 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 环状序列

#include<bits/stdc++.h>
using 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：
输入一些数，统计个数

#include<bits/stdc++.h>
using namespace std;
int main(){
    int a, cnt = 0;
    while(scanf("%d", &a)){
        cnt ++ ;
    }
    printf("%d", cnt);
    return 0;
}
// 不需要数组

输入一些数，求最大值、最小值和平均数

#include<bits/stdc++.h>
using 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;
}
// 不需要数组

输入一些数，哪两个数最接近

#include<bits/stdc++.h>
using 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;
}
// 需要数组

输入一些数，求第二大的数

#include<bits/stdc++.h>
using 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;
}
// 不需要数组

输入一些数，求它们的方差

#include<bits/stdc++.h>
using 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;
}
// 需要数组

输入一些数，统计不超过平均数的个数

#include<bits/stdc++.h>
using 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<cstdio>
#include<cstring>
#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 得分

#include<bits/stdc++.h>
using 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 分子量

#include<bits/stdc++.h>
using 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 < n && s[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 数数字

#include<bits/stdc++.h>
using 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 周期串

#include<bits/stdc++.h>
using 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 谜题

#include<bits/stdc++.h>
using 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 < 0) return false;
            swap(s[i][j], s[i - 1][j]);
            return true;
        case 'B': // 下
            if(i + 1 >= 5) return false;
            swap(s[i][j], s[i + 1][j]);
            return true;
        case 'L': // 左
            if(j - 1 < 0) return false;
            swap(s[i][j], s[i][j - 1]);
            return true;
        case 'R': // 右
            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 < 5; j ++ ){
            if(s[i][j] == '\n')  s[i][j] = ' ';
        }
    }
}
int main(){
    int cnt = -1, T = 0;
    while(fgets(s[ ++ cnt], N, stdin) && s[cnt][0] != 'Z'){ // fgets 会读入换行符
        if(cnt == 4){
            // 先格式化一下, 例如 PQRS\n -> 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

热门相关：万道龙皇   都市最强小村医   都市最强小村医   我有一个进化点   贴身侍卫