刷题心得-长期更新

P5738-歌唱比赛

在定义 num[N] 数组前必须对 N 赋值, 否则在 GCC 编译器，并且启用了 -std=gnu99 选项的情况下

int n;
int num[n]; //n未赋值

不会报错提醒. (~~没有发现这一点导致数组越界把我折磨了十几分钟~~)

在使用的是 GCC 编译器，并且启用了 -std=gnu99 选项的情况下，会使用 GNU 扩展.

在 GNU 扩展中，允许使用未初始化的变量作为数组的大小，这与 C99 标准不符.

所以在写数组定义前应该先定义 N 的值.

const int N = 110;
int num[N];

P1601-高精度加法

高精度加法步骤:

按位将字符串a, b逆序读入数组numa, numb中
按位计算numa[i], numb[i]的和并按位存入数组num[i]中
按位判断num[i]是否>= 10, 是则进位(num[i + 1] += num[i] / 10), 再将num[i]的十位截断(num[i] %= 10)
判断最后一位是否进位, 是则将结果位数+1(n++)
逆序输出num

#include <iostream>
#include <string>
using namespace std;

const int N = 1e3 + 10;

int main() {
    string a, b;
    int n;
    int numa[N], numb[N], num[N] = {0};

    cin >> a >> b;

    // 将字符串a, b逆序输入数组numa, numb中
    for (int i = 0; i < a.length(); i++) {
        numa[a.length() - i - 1] = a[i] - '0';
    }
    for (int i = 0; i < b.length(); i++) {
        numb[b.length() - i - 1] = b[i] - '0';
    }

    // 计算numa, numb各位之和
    n = a.length() > b.length() ? a.length() : b.length();
    for (int i = 0; i < n; i++) {
        num[i] = numa[i] + numb[i];
    }

    // 当某一位上的数字>=10时, 进位, 否则截断
    for (int i = 0; i < n; i++) {
        if (num[i] >= 10) {
            num[i + 1] = num[i + 1] + num[i] / 10;
            num[i] = num[i] % 10;
        }
    }

    // 如果最后一位有进位, 则结果位数+1
    if (num[n] != 0) {
        n++;
    }

    // 逆序输出num, 既为答案
    for (int i = n - 1; i >= 0; i--) {
        cout << num[i];
    }

    return 0;
}

二分查找模板

前提: num[]单调不减.

此处参考了 up 主: 五点七边和 up 主: 一只会 code 的金鱼的相关解答, 万分感谢

题目: 输出数字 val 在数组序列中第一次出现的下标, 如果没有找到的话输出-1.

int binary_search(vector<int> &num, int n, int val) {
    int i = -1, j = n;
    while (i + 1 != j) {
        int mid = i + (j - i) / 2; // 防止 int 溢出
        if (num[mid] < val) // 满足条件的mid及其左侧为蓝色部分
            i = mid;
        else
            j = mid;        // mid右侧为红色部分
    }
    // 退出循环后, 蓝色部分数字全部满足小于val(<val), 红色部分则全部满足不小于val(>=val).
    if (num[j] == val) // 红色部分第一个数字(num[j])既为不小于val(>=val)的第一个数字, 判断其是否==val
        return j; // 返回等于val的第一个数字的下标.
    else
        return -1;
}

根据题目要求不同, 通常会改变循环内部if过改变循环外部if或return的值, 例如:

例题: 返回比 val 小的最后一个数字的下标, 如果没有找到的话返回-1

    // 前段与上例相同
    if (i != -1) // i == -1时说明红色部分为整个数组, 不存在蓝色部分, 自然不能返回.
        return i; // 蓝色部分最后一个数字(num[i])即为小于val(<val)的最后一个数字.
    else // 此处虽然不用添加else便可完成返回-1的目的, 但为了与其它情况保持相同, 便不删去这两行
        return -1

例题: 返回比 val 大的第一个数字的下标, 如果没有找到的返回-1

    if (j != n) // j == n时说明蓝色部分为整个数组, 不存在红色部分, 自然不能返回.
        return j; // 红色部分第一个数字(num[j])即为不小于val(<val)的最后一个数字.
    else
        return -1

P1014-Cantor 表

已知所示金字塔数字为:

1/1
1/2 2/1
3/1 2/2 1/3
1/4 2/3 3/2 4/1
5/1 4/2 3/3 2/4 1/5

要求输出表中第 n 项.

void function(int n) {
    int count = 1;
    while (n > count) { // count为n所在的行, n变为n所在的列
        n = n - count;
        count++;
    }
    if (count % 2 == 0) { // 如果n所在的行是偶数
        cout << n << "/" << count - n + 1; // n = 2: 1/2 2/1
    } else { // 如果n所在的行是奇数
        cout << count - n + 1 << "/" << n; // n = 3: 3/1 2/2 1/3
        // count - n + 1即为列的逆序(反着排)
    }
}

P2141-珠心算测验

std::sort的用法:

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n = 7;
    vector<int> arr = {1, 9, 1, 9, 8, 1, 0};
    sort(arr.begin(), arr.end());
    // arr = {0, 1, 1, 1, 8, 9, 9}
}

过滤空格

题目: 给你一个字符串，要求你过滤掉空格和换行，其余字符的长度。

直接使用 cin 读取字符串会在 遇到空格和换行时停止读取 ，所以我们需要用 getline 函数来读取题目中的字符串

getline 代码示例，输入字符串 s

getline(cin, s);

读取字符串后我们需要看字符串的每一位，如果符合要求，那么就将计数变量 ans 加上 1 最后输出 ans 即可。

递推与递归

1. 全排列代码-全排列问题

void dfs(int x) { // x: 当前处理的位置
    if (x > n) { 输出排列; return; }
    for (int i=1; i<=n; i++) { // 遍历所有数字
        if (!st[i]) {          // 选择未使用的数字
            st[i] = true;
            arr[x] = i;        // 填入当前位置
            dfs(x+1);          // 处理下一个位置
            st[i] = false;     // 回溯
        }
    }
}

特点：

递归参数 x 表示位置，逐个填充。

使用 st[] 数组标记已使用的数字，确保不重复。

循环遍历所有可能的数字，保证每个位置尝试所有可能性。

输出顺序：严格按字典序（通过固定位置顺序+从小到大选择数字）。

2. 子集代码

void dfs(int x) { // x: 当前处理的元素
    if (x > n) { 输出子集; return; }
    // 选择当前元素
    st[x] = 1;
    dfs(x+1);    // 处理下一个元素
    st[x] = 0;   // 回溯
    // 不选择当前元素
    dfs(x+1);
}

特点：

递归参数 x 表示元素索引，逐个决策选/不选。

无循环，每个元素直接分两种情况递归。

使用 st[] 数组记录元素是否被选中。

输出顺序：按元素索引顺序（如 1→2→3 先选1再选2）。

3. 组合代码-组合的输出

void dfs(int x, int start) { // x: 当前处理的位置；start: 起始元素
    if (x > r) { 输出组合; return; }
    for (int i=start; i<=n; i++) { // 从start开始遍历
        arr[x] = i;            // 选择当前元素
        dfs(x+1, i+1);         // 下一层从i+1开始，避免重复
    }
}

特点：

递归参数 x（位置）和 start（起始元素）。

循环从 start 开始，确保组合内元素递增（避免重复）。

无需标记数组，通过 start 控制选择范围。

输出顺序：按递增顺序（如 123,124,125…）。

关键差异对比

-2025.2.3 04:13 Marlin 于家中编

"Hello Luogu"