C++算法之旅、01 入门篇

使用胡凡主编的《算法笔记》教材。题目均为第三章题目。

TEST

// Problem Address

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>

int main() { return 0; }

PAT_B1001 3n+1

// https://pintia.cn/problem-sets/994805260223102976/exam/problems/994805325918486528

#include <cstdio>

int main() {
    int steps = 0, n;
    scanf("%d", &n);
    while (n != 1) {
        if (n % 2 == 0) {
            n /= 2;
        } else {
            n = (3 * n + 1) / 2;
        }
        steps++;
    }
    printf("%d", steps);
    return 0;
}

PAT_B1032 挖掘机

// https://pintia.cn/problem-sets/994805260223102976/exam/problems/994805289432236032

#include <cstdio>
// #include <cstring>

int main() {
    int n, id = 1, score[100010] = {0}, score_, id_;
    // memset(score, 0, sizeof(score));
    scanf("%d", &n);
    while (n--) {
        scanf("%d%d", &id_, &score_);
        score[id_] += score_;
        if (score[id_] > score[id]) {
            id = id_;
        }
    }
    printf("%d %d\n", id, score[id]);
}

CODEUP_1934 找x

// http://codeup.hustoj.com/problem.php?cid=100000576&pid=1

#include <cstdio>

int main() {
    int i, n, x, nums[210];

    while (scanf("%d", &n) != EOF) {
        for (i = 0; i < n; i++) {
            scanf("%d", &nums[i]);
        }
        scanf("%d", &x);
        for (i = 0; i < n; i++) {
            if (nums[i] == x) {
                printf("%d\n", i);
                break;
            }
        }
        if (i == n) {
            printf("-1\n");
        }
    }

    return 0;
}

PAT_B1036 奥巴马

// https://pintia.cn/problem-sets/994805260223102976/exam/problems/994805285812551680

#include <cstdio>

int main() {
    int cols, rows;
    char c;
    scanf("%d %c", &cols, &c);  // %c 也会读空格,所以中间加了个空格
    if (cols % 2 == 1) {
        rows = cols / 2 + 1;
    } else {
        rows = cols / 2;
    }
    for (int i = 0; i < cols; i++) {
        printf("%c", c);
    }
    printf("\n");
    for (int i = 0; i < rows - 2; i++) {
        printf("%c", c);
        for (int i = 0; i < cols - 2; i++) {
            printf(" ");
        }
        printf("%c\n", c);
    }
    for (int i = 0; i < cols; i++) {
        printf("%c", c);
    }
    printf("\n");

    return 0;
}

CODEUP_1928 日期差值

// http://codeup.hustoj.com/problem.php?cid=100000578&pid=0

#include <cstdio>

bool isRunYear(int year) {
    return (year % 4 == 0 && year % 100 != 0) || year % 400 == 0;
}

int month[13][2] = {{0, 0},   {31, 31}, {28, 29}, {31, 31}, {30, 30},
                    {31, 31}, {30, 30}, {31, 31}, {31, 31}, {30, 30},
                    {31, 31}, {30, 30}, {31, 31}};

int main() {
    int t1, t2, y1, y2, m1, m2, d1, d2;
    while (scanf("%d%d", &t1, &t2) != EOF) {
        int total = 1;
        if (t2 > t1) {
            y1 = t2;
            t2 = t1;
            t1 = y1;
        }
        y1 = t1 / 10000, y2 = t2 / 10000;
        m1 = t1 % 10000 / 100, m2 = t2 % 10000 / 100;  // 去除年份
        d1 = t1 % 100, d2 = t2 % 100;
        while (y1 != y2 || m1 != m2 || d1 != d2) {  // 不是 &&
            // printf("%d %d %d\n", y2, m2, d2);
            total++;
            if (d2 != month[m2][isRunYear(y2)]) {
                d2 += 1;
            } else {
                d2 = 1;
                m2 += 1;
                if (m2 == 13) {
                    y2 += 1;
                    m2 = 1;
                }
            }
        }
        printf("%d\n", total);
    }
    return 0;
}

PAT_B1022 D进制的A+B

// https://pintia.cn/problem-sets/994805260223102976/exam/problems/994805299301433344

// 考查 除基取余法
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>

int main() {
    int a, b, n, index = 0, ans[32] = {0};
    scanf("%d%d%d", &a, &b, &n);
    int d = a + b;
    // 考虑 d 为 0 的情况使用 do while
    do {
        ans[index++] = d % n;
        d /= n;
    } while (d != 0);
    for (int i = index - 1; i >= 0; i--) {
        printf("%d", ans[i]);
    }
    printf("\n");
    return 0;
}

CODEUP_5901 回文串

// http://codeup.hustoj.com/problem.php?cid=100000580&pid=8

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>

int main() {
    char str[256];
    scanf("%s", str);
    int len = strlen(str);
    for (int i = 0; i < len / 2; i++) {
        if (str[i] != str[len - 1 - i]) {
            printf("NO\n");
            return 0;
        }
    }
    printf("YES\n");

    return 0;
}

PAT_B1009 说反话

解法一

// https://pintia.cn/problem-sets/994805260223102976/exam/problems/994805314941992960

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>

int main() {
    char words[80][80];
    int index = 0;

    while (scanf("%s", words[index]) !=
           EOF) {  // 如果index++放在scanf,EOF时index也会++,下面for需要改为
                   // i = index - 2
        index++;
    }

    for (int i = index - 1; i >= 0; i--) {
        printf("%s", words[i]);
        if (i) {
            printf(" ");
        }
    }

    return 0;
}

解法二

// https://pintia.cn/problem-sets/994805260223102976/exam/problems/994805314941992960

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>

int main() {
    char str[100];
    char words[80][80];
    int index = 0;

    fgets(str, 100, stdin);  // PAT 不再使用 gets
    int i = 0;
    while (str[i] != 10) {  // '\n'
        i++;
    }
    str[i] = 0;  // '\0'

    int wordIndex = 0;
    for (int i = 0; i < strlen(str); i++) {
        if (str[i] != 32) {
            words[index][wordIndex++] = str[i];
        } else {
            index++;
            wordIndex = 0;
        }
    }
    for (int i = index--; i >= 0; i--) {
        printf("%s", words[i]);
        if (i) {
            printf(" ");
        }
    }
    return 0;
}

弃用gets改用fgets

C++中使用fgets函数代替gets函数（PAT中gets函数编译失败解决方案） - 知乎 (zhihu.com)

C语言通过gets和gets_s分别实现读取含空格的字符串_C 语言_脚本之家 (jb51.net)

PAT中gets函数不能使用，用fgets、gets_Circle-C的博客-CSDN博客