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

这篇具有很好参考价值的文章主要介绍了《算法竞赛入门经典(第二版)》学习笔记。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

算法竞赛入门经典(第二版)学习笔记

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

第一章 程序设计入门

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 谜题

#include<bits/stdc++.h>
using namespace std;
const int N = 15;
char s[N][N];
int arr[N][N];
bool st[N][N];
int main(int, char**){
    int n, m, T = 0;
    while(scanf("%d", &n) && n){
        memset(arr, 0, sizeof arr);
        scanf("%d\n", &m);
        if(T) puts("");
        printf("puzzle #%d:\n", ++T);
        for(int i = 0; i < n; i ++ ) fgets(s[i], N, stdin);
        int cnt = 0;
        for(int i = 0; i < n; i ++ ){
            for(int j = 0; j < m; j ++ ){
                if(s[i][j] != '*' && (i == 0 || j == 0 || s[i][j - 1] == '*' || s[i - 1][j] == '*')) arr[i][j] = ++cnt;
            }
        }
        // for(int i = 0; i < n; i ++ ) printf("%s", s[i]);
        // for(int i = 0; i < n; i ++ ){
        //     for(int j = 0; j < m; j ++ ){
        //         printf("%d ", arr[i][j]);
        //     }
        //     puts("");
        // }
        // 横向
        puts("Across");
        memset(st, 0, sizeof st);
        for(int i = 0; i < n; i ++ ){
            for(int j = 0; j < m; j ++ ){
                if(!st[i][j] && arr[i][j]){
                    int t = j;
                    printf("%3d.", arr[i][j]);
                    while(t < m && s[i][t] != '*') {
                        st[i][t] = true;
                        putchar(s[i][t]);
                        t ++ ;
                    }
                    puts("");
                }
            }
        }
        // 纵向
        puts("Down");
        memset(st, 0, sizeof st);
        for(int i = 0; i < n; i ++ ){
            for(int j = 0; j < m; j ++ ){
                if(!st[i][j] && arr[i][j]){
                    int t = i;
                    printf("%3d.", arr[i][j]);
                    while(t < n && s[t][j] != '*') {
                        st[t][j] = true;
                        putchar(s[t][j]);
                        t ++ ;
                    }
                    puts("");
                }
            }
        }
    }   
}

习题3-7
UVA-1368 DNA序列

#include<bits/stdc++.h>
using namespace std;
typedef pair<char, int> PCI;
const int N = 55, M = 1e3 + 10;
char s[N][M];
int main(int, char**){
    auto compare = [](const PCI &p1, const PCI &p2) -> bool {
        if(p1.second == p2.second) return p1.first < p2.first;
        return p1.second > p2.second;
    };
    int T, n, m;
    scanf("%d", &T);
    while(T -- ){
        scanf("%d%d", &n, &m);
        for(int i = 0; i < n; i ++ ) scanf("%s", s[i]);
        string ans;
        int cnt = 0;
        for(int i = 0; i < m; i ++ ){
            unordered_map<char, int> hash;
            for(int j = 0; j < n; j ++ ){
                hash[s[j][i]] ++ ;
            }
            vector<PCI> v(hash.begin(), hash.end());
            sort(v.begin(), v.end(), compare);
            for(auto it = v.begin() + 1; it != v.end(); ++it){
                cnt += it -> second;
            }
            ans.push_back(v.begin() -> first);
        }
        printf("%s\n%d\n", ans.c_str(), cnt);
    }
}

习题3-8
UVA-202 循环小数

TODO

习题3-9
UVA-1368 DNA序列

TODO

习题3-10
UVA-1368 DNA序列

TODO

习题3-11
UVA-1368 DNA序列

TODO

习题3-12
UVA-1368 DNA序列文章来源地址https://www.toymoban.com/news/detail-770344.html

TODO

到了这里,关于《算法竞赛入门经典(第二版)》学习笔记的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【python快速编程入门(第二版)黑马程序员课后编程题】

    第二章  python基础 1、课本33页练习:求圆的半径和面积; 用户输入圆的半径,输出圆的直径和面积。面积公式:s=π*r*r 2、#课本33页练习:计算运输次数; #煤场有29.5t,4t运了3次,其余用2.5t车运,还需几次才能运完 第三章  流程控制 1、#课本44页练习:用while循环输出100以内

    2024年02月04日
    浏览(51)
  • 系统集成项目管理工程师 软考中级 第三章重点汇总笔记(书本参照 第二版)

    第三章 信息系统的生命周期(p133) (1)立项阶段:即概念阶段或需求阶段,这一阶段根据用户业务发展和经营管理的需要,提出建设信息系统的初步构想;然后对企业信息系统的需求进行深入调研和分析,形成《需求规格说明书》并确定立项。 (2)开发阶段:以立项阶段所做的需

    2023年04月22日
    浏览(68)
  • 《Python程序设计与算法基础教程(第二版)》江红 余青松 课后选择题 课后填空题答案

    Python语言属于 C A.机器语言 B.汇编语言 C.高级语言 D.以上都不是 在下列选项中,不属于Python特点的是 B C.可移植性 D.免费和开源 A.面向对象 B.运行效率高 在下列选项中, A 是最信用的Pyton版本,也称之为Casiseyrhoip A. CPython B. Jython C. IronPython D. PyPy Python内置的集成开发工具是 D

    2024年02月07日
    浏览(44)
  • 机器学习笔记之优化算法(十八)经典牛顿法

    本节将介绍 优化算法——经典牛顿法 ( Newton Method ) (text{Newton Method}) ( Newton Method ) 。 下降方向 在线搜索方法——方向角度中介绍了 下降方向 ( Descent Direction ) (text{Descent Direction}) ( Descent Direction ) 的概念。首先,通过推导得到 如果 更新方向 P k mathcal P_k P k ​ 与梯度方向

    2024年02月11日
    浏览(35)
  • 【UnityShader入门精要学习笔记】第二章(3)章节答疑

    本系列为作者学习UnityShader入门精要而作的笔记,内容将包括: 书本中句子照抄 + 个人批注 项目源码 一堆新手会犯的错误 潜在的太监断更,有始无终 总之适用于同样开始学习Shader的同学们进行有取舍的参考。 (PS:章节答疑不是我答,是原作者对一些比较容易产生困惑的地

    2024年02月03日
    浏览(53)
  • 【书籍】强化学习第二版(英文版电子版下载、github源码)-附copilot翻译的中英文目录...

    英文原版书籍下载:http://incompleteideas.net/book/the-book-2nd.html 作者: 理查德·S·萨顿是阿尔伯塔大学计算机科学教授和强化学习与人工智能 AITF 主席,也是 DeepMind 的杰出研究科学家。 安德鲁·G·巴托是马萨诸塞大学阿默斯特分校计算机与信息科学学院的荣誉退休教授。 描述:

    2024年01月18日
    浏览(52)
  • 《MetaGPT智能体开发入门》学习笔记 第一章第二章

    使用从 - 通过github仓库获取MetaGPT 代码拉下来后在config文件夹中配置chatGPT key 使用的python环境为3.9.2 metaGPT代码下载后在metagpt文件夹中找statup.py文件,运行以下命令,我是没有成功可能是chatgpt没钱 智能体 = LLM+观察+思考+行动+记忆 多智能体 = 智能体+环境+SOP+评审+路由+订阅+经

    2024年01月17日
    浏览(56)
  • 【UnityShader入门精要学习笔记】第二章(2)GPU流水线

    本系列为作者学习UnityShader入门精要而作的笔记,内容将包括: 书本中句子照抄 + 个人批注 项目源码 一堆新手会犯的错误 潜在的太监断更,有始无终 总之适用于同样开始学习Shader的同学们进行有取舍的参考。 在上节笔记中,我们学习了图像渲染流水线的基本过程,从应用

    2024年02月22日
    浏览(44)
  • 【UnityShader入门精要学习笔记】第二章(1)了解渲染流水线

    本系列为作者学习UnityShader入门精要而作的笔记,内容将包括: 书本中句子照抄 + 个人批注 项目源码 一堆新手会犯的错误 潜在的太监断更,有始无终 总之适用于同样开始学习Shader的同学们进行有取舍的参考。 什么是流水线?书中举了一个生产洋娃娃的例子。一个洋娃娃的

    2024年01月25日
    浏览(42)
  • 算法竞赛备赛之经典基础算法训练提升,暑期集训营培训

      目录 1.排序 1.1.快速排序 1.2.归并排序 2.二分 2.1.整数 2.2.浮点数 3.高精度 3.1.高精度加法 3.2.高精度减法 3.3.高精度乘法 3.4.高精度除法 4.前缀和 5.差分 6.双指针算法 7.位运算 8.离散化 8.1.unique函数实现 9.区间合并 快速排序的基本思想来自于分治。 首先,确定分界点的方法:

    2024年02月15日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包