算法题解2025-08-25约 1861 字

牛客周赛 Round 106 赛后题解复盘

比赛信息

比赛名称：牛客周赛 Round 106
比赛时间：2025-08-25 19:00 ~ 21:00
个人结果：AC 4 / 6，排名 203 / 920，用时 1h45min
涉及算法：模拟、枚举、预处理、贪心

整体复盘

这场比赛整体难度大致在 Easy 到 Medium 之间，前两题偏基础模拟和结论题，C、D 需要更明确的规律观察。我的主要问题不是完全不会，而是对题目规律的抽象速度还不够快，导致后续 E、F 没有足够时间继续推进。

本场比较值得记录的点有三个：

A/B 题需要快速稳定 AC，不能在基础题上消耗太多时间。
C 题的核心是把问题压缩到个位数状态，而不是暴力枚举原始区间。
D 题需要先发现操作会进入循环，再把每个数可达的状态预处理出来。

Problem A：小苯的方格覆盖

题目信息

难度：Easy
状态：1 次 AC
用时：2min
题目链接：小苯的方格覆盖

题意简述

给定一个 3 * n 的矩形，使用若干个 1 * 2 的小方块覆盖，方向不限。判断是否可以恰好覆盖整个矩形。

核心思路

每个小方块覆盖 2 个格子，所以总格子数必须是偶数。

矩形共有 3 * n 个格子。因为 3 是奇数，所以 3 * n 的奇偶性完全取决于 n。因此：

n 为偶数时，总格子数为偶数，可以覆盖。
n 为奇数时，总格子数为奇数，不可能覆盖。

这里原始笔记里“保证 n 为奇数”应当是笔误，正确条件是 n 为偶数。

复杂度

时间复杂度：O(1)
空间复杂度：O(1)

参考代码

点击展开代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

int n;

void solve() {
    if (n & 1) cout << "NO" << '\n';
    else cout << "YES" << '\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    solve();
    return 0;
}

Problem B：小苯的数字折叠

题目信息

难度：Easy
状态：1 次 AC
题目链接：小苯的数字折叠

题意简述

给定数字 n 和操作次数上限 k。一次折叠操作为：

将 n 倒序，去除前导零，得到 n'。
更新 n = n + n'。

如果最多 k 次操作内能得到回文数，则输出该回文数和最少操作次数；否则输出第 k 次操作后的结果和 -1。

核心思路

这题直接模拟即可。每次操作前先判断当前数字是否已经是回文数，如果是则提前结束；否则执行一次折叠操作。

需要注意的是：循环结束后仍要再判断一次当前数是否为回文数，因为最后一次折叠后可能刚好得到答案。

实现步骤

写 check(x) 判断 x 是否为回文数。
写 reverseNumber(x) 得到 x 的十进制反转数。
循环最多执行 k 次。
若过程中或结束后出现回文数，输出答案；否则输出当前值和 -1。

复杂度

设数字长度为 d。

时间复杂度：O(k * d)
空间复杂度：O(d)

参考代码

点击展开代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

int T, n, k;

int reverseNumber(int x) {
    int res = 0;
    while (x) {
        res = res * 10 + x % 10;
        x /= 10;
    }
    return res;
}

bool isPalindrome(int x) {
    string s = to_string(x);
    string t(s.rbegin(), s.rend());
    return s == t;
}

void solve() {
    int cur = n;
    int cnt = 0;

    while (cnt < k) {
        if (isPalindrome(cur)) break;
        cur += reverseNumber(cur);
        cnt++;
    }

    if (isPalindrome(cur)) cout << cur << ' ' << cnt << '\n';
    else cout << cur << ' ' << -1 << '\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> T;
    while (T--) {
        cin >> n >> k;
        solve();
    }
    return 0;
}

Problem C：小苯的波浪加密器

题目信息

难度：Easy
状态：4 次 AC
题目链接：小苯的波浪加密器

核心思路

这题的关键突破口是：后续数字只和前两个数字乘积的个位数有关。因此不用枚举完整区间中的所有数字，只需要枚举 a1 和 a2 的个位数。

也就是说，候选状态最多只有：

10 * 10 = 100

枚举量非常小。

易错点

直接枚举 [l1, r1] 和 [l2, r2] 的所有数会超时。正确做法是枚举个位，再找到区间内具有该个位的最小数字。

实现步骤

检查已给出的后续数组是否满足规则。
枚举 a1 和 a2 的个位 i, j。
检查是否满足 i * j % 10 == a3。
若 n >= 4，继续检查 j * a3 % 10 == a4。
在给定区间中找出个位为 i 或 j 的最小合法数。
按 a1 优先、a2 次优先更新答案。

复杂度

时间复杂度：O(100)，可视为 O(1)
空间复杂度：O(1)

参考代码

点击展开代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 5e5 + 3;
const int INF = 2e18;

int T, n, l1, r1, l2, r2, a[N];

int getNumberWithDigit(int digit, int l, int r) {
    int cur = l % 10;
    int diff = (digit - cur + 10) % 10;
    int res = l + diff;
    return res > r ? -1 : res;
}

void solve() {
    for (int i = 5; i <= n; i++) {
        if (a[i - 2] * a[i - 1] % 10 != a[i]) {
            cout << "-1 -1" << '\n';
            return;
        }
    }

    int ans1 = INF, ans2 = INF;
    bool ok = false;

    for (int i = 0; i <= min(r1, 9LL); i++) {
        for (int j = 0; j <= min(r2, 9LL); j++) {
            if (i * j % 10 != a[3]) continue;
            if (n >= 4 && j * a[3] % 10 != a[4]) continue;

            int x = getNumberWithDigit(i, l1, r1);
            int y = getNumberWithDigit(j, l2, r2);
            if (x == -1 || y == -1) continue;

            if (x < ans1 || (x == ans1 && y < ans2)) {
                ans1 = x;
                ans2 = y;
                ok = true;
            }
        }
    }

    if (!ok) cout << "-1 -1" << '\n';
    else cout << ans1 << ' ' << ans2 << '\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> T;
    while (T--) {
        cin >> n >> l1 >> r1 >> l2 >> r2;
        for (int i = 3; i <= n; i++) cin >> a[i];
        solve();
    }
    return 0;
}

Problem D：小苯的数字变换

题目信息

难度：Medium
状态：1 次 AC
题目链接：小苯的数字变换

核心思路

核心观察是：一个数不断执行题目中的变换后，不会无限产生全新的状态，而是会进入循环。因此每个数能到达的状态集合是有限的。

对于数组中一对对称位置 l 和 r，我们只需要找到它们可达状态集合中的交集，并选择总代价最小的公共状态。

实现步骤

对每个 a[i] 预处理它能够到达的所有状态。
记录每个状态第一次出现时需要的操作次数。
双指针枚举对称位置 l, r。
枚举左侧可达状态，查询右侧是否也能到达。
取最小操作次数累加。
如果某一对不存在公共状态，则输出 -1。

复杂度

原始代码中每个数可达状态数量有限，整体复杂度与状态数量有关。保守写法可认为是：

时间复杂度：O(n * s)，其中 s 是单个数进入循环前的状态数。
空间复杂度：O(n * s)

参考代码

点击展开代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 5e5 + 3;
const int INF = 2e18;

int T, n, a[N];

struct Node {
    vector<int> all;
    unordered_map<int, int> step;
};

void solve() {
    vector<Node> node(n + 1);

    for (int i = 1; i <= n; i++) {
        int cur = a[i];
        int step = 0;

        while (!node[i].step.count(cur)) {
            node[i].all.push_back(cur);
            node[i].step[cur] = step;
            step++;
            cur ^= (cur >> 1);
        }
    }

    int ans = 0;
    int l = 1, r = n;

    while (l < r) {
        int best = INF;

        for (int x : node[l].all) {
            auto it = node[r].step.find(x);
            if (it != node[r].step.end()) {
                best = min(best, node[l].step[x] + it->second);
            }
        }

        if (best == INF) {
            cout << -1 << '\n';
            return;
        }

        ans += best;
        l++;
        r--;
    }

    cout << ans << '\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> a[i];
        solve();
    }
    return 0;
}

Problem E：小苯的洞数组构造

题目信息

难度：Easy
状态：未 AC
题目链接：小苯的洞数组构造

赛后思路记录

这题的核心是最大化数字中的“洞”数量。根据常见数位洞数：

0、4、6、9 各有 1 个洞。
8 有 2 个洞。
其他数字没有洞。

由于数字不能有前导零，因此构造时优先考虑 4 和 8。在相同位数下，8 的洞数收益更高；但从总和约束角度看，4 是获取 1 个洞的最小代价。

原始思路是先把所有数设为 1，再根据剩余和逐步给每个位置增加贡献，使数组总和尽量接近 sum 的同时增加洞数。

反思

这题当场没有 AC，说明构造题不能只靠观察局部规律，还要严格证明：

当前构造是否一定满足总和约束。
当前构造是否一定最大化洞数。
同等洞数下是否需要考虑字典序、任意解或其他隐含条件。

这类题后续需要补题时重新推导完整正确性，而不是只保留比赛时的半成品思路。

原始实现记录

点击展开代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

int T, n, sum;

void print(vector<int> a) {
    for (int i = 1; i <= n; i++) {
        cout << a[i];
        if (i != n) cout << ' ';
    }
    cout << '\n';
}

void solve() {
    if (sum < n) {
        cout << -1 << '\n';
        return;
    }

    vector<int> a(n + 1, 1);
    int curSum = n;

    for (int i = 1; i <= n; i++) {
        if (curSum + 3 > sum) break;
        curSum += 3;
        a[i] += 3;
    }

    if (sum <= 4 * n) {
        print(a);
        return;
    }

    int delta = 4;
    bool expand = true;

    while (curSum + delta <= sum) {
        for (int i = 1; i <= n; i++) {
            if (curSum + delta > sum) break;
            curSum += delta;
            a[i] += delta;
        }
        if (expand) delta *= 10;
        expand = !expand;
    }

    print(a);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> T;
    while (T--) {
        cin >> n >> sum;
        solve();
    }
    return 0;
}

Problem F：小苯的数组计数

原始笔记中只列出了目录，没有整理完整题意和解法。这题建议后续单独补题，不要把不完整内容伪装成题解。

总结

这场比赛的主要收获不是某一个具体模板，而是两类能力：

对模拟题，要快速把操作翻译成稳定代码，避免在基础题上损失时间。
对规律题，要尽快缩小状态空间，例如 C 题从大区间压缩到个位状态，D 题从无限操作压缩到有限循环状态。

后续训练重点应放在：

构造题正确性证明。
状态压缩后的边界处理。
比赛中快速判断题目是否值得继续投入时间。