GESP 4级

B3939 [GESP样题四级] 绝对素数 ¶

找出区间[A,B]内，本身和交换十位、个位后都是素数的两位数。

提示1-先按定义检查

看全部数据范围，\(10<A<B<100\)。

我先逐个检查区间里的数。

不到一百个候选，不需要筛法，也不用背下答案。

提示2-怎样交换两位

个位是 \(x\bmod 10\)，十位是 \(\lfloor x/10\rfloor\)，交换后就是 \(10(x\bmod 10)+\lfloor x/10\rfloor\)。

我分别判断原数和交换后的数是否为素数

试除到平方根即可。

代码-满分

时间 \(O((B-A+1)\sqrt B)\)，额外空间 \(O(1)\)。

#include <bits/stdc++.h>

using namespace std;

bool prime(int x) {
    if (x < 2) return false;
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) return false;
    }

    return true;
}

int main() {
    int a, b;
    cin >> a >> b;

    bool first = true;
    for (int x = a; x <= b; x++) {
        // 我把个位搬到十位，再分别检查这两个数。
        int y = x % 10 * 10 + x / 10;
        if (!prime(x) || !prime(y)) continue;
        if (!first) cout << '\n';
        cout << x;
        first = false;
    }

    return 0;
}

B3940 [GESP样题四级] 填幻方 ¶

按题目给出的移动规则，填出N×N的奇数阶幻方。

提示1-先把移动规则拆开

看全部数据范围，\(3\le N\le21\)，\(N\) 为奇数。

我先在第一行中间填 \(1\)，再尝试向右上方走。

越过边界，就从另一侧回来。

提示2-先试位置，再决定去哪里

右上方为空，就走过去。

右上方已经填过，就从原位置向下走，不能从试过的位置继续向下。

我用取模处理环绕，并用二维数组保存每个格子的数。

代码-满分

时间、空间均为 \(O(N^2)\)。

#include <bits/stdc++.h>

using namespace std;

const int N = 25;

int a[N][N];

int main() {
    int n;
    cin >> n;

    int row = 0, col = n / 2;
    for (int x = 1; x <= n * n; x++) {
        a[row][col] = x;
        int next_row = (row + n - 1) % n;
        int next_col = (col + 1) % n;

        // 我先试右上方，撞到已填的格子才从原位置往下走。
        if (a[next_row][next_col] == 0) {
            row = next_row;
            col = next_col;
        } else {
            row = (row + 1) % n;
        }
    }

    for (int i = 0; i < n; i++) {
        if (i) cout << '\n';
        for (int j = 0; j < n; j++) {
            if (j) cout << ' ';
            cout << a[i][j];
        }
    }

    return 0;
}

B3850 [GESP202306 四级] 幸运数 ¶

从个位开始，奇数位乘7并反复求数位和至一位数，偶数位不变。
变换后数位和是8的倍数则输出T，否则输出F。

提示1-先确认从哪边数

看全部数据范围，询问数 \(N\le20\)，每个整数小于 \(10^{12}\)。

我用字符串读入，从右往左数位，个位才是第 \(1\) 位。

用字符串可以避开整数类型和拆位顺序的问题。

提示2-一次变换不一定结束

例如 \(7\times7=49\)，求和得到 \(13\)，还要继续求和得到 \(4\)。

我把这个过程写成小函数，逐位变换后累加，最后检查和能否被 \(8\) 整除。

代码-满分

设最长数位数为 \(L\)，时间 \(O(NL)\)，额外空间 \(O(L)\)。单个数位的变换次数为常数。

#include <bits/stdc++.h>

using namespace std;

int change(int x) {
    x *= 7;
    while (x >= 10) {
        int sum = 0;
        while (x) {
            sum += x % 10;
            x /= 10;
        }
        x = sum;
    }

    return x;
}

int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;

        int sum = 0, place = 1;
        // 我从右往左编号，保证个位按奇数位处理。
        for (int j = (int)s.size() - 1; j >= 0; j--, place++) {
            int x = s[j] - '0';
            if (place % 2 == 1) x = change(x);
            sum += x;
        }

        if (i) cout << '\n';
        cout << (sum % 8 == 0 ? 'T' : 'F');
    }

    return 0;
}

B3851 [GESP202306 四级] 图像压缩 ¶

统计灰阶频数，按频数降序、灰阶值升序选出前16种。每个像素换成最接近的入选灰阶编号，
距离相同取较小编号。

提示1-两位字符才是一个像素

看全部数据范围，\(10\le n\le20\)，每行最多 \(20\) 个像素，至少有 \(16\) 种灰阶。

我先把每两个十六进制字符变成一个 \(0\) 到 \(255\) 的数，用数组统计次数。

提示2-先排频数，再排灰阶值

频数相同时，灰阶值小的排前面。

入选顺序就是编号顺序，不要再按灰阶值重排这 \(16\) 种颜色。

提示3-距离相同，保留先找到的编号

我按编号从小到大试这 \(16\) 种颜色，只在距离严格更小时更新。

这样距离相等时，较小编号自然留下。

输出色表时每个灰阶仍占两位，图像里的编号只占一位。

代码-满分

设像素数为 \(P\)，时间 \(O(P+256\log256+256\times16)\)，空间 \(O(P+256)\)。

#include <bits/stdc++.h>

using namespace std;

const int N = 25;

string image[N];
int count_color[256], order[256], color[16], nearest[256];
string digit = "0123456789ABCDEF";

int value(char c) {
    if (c <= '9') return c - '0';

    return c - 'A' + 10;
}

bool cmp(int x, int y) {
    if (count_color[x] != count_color[y]) return count_color[x] > count_color[y];

    return x < y;
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> image[i];
        for (int j = 0; j < (int)image[i].size(); j += 2) {
            int x = value(image[i][j]) * 16 + value(image[i][j + 1]);
            count_color[x]++;
        }
    }

    for (int i = 0; i < 256; i++) order[i] = i;
    sort(order, order + 256, cmp);
    for (int i = 0; i < 16; i++) {
        color[i] = order[i];
        cout << digit[color[i] / 16] << digit[color[i] % 16];
    }

    // 我只在距离更小时换编号，距离相同就保留较小的编号。
    for (int x = 0; x < 256; x++) {
        int best = 0;
        for (int i = 1; i < 16; i++) {
            if (abs(x - color[i]) < abs(x - color[best])) best = i;
        }
        nearest[x] = best;
    }

    for (int i = 0; i < n; i++) {
        cout << '\n';
        for (int j = 0; j < (int)image[i].size(); j += 2) {
            int x = value(image[i][j]) * 16 + value(image[i][j + 1]);
            cout << digit[nearest[x]];
        }
    }

    return 0;
}

B3869 [GESP202309 四级] 进制转换 ¶

把给定的K进制数转换为十进制数，字母A到F分别表示10到15。

提示1-不必逐位计算幂

看全部数据范围，\(N\le1000\)，\(2\le K\le16\)，每个数最多 \(9\) 位。

我先试十进制的 \(123\)：读到下一位，就是把已有结果乘以 \(10\)，再加新数字。

换成 \(K\) 进制，只需把乘数换成 \(K\)。

提示2-结果可能超过int

最大结果为 \(16^9-1\)，要用 long long。

数字字符减去字符0，字母字符减去字符A再加 \(10\)，不能把字符编码直接当数值。

代码-满分

设最长位数为 \(L\)，时间 \(O(NL)\)，额外空间 \(O(L)\)。

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        int k;
        string s;
        cin >> k >> s;

        long long ans = 0;
        // 我每读一位，就把已有数值向高位挪一位。
        for (char c : s) {
            int x = c <= '9' ? c - '0' : c - 'A' + 10;
            ans = ans * k + x;
        }

        if (i) cout << '\n';
        cout << ans;
    }

    return 0;
}

B3870 [GESP202309 四级] 变长编码 ¶

把非负整数按低位到高位每7个二进制位分组。
还有后续分组时将当前字节最高位置1，按两位大写十六进制输出。

提示1-七位一组，对应除以多少

看全部数据范围，\(0\le N\le10^{18}\)，用 long long。

我把 \(7\) 个二进制位看成一个 \(128\) 进制数位：\(N\bmod128\) 取出当前组，整除 \(128\) 得到剩余组。

提示2-最高位表示后面还有没有

除完后仍有剩余，就给当前字节加 \(128\)

没有剩余，就不加。

我会特别试 \(N=0\)：也必须输出一组00，所以用至少执行一次的 do-while。

代码-满分

时间 \(O(1+\log_{128}(N+1))\)，额外空间 \(O(1)\)。

#include <bits/stdc++.h>

using namespace std;

string digit = "0123456789ABCDEF";

int main() {
    long long n;
    cin >> n;

    bool first = true;
    // 我用128进制逐组取低七位，零也要执行一次。
    do {
        int x = n % 128;
        n /= 128;
        if (n > 0) x += 128;

        if (!first) cout << ' ';
        cout << digit[x / 16] << digit[x % 16];
        first = false;
    } while (n > 0);

    return 0;
}

B3927 [GESP202312 四级] 小杨的字典 ¶

根据字典替换文章中的小写单词，未知单词输出UNK，所有标点原样保留。

提示1-先找单词边界

看全部数据范围，字典条目数 \(N\le100\)，单词长度不超过 \(10\)，文章长度 \(L\le1000\)。

我从左往右读，小写字母就接到当前单词后面，遇到标点才说明单词结束。

提示2-标点不能丢，末尾单词不能漏

遇到标点，先翻译积累的单词，再输出标点。

连续标点之间没有单词，不要多输出UNK。

读完整篇文章后，还要翻译最后没遇到标点的单词。

我用 map 保存字典，用 find 查询，避免查询时插入新条目。

代码-满分

设单词长度上界为 \(W\)，时间 \(O(NW\log(N+1)+LW\log(N+1))\)，空间 \(O(NW+L)\)。这里 \(W\le10\)。

#include <bits/stdc++.h>

using namespace std;

map<string, string> dict;

void translate(string &word) {
    if (word.empty()) return;

    auto it = dict.find(word);
    if (it == dict.end()) cout << "UNK";
    else cout << it->second;
    word.clear();
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        string a, b;
        cin >> a >> b;
        dict[a] = b;
    }

    string s, word;
    cin >> s;
    // 我先翻译单词，再原样放回分隔它的标点。
    for (char c : s) {
        if (c >= 'a' && c <= 'z') word += c;
        else {
            translate(word);
            cout << c;
        }
    }
    translate(word);

    return 0;
}

B3928 [GESP202312 四级] 田忌赛马 ¶

双方各有N匹马，速度两两不同。对方出场顺序固定，求自己最多能赢几轮。

提示1-先想赢一匹弱马

看全部数据范围，\(N\le5\times10^4\)，速度不超过 \(2N\)。

我想赢对方一匹马时，应该用刚好能赢它的最慢马，把更快的马留给更强的对手。

提示2-排序后直接配对

我先把双方按速度升序排列。

当前自己的马能赢最慢的待匹配对手，就配成一场胜利。

否则自己的这匹马连最慢的对手都赢不了，可以跳过。

这里只求最多胜场，配对后再按对方原来的出场顺序安排即可，不必保存具体出场方案。

代码-满分

时间 \(O(N\log N)\)，空间 \(O(N)\)。

#include <bits/stdc++.h>

using namespace std;

const int N = 50005;

int a[N], b[N];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];

    sort(a, a + n);
    sort(b, b + n);

    int ans = 0, j = 0;
    // 我用能赢当前对手的最慢马，把快马留给后面的对手。
    for (int i = 0; i < n; i++) {
        if (j < n && a[i] > b[j]) {
            ans++;
            j++;
        }
    }
    cout << ans;

    return 0;
}

B3958 [GESP202403 四级] 相似字符串 ¶

判断两个字符串能否通过至多一次插入、删除或修改变成相同字符串。

提示1-先按长度分情况

看全部数据范围，\(T\le100\)，字符串长度不超过 \(50\)。

长度差超过 \(1\)，一次操作肯定不够。

长度相同，只能靠修改，统计不同位置的数量，不超过 \(1\) 就行。

提示2-长度差一时，只能跳过长串的一个字符

我让较短的串放在前面，用两个下标同时比较。

第一次不同，只跳过长串的当前字符。

再遇到不同，就不相似。

若前面都相同，长串最后多出的字符也算一次插入。

代码-满分

设最长串长为 \(L\)，时间 \(O(TL)\)，额外空间 \(O(L)\)。

#include <bits/stdc++.h>

using namespace std;

bool similar(string a, string b) {
    if (a.size() > b.size()) swap(a, b);
    if (b.size() - a.size() > 1) return false;

    if (a.size() == b.size()) {
        int count = 0;
        for (int i = 0; i < (int)a.size(); i++) {
            if (a[i] != b[i]) count++;
        }
        return count <= 1;
    }

    int i = 0, j = 0, skipped = 0;
    // 我只让长串多走一步，短串仍然等待匹配当前字符。
    while (i < (int)a.size() && j < (int)b.size()) {
        if (a[i] == b[j]) {
            i++;
            j++;
        } else {
            skipped++;
            if (skipped > 1) return false;
            j++;
        }
    }

    return true;
}

int main() {
    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        string a, b;
        cin >> a >> b;
        if (i) cout << '\n';
        cout << (similar(a, b) ? "similar" : "not similar");
    }

    return 0;
}

B3959 [GESP202403 四级] 做题 ¶

第k天需要做k道题，每天使用一套未用过的题单，求最多能坚持多少天。

提示1-小题单应该留给哪一天

看全部数据范围，\(n\le10^6\)，\(a_i\le10^9\)。

我先做需求少的日子，并优先用题数最少但够用的题单。

把大题单提前用掉，后面可能没有足够大的题单。

提示2-题数不够时，不是马上结束

排序后，设已经完成 \(d\) 天。

当前题单至少有 \(d+1\) 道题，就可以继续一天。

不够就跳过这套题单，再找后面更大的，不能把没用成的题单也计作一天。

代码-满分

时间 \(O(n\log n)\)，空间 \(O(n)\)。

#include <bits/stdc++.h>

using namespace std;

const int N = 1000005;

int a[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a, a + n);

    int ans = 0;
    // 我把最小的够用题单交给当前这一天，不够就继续找。
    for (int i = 0; i < n; i++) {
        if (a[i] >= ans + 1) ans++;
    }
    cout << ans;

    return 0;
}

B4005 [GESP202406 四级] 黑白方块 ¶

在01网格中，找黑格与白格数量相等的最大子矩形，不存在则输出0。

提示1-先看范围，直接枚举四条边

看全部数据范围，\(1\le n,m\le10\)。

我先枚举上、下、左、右边界。

矩阵很小，不需要复杂的动态规划。

提示2-怎样快速数黑格

我先求二维前缀和，四次加减就能得到一个矩形的黑格数。

黑格数乘 \(2\) 等于矩形面积，就说明黑白各占一半。

符合条件时，用面积更新最大值。

代码-满分

时间 \(O(n^2m^2)\)，空间 \(O(nm)\)。

#include <bits/stdc++.h>

using namespace std;

const int N = 15;

int sum[N][N];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        for (int j = 1; j <= m; j++) {
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1]
                        - sum[i - 1][j - 1] + s[j - 1] - '0';
        }
    }

    int ans = 0;
    // 我固定四条边，再用前缀和直接数出黑格。
    for (int top = 1; top <= n; top++) {
        for (int bottom = top; bottom <= n; bottom++) {
            for (int left = 1; left <= m; left++) {
                for (int right = left; right <= m; right++) {
                    int black = sum[bottom][right] - sum[top - 1][right]
                                - sum[bottom][left - 1] + sum[top - 1][left - 1];
                    int area = (bottom - top + 1) * (right - left + 1);
                    if (black * 2 == area) ans = max(ans, area);
                }
            }
        }
    }
    cout << ans;

    return 0;
}

B4006 [GESP202406 四级] 宝箱 ¶

选取一些正价值宝箱，最大价值与最小价值之差不超过k，求最大总价值。

提示1-先排序，把能一起带走的放一起

看全部数据范围，\(n\le1000\)，\(0\le k\le1000\)，\(1\le a_i\le1000\)。

我固定最小、最大价值后，中间的宝箱都可以拿，而且价值为正，多拿不会吃亏。

于是答案一定能用排序后的连续区间表示。

提示2-右边加入，左边收紧

我把右端点逐个向右移，并维护区间价值和。

若最大值减最小值超过 \(k\)，就不断移走左端点，直到合法。

此时保留下来的最长区间也是当前右端点下总价值最大的区间。

代码-满分

时间 \(O(n\log n)\)，空间 \(O(n)\)。本题最大总价值不超过 \(10^6\)，int 足够。

#include <bits/stdc++.h>

using namespace std;

const int N = 1005;

int a[N];

int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a, a + n);

    int left = 0, sum = 0, ans = 0;
    // 所有价值都为正，我保留当前右端点下尽可能长的合法区间。
    for (int right = 0; right < n; right++) {
        sum += a[right];
        while (a[right] - a[left] > k) {
            sum -= a[left];
            left++;
        }
        ans = max(ans, sum);
    }
    cout << ans;

    return 0;
}

B4040 [GESP202409 四级] 黑白方块 ¶

判断01网格是否含有4×4子矩形：白色边框包围黑色2×2中心。有则输出Yes，否则输出No。

提示1-图案固定，枚举左上角

看全部数据范围，\(t\le10\)，\(n,m\le100\)。

我把目标图案写成四行字符串，再枚举所有能放下它的位置，每次比较 \(16\) 个格子。

提示2-边界不能多走一格

左上角下方和右方都还要留 \(3\) 格。

若 \(n<4\) 或 \(m<4\)，没有合法左上角，答案自然为No。

每组数据都要重新设置是否找到。

代码-满分

时间 \(O(tnm)\)，空间 \(O(nm)\)；每个位置的 \(16\) 次比较是常数。

#include <bits/stdc++.h>

using namespace std;

const int N = 105;

string a[N];
string pattern[4] = {"0000", "0110", "0110", "0000"};

int main() {
    int t;
    cin >> t;
    for (int test = 0; test < t; test++) {
        int n, m;
        cin >> n >> m;
        for (int i = 0; i < n; i++) cin >> a[i];

        bool found = false;
        // 图案只有十六格，我直接逐格比较，不给边界外的位置开后门。
        for (int i = 0; i + 3 < n; i++) {
            for (int j = 0; j + 3 < m; j++) {
                bool ok = true;
                for (int x = 0; x < 4; x++) {
                    for (int y = 0; y < 4; y++) {
                        if (a[i + x][j + y] != pattern[x][y]) ok = false;
                    }
                }
                if (ok) found = true;
            }
        }

        if (test) cout << '\n';
        cout << (found ? "Yes" : "No");
    }

    return 0;
}

B4041 [GESP202409 四级] 区间排序 ¶

依次对给定的闭区间[l,r]进行升序排序，输出最终序列。

提示1-范围小，按操作顺序做

看全部数据范围，\(n,q,a_i\le100\)。

我每读到一个区间，就对当前数组的这一段排序。

后一次必须接着前一次的结果，不能每次从原数组开始。

提示2-闭区间和sort的边界不同

题目下标从 \(1\) 开始，我也把数组从 \(1\) 开始存。

sort 的结束位置不包含在内，所以排序 \([l,r]\) 要写成 sort(a+l,a+r+1)。

代码-满分

时间 \(O(qn\log n)\)，空间 \(O(n)\)。

#include <bits/stdc++.h>

using namespace std;

const int N = 105;

int a[N];

int main() {
    int n, q;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    cin >> q;

    // 我让每次排序直接作用在上次留下的数组上。
    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        sort(a + l, a + r + 1);
    }

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

    return 0;
}

B4068 [GESP202412 四级] Recamán ¶

从a₁=1开始，优先减去当前项号得到未出现过的正整数，否则加上项号。
输出前n项排序后的结果。

提示1-按题意生成，不要提前排序

看全部数据范围，\(n\le3000\)。

我先完整生成数列，最后才排序。

生成下一项要用上一项的原值，提前排序就会改变数列。

提示2-零不能选，加法可能产生重复

减法结果必须严格大于 \(0\)，并且没有出现过。

否则直接用加法结果，不要求加法结果也没出现过。

我用 set 记录出现情况，但原数组要保留重复项。

代码-满分

时间 \(O(n\log n)\)，空间 \(O(n)\)。数值不超过 \(n(n+1)/2\)，int 足够。

#include <bits/stdc++.h>

using namespace std;

const int N = 3005;

int a[N];
set<int> seen;

int main() {
    int n;
    cin >> n;
    a[1] = 1;
    seen.insert(1);

    // 我只检查减法候选是否出现过，加法结果照题意直接接受。
    for (int i = 2; i <= n; i++) {
        int x = a[i - 1] - i;
        if (x > 0 && !seen.count(x)) a[i] = x;
        else a[i] = a[i - 1] + i;
        seen.insert(a[i]);
    }

    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++) {
        if (i > 1) cout << ' ';
        cout << a[i];
    }

    return 0;
}

B4069 [GESP202412 四级] 字符排序 ¶

重排若干小写字符串后拼接，判断能否让整个字符串的字符不下降，能则输出1，
否则输出0。

提示1-字符串内部不能改

看全部数据范围，\(T,n\le100\)，每个串长度 \(L\le10\)。

我先检查每个串内部是否不下降。

若出现ba这样的下降，无论把这个串放在哪里都不行。

提示2-再看两个串的接缝

内部合法后，我按字典序排序，再检查前一串末字符是否不大于后一串首字符。

若有合法排列，各串在整体中的顺序也会按字典序不下降，因此这样排序不会错过可行方案。

相同字符串也要保留。

代码-满分

时间 \(O(TnL\log(n+1))\)，空间 \(O(nL)\)。

#include <bits/stdc++.h>

using namespace std;

const int N = 105;

string s[N];

int main() {
    int t;
    cin >> t;
    for (int test = 0; test < t; test++) {
        int n;
        cin >> n;
        bool ok = true;
        for (int i = 0; i < n; i++) {
            cin >> s[i];
            for (int j = 1; j < (int)s[i].size(); j++) {
                if (s[i][j - 1] > s[i][j]) ok = false;
            }
        }

        sort(s, s + n);
        // 我既检查串内，也检查拼接后两个串之间的接缝。
        for (int i = 1; i < n; i++) {
            if (s[i - 1].back() > s[i].front()) ok = false;
        }

        if (test) cout << '\n';
        cout << (ok ? 1 : 0);
    }

    return 0;
}

B4263 [GESP202503 四级] 荒地开垦 ¶

空地及其上下左右相邻的格子都无杂物时，才可开垦。
最多清除一处杂物，求可开垦格子的最大数量。

提示1-不能每清一次就重新检查整张图

看全部数据范围，\(n,m\le1000\)。

我先统计原来能开垦的格子。

清除一个杂物，只会影响它自己和上下左右的格子，最多 \(5\) 处。

提示2-空地什么时候能新增

我记录每块空地旁边有几个杂物。

相邻杂物恰好有 \(1\) 个时，清除这唯一的杂物，它就能新增到答案。

本来没有相邻杂物的空地已计入原答案，不能重复加。

相邻杂物有多个时，只清一次仍然不够。

提示3-被清除的格子也要检查

原杂物位置清空后，只有四周没有其他杂物，它自己才能开垦。

我逐个枚举杂物，累加这几处新增量，再加原答案。

边界外没有格子，不算杂物。

代码-满分

时间、空间均为 \(O(nm)\)。

#include <bits/stdc++.h>

using namespace std;

const int N = 1005;

string a[N];
int blocked[N][N];
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
int n, m;

bool inside(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> a[i];

    int original = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            for (int k = 0; k < 4; k++) {
                int x = i + dx[k], y = j + dy[k];
                if (inside(x, y) && a[x][y] == '#') blocked[i][j]++;
            }
            if (a[i][j] == '.' && blocked[i][j] == 0) original++;
        }
    }

    int ans = original;
    // 我只看清除位置周围的五格，不重复扫描整张图。
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (a[i][j] != '#') continue;
            int gain = blocked[i][j] == 0 ? 1 : 0;
            for (int k = 0; k < 4; k++) {
                int x = i + dx[k], y = j + dy[k];
                if (inside(x, y) && a[x][y] == '.' && blocked[x][y] == 1) gain++;
            }
            ans = max(ans, original + gain);
        }
    }
    cout << ans;

    return 0;
}

B4264 [GESP202503 四级] 二阶矩阵 ¶

统计所有相邻两行、相邻两列构成的2×2子矩阵中，两条对角线乘积相等的数量。

提示1-固定左上角，就固定了四个数

看全部数据范围，\(n,m\le500\)，\(-100\le a_{i,j}\le100\)。

我枚举左上角，右下角一定是下一行、下一列，不需要再枚举四条边。

提示2-直接乘，不要改成除法

判断 \(a_{i,j}a_{i+1,j+1}=a_{i,j+1}a_{i+1,j}\)。

元素可能为 \(0\) 或负数，用乘法最直接。

每个乘积绝对值最多 \(10^4\)，int 足够

只有一行或一列时答案为 \(0\)。

代码-满分

时间、空间均为 \(O(nm)\)。

#include <bits/stdc++.h>

using namespace std;

const int N = 505;

int a[N][N];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) cin >> a[i][j];
    }

    int ans = 0;
    // 我直接比较交叉乘积，避免零元素引起除零。
    for (int i = 0; i + 1 < n; i++) {
        for (int j = 0; j + 1 < m; j++) {
            if (a[i][j] * a[i + 1][j + 1] == a[i][j + 1] * a[i + 1][j]) ans++;
        }
    }
    cout << ans;

    return 0;
}

B4360 [GESP202506 四级] 画布裁剪 ¶

保留字符画布第x₁到x₂行、第y₁到y₂列，输出裁剪后的内容。

提示1-输入坐标与字符串下标差一

看全部数据范围，\(h,w\le100\)，保留边界均在画布内。

题目列号从 \(1\) 开始，字符串从 \(0\) 开始。

第 \(y_1\) 列对应字符串下标 \(y_1-1\)。

提示2-不在范围内的行也要读

我逐行读画布，只输出保留范围内的行，再截取需要的列。

substr 的第二个参数是长度，应该是 \(y_2-y_1+1\)，不是结束下标。

画布没有空格，可以直接用 cin。

代码-满分

时间 \(O(hw)\)，额外空间 \(O(w)\)。

#include <bits/stdc++.h>

using namespace std;

int main() {
    int h, w, x1, x2, y1, y2;
    cin >> h >> w >> x1 >> x2 >> y1 >> y2;

    // 我仍然读完每一行，只在保留范围内输出。
    for (int i = 1; i <= h; i++) {
        string s;
        cin >> s;
        if (i < x1 || i > x2) continue;
        if (i > x1) cout << '\n';
        cout << s.substr(y1 - 1, y2 - y1 + 1);
    }

    return 0;
}

B4361 [GESP202506 四级] 排序 ¶

按身高降序、同身高按体重降序排队，每次只能交换相邻两人，求最少交换次数。

提示1-不是问调用sort要几次

看全部数据范围，\(n\le3000\)，\(0\le h_i,w_i\le10^9\)。

我先找必须换顺序的两个人：前面的人较矮，或者同身高但较轻。

这一对在最终队伍里一定要反过来。

提示2-每对颠倒关系都要修正一次

相邻交换每次只改变被交换的这一对人的先后关系，其他人的相对顺序不变。

用冒泡的方式，每次交换一对颠倒的相邻人，就能恰好把这些颠倒关系各修正一次。

所以我直接枚举所有 \(i<j\) 并统计。

最多约 \(450\) 万对，平方级足够

身高和体重都相同不计交换。

代码-满分

时间 \(O(n^2)\)，空间 \(O(n)\)。本题不必用树状数组或归并排序。

#include <bits/stdc++.h>

using namespace std;

const int N = 3005;

int height[N], weight[N];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> height[i] >> weight[i];

    long long ans = 0;
    // 我数的是必须改变先后顺序的人对，不是实际模拟搬动队伍。
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (height[i] < height[j] ||
                (height[i] == height[j] && weight[i] < weight[j])) ans++;
        }
    }
    cout << ans;

    return 0;
}

B4415 [GESP202509 四级] 排兵布阵 ¶

在01矩阵中选出全为1的最大子矩形，输出它包含的格子数。

提示1-十二行十二列，先枚举矩形

看全部数据范围，\(n,m\le12\)。

我用上、下、左、右四条边确定矩形。

规模很小，直接枚举全部矩形就能满分，不必使用单调栈。

提示2-数零，比逐格检查更方便

我先求零格数量的二维前缀和。

一个矩形里的零格数为 \(0\)，就说明它全部为 \(1\)。

合法时更新最大面积

全是 \(0\) 时，答案保持为 \(0\)。

代码-满分

时间 \(O(n^2m^2)\)，空间 \(O(nm)\)。

#include <bits/stdc++.h>

using namespace std;

const int N = 15;

int sum[N][N];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int x;
            cin >> x;
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1]
                        - sum[i - 1][j - 1] + (x == 0);
        }
    }

    int ans = 0;
    // 我检查矩形里有没有零，而不是重新看每一个格子。
    for (int top = 1; top <= n; top++) {
        for (int bottom = top; bottom <= n; bottom++) {
            for (int left = 1; left <= m; left++) {
                for (int right = left; right <= m; right++) {
                    int zeros = sum[bottom][right] - sum[top - 1][right]
                                - sum[bottom][left - 1] + sum[top - 1][left - 1];
                    int area = (bottom - top + 1) * (right - left + 1);
                    if (zeros == 0) ans = max(ans, area);
                }
            }
        }
    }
    cout << ans;

    return 0;
}

B4416 [GESP202509 四级] 最长连续段 ¶

可以重排整数数组，求每个数都比前一个大1的最长连续子数组长度。

提示1-40分为什么想到枚举排列

40分做法，\(n\le8\)。

看全部数据范围，\(n\le10^5\)，\(-10^9\le a_i\le10^9\)。

题目允许任意重排，我先照这个要求，把每种排列都试一遍。

\(8!\) 只有 \(40320\)，可以边排列边记录连续段长度。

提示2-大范围只关心哪些数存在

我再看一段连续数，比如 \(3,4,5\)。

只要这三个数都存在，就能把它们放在一起，原来的位置并不重要。

重复的 \(4\) 不能让这段更长，但可以放到别处。

因此我先排序，遇到重复数就跳过。

提示3-遇到断档就重新开始

当前数比前一个不同的数大 \(1\)，连续长度加一。

否则从当前数重新开始，长度设为 \(1\)。

全是相同数字时答案也是 \(1\)。

代码-40分-枚举排列

时间 \(O(n\cdot n!)\)，空间 \(O(n)\)，只适用于 \(n\le8\)。

#include <bits/stdc++.h>

using namespace std;

const int N = 10;

int a[N], n, ans;
bool used[N];

void dfs(int place, int last, int length) {
    if (place == n) return;

    // 我先把每种排列走出来，边放数字边检查当前连续段。
    for (int i = 0; i < n; i++) {
        if (used[i]) continue;
        int current = place > 0 && a[i] == last + 1 ? length + 1 : 1;
        ans = max(ans, current);

        used[i] = true;
        dfs(place + 1, a[i], current);
        used[i] = false;
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];

    dfs(0, 0, 0);
    cout << ans;

    return 0;
}

代码-满分

时间 \(O(n\log n)\)，空间 \(O(n)\)。

#include <bits/stdc++.h>

using namespace std;

const int N = 100005;

int a[N];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a, a + n);

    int length = 1, ans = 1;
    // 重复数不能延长连续段，我把它跳过，而不是把当前段清空。
    for (int i = 1; i < n; i++) {
        if (a[i] == a[i - 1]) continue;
        if (a[i] == a[i - 1] + 1) length++;
        else length = 1;
        ans = max(ans, length);
    }
    cout << ans;

    return 0;
}

B4451 [GESP202512 四级] 建造 ¶

枚举3×3区域，要求最大海拔与最小海拔之差不超过H，求合法区域的最大海拔总和。

提示1-地图大，但每次只看九格

看全部数据范围，\(M,N\le1000\)，\(H,a_{i,j}\le10^5\)，保证存在合法区域。

我枚举停机坪左上角，每次只检查 \(9\) 个格子。

百万个位置乘以 \(9\)，直接扫描就够了。

提示2-三个量分开记录

我记录最大海拔、最小海拔和总和。

高度差合法时才更新答案。

最大、最小值先取区域左上角的高度，不用随便猜一个大常数。

总和最多 \(9\times10^5\)，int 足够。

代码-满分

时间、空间均为 \(O(MN)\)。

#include <bits/stdc++.h>

using namespace std;

const int N = 1005;

int a[N][N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int rows, cols, h;
    cin >> rows >> cols >> h;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) cin >> a[i][j];
    }

    int ans = 0;
    // 每个候选只有九格，我直接求它的最大值、最小值和总和。
    for (int i = 0; i + 2 < rows; i++) {
        for (int j = 0; j + 2 < cols; j++) {
            int largest = a[i][j], smallest = a[i][j], sum = 0;
            for (int x = i; x <= i + 2; x++) {
                for (int y = j; y <= j + 2; y++) {
                    largest = max(largest, a[x][y]);
                    smallest = min(smallest, a[x][y]);
                    sum += a[x][y];
                }
            }
            if (largest - smallest <= h) ans = max(ans, sum);
        }
    }
    cout << ans;

    return 0;
}

B4452 [GESP202512 四级] 优先购买 ¶

按优先级升序、价格升序、名字字典序购买能买得起的商品，
最后按名字字典序输出已购商品。

提示1-买的顺序和输出的顺序不同

看全部数据范围，\(N\le1000\)，预算和价格不超过 \(10^5\)，名字长度 \(L\le10\)，优先级不超过 \(10\)。

我先按优先级、价格、名字这三个条件排序，用这个顺序决定买谁。

买完后，再把已购名字按字典序输出。

提示2-当前买不起，还能看看后面

当前商品买不起，就跳过，不是结束购物。

较低优先级的商品可能更便宜。

同一优先级可以购买多件，每件商品最多购买一次。

样例里预算剩 \(5\) 元时，apple买不起，但water和cab还能购买。

代码-满分

时间 \(O(NL\log N)\)，空间 \(O(NL)\)。

#include <bits/stdc++.h>

using namespace std;

const int N = 1005;

struct Item {
    string name;
    int price, priority;
} a[N];

bool cmp(const Item &x, const Item &y) {
    if (x.priority != y.priority) return x.priority < y.priority;
    if (x.price != y.price) return x.price < y.price;

    return x.name < y.name;
}

int main() {
    int money, n;
    cin >> money >> n;
    for (int i = 0; i < n; i++) cin >> a[i].name >> a[i].price >> a[i].priority;
    sort(a, a + n, cmp);

    vector<string> bought;
    // 我跳过买不起的商品，后面的便宜商品仍有机会。
    for (int i = 0; i < n; i++) {
        if (a[i].price <= money) {
            money -= a[i].price;
            bought.push_back(a[i].name);
        }
    }

    sort(bought.begin(), bought.end());
    for (int i = 0; i < (int)bought.size(); i++) {
        if (i) cout << '\n';
        cout << bought[i];
    }

    return 0;
}

B4501 [GESP202603 四级] 山之谷 ¶

格子的海拔不高于周围八个方向所有有效邻居时，称为山谷，求山谷数量。

提示1-不高于，允许相等

看全部数据范围，\(N,M\le100\)，海拔不超过 \(10^5\)。

我对每个格子检查八个方向。

只有发现更低的邻居，它才不是山谷

同高度的邻居不会让它失去资格。

提示2-边界只检查图内邻居

角落只有三个邻居，边缘也不到八个。

我先判断邻居是否在图内，再读取海拔。

只有一个格子时，没有更低的邻居，所以答案为 \(1\)。

代码-满分

时间、空间均为 \(O(NM)\)。

#include <bits/stdc++.h>

using namespace std;

const int N = 105;

int a[N][N];
int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) cin >> a[i][j];
    }

    int ans = 0;
    // 我只排除有更低邻居的格子，不能把相等高度也排除。
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            bool ok = true;
            for (int k = 0; k < 8; k++) {
                int x = i + dx[k], y = j + dy[k];
                if (x < 0 || x >= n || y < 0 || y >= m) continue;
                if (a[x][y] < a[i][j]) ok = false;
            }
            if (ok) ans++;
        }
    }
    cout << ans;

    return 0;
}

B4502 [GESP202603 四级] 礼盒排序 ¶

礼盒按总价、最高商品价、最低商品价、编号依次升序排序，输出编号。

提示1-先把排序需要的信息存下来

看全部数据范围，\(n\le1000\)，每盒商品数 \(k\le10\)，商品价格不超过 \(10^4\)。

我读一盒商品时就求总价、最大值、最小值，连同原编号一起存，不需要保存盒内所有价格。

提示2-前一条没分出大小，再看下一条

比较函数依次检查总价、最大值、最小值，最后比较编号。

编号是最后的规则，不能因为排序后位置变了，就把编号也改掉。

总价最多 \(10^5\)，int 足够。

代码-满分

时间 \(O(nk+n\log n)\)，空间 \(O(n)\)。

#include <bits/stdc++.h>

using namespace std;

const int N = 1005;

struct Box {
    int sum, largest, smallest, id;
} a[N];

bool cmp(const Box &x, const Box &y) {
    if (x.sum != y.sum) return x.sum < y.sum;
    if (x.largest != y.largest) return x.largest < y.largest;
    if (x.smallest != y.smallest) return x.smallest < y.smallest;

    return x.id < y.id;
}

int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        a[i].id = i + 1;
        for (int j = 0; j < k; j++) {
            int x;
            cin >> x;
            a[i].sum += x;
            if (j == 0) a[i].largest = a[i].smallest = x;
            else {
                a[i].largest = max(a[i].largest, x);
                a[i].smallest = min(a[i].smallest, x);
            }
        }
    }

    // 我只排序礼盒记录，原编号一直跟着礼盒走。
    sort(a, a + n, cmp);
    for (int i = 0; i < n; i++) {
        if (i) cout << ' ';
        cout << a[i].id;
    }

    return 0;
}

B4557 [GESP202606 四级] 扫雷 ¶

给出雷区坐标，输出扫雷地图：雷区为*，其余格子输出周围八方向的雷数，
格子间用空格分隔。

提示1-先把雷的位置全部标好

看全部数据范围，\(3\le n,m\le500\)，\(1\le q\le nm\)，坐标不重复。

我先读完所有雷区，再生成答案。

如果读到一颗雷就马上输出，后面读入的雷可能漏算。

提示2-雷区和非雷区分开处理

当前是雷区，直接输出星号。

否则检查八个方向，统计有效邻居中的雷。

边界外不能访问，行列坐标都从 \(1\) 开始。

代码-满分

时间 \(O(nm+q)\)，空间 \(O(nm)\)。

#include <bits/stdc++.h>

using namespace std;

const int N = 505;

bool mine[N][N];
int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};

int main() {
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 0; i < q; i++) {
        int x, y;
        cin >> x >> y;
        mine[x][y] = true;
    }

    // 我先标完所有雷，再逐格查看周围八个方向。
    for (int i = 1; i <= n; i++) {
        if (i > 1) cout << '\n';
        for (int j = 1; j <= m; j++) {
            if (j > 1) cout << ' ';
            if (mine[i][j]) {
                cout << '*';
                continue;
            }

            int count = 0;
            for (int k = 0; k < 8; k++) {
                int x = i + dx[k], y = j + dy[k];
                if (x < 1 || x > n || y < 1 || y > m) continue;
                if (mine[x][y]) count++;
            }
            cout << count;
        }
    }

    return 0;
}

B4558 [GESP202606 四级] 身高体重指数 ¶

按照BMI从高到低输出编号。BMI等于体重除以身高的平方，输入身高恰有两位小数。

提示1-先把公式写对

看全部数据范围，\(n\le1000\)，\(10\le w_i\le100\)，\(0.8\le h_i\le1.9\)，BMI互不相同。

BMI为 \(\frac{w_i}{h_i^2}\)。

我先计算每个人的BMI，保存编号，再按BMI降序排列，就能解决本题。

提示2-两位小数还能变成整数比较

我进一步利用身高恰有两位小数，把它读成厘米整数 \(c_i\)。

公共倍数不影响排序。

比较两个人，只需比较 \(w_ic_j^2\) 和 \(w_jc_i^2\)，不用先除，也不用人为设误差。

乘法用 long long。

代码-满分

时间 \(O(n\log n)\)，空间 \(O(n)\)。

#include <bits/stdc++.h>

using namespace std;

const int N = 1005;

struct Child {
    int weight, height, id;
} a[N];

bool cmp(const Child &x, const Child &y) {
    return 1LL * x.weight * y.height * y.height
           > 1LL * y.weight * x.height * x.height;
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i].weight;
        a[i].id = i + 1;
    }

    // 身高恰有两位小数，我去掉小数点，直接得到厘米数。
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (char c : s) {
            if (c != '.') a[i].height = a[i].height * 10 + c - '0';
        }
    }

    sort(a, a + n, cmp);
    for (int i = 0; i < n; i++) {
        if (i) cout << ' ';
        cout << a[i].id;
    }

    return 0;
}

B4579 [GESP202609 四级] 新汉诺塔 ¶

圆盘只允许沿A→B→C→A移动，求把n个圆盘从A移到C的最少步数。

提示1-新规则下，一步和两步方向不一样

看全部数据范围，\(1\le n\le20\)。

我先试一个盘：从A到B要 \(1\) 步，从A到C要 \(2\) 步。

不能直接沿用普通汉诺塔的递推。

记 \(f_n\) 为搬到循环方向下一根柱子的最少步数，\(g_n\) 为搬到下两根柱子的最少步数，答案是 \(g_n\)。

提示2-先看最大盘走一步

从A搬到B前，我必须把上面 \(n-1\) 个盘搬到C，再移动最大盘，最后把小盘从C搬到B。

两次小盘移动都是两步方向，所以 \(f_n=2g_{n-1}+1\)。

提示3-最大盘要走两步时

从A搬到C：先把小盘搬到C，最大盘A→B

再把小盘C→A，最大盘B→C

最后把小盘A→C。

小盘的三次任务分别是两步、一步、两步方向，因此：

\[ g_n=2g_{n-1}+f_{n-1}+2 \]

我从 \(f_0=g_0=0\) 开始递推。

最大盘要动时，其他两根柱子的位置决定了小盘必须在哪里

多绕圈只会增加这些任务。

结果用 long long。

代码-满分

时间、空间均为 \(O(n)\)。\(n=20\) 时答案为 \(578272255\)；代码用 long long 保存递推值。

#include <bits/stdc++.h>

using namespace std;

const int N = 25;

long long f[N], g[N];

int main() {
    int n;
    cin >> n;

    // 我分别记下一根和下两根柱子的代价，避免把两种任务混在一起。
    for (int i = 1; i <= n; i++) {
        f[i] = 2 * g[i - 1] + 1;
        g[i] = 2 * g[i - 1] + f[i - 1] + 2;
    }
    cout << g[n];

    return 0;
}

B4580 [GESP202609 四级] 有序网格 ¶

先将矩阵每行升序排序，再将每列升序排序，输出最终矩阵。

提示1-两轮排序，先后不能颠倒

看全部数据范围，\(2\le n,m\le10\)，\(1\le a_{i,j}\le100\)。

我先排完所有行，再排所有列。

不要排一行就接着排对应的一列，那不是题目要求的顺序。

提示2-一列不是连续存储的

二维数组的一行可以直接用 sort。

一列则先取到临时数组，排序后放回原列。

临时数组也放在全局，长度只需覆盖最大行数。

代码-满分

时间 \(O(nm(\log n+\log m))\)，空间 \(O(nm)\)。

#include <bits/stdc++.h>

using namespace std;

const int N = 15;

int a[N][N], column[N];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) cin >> a[i][j];
    }

    for (int i = 0; i < n; i++) sort(a[i], a[i] + m);

    // 一列不连续，我先取出来排序，再放回原位置。
    for (int j = 0; j < m; j++) {
        for (int i = 0; i < n; i++) column[i] = a[i][j];
        sort(column, column + n);
        for (int i = 0; i < n; i++) a[i][j] = column[i];
    }

    for (int i = 0; i < n; i++) {
        if (i) cout << '\n';
        for (int j = 0; j < m; j++) {
            if (j) cout << ' ';
            cout << a[i][j];
        }
    }

    return 0;
}