GESP C++ 四级历年真题题解

_Separation 2026-5-17 20:28:50 23 浏览 0 点赞 0 收藏

#GESP

GESP C++ 四级历年真题题解

1. 绝对素数

题目大意

如果一个两位数本身是素数，并且交换十位和个位后仍然是素数，则称为 绝对素数。给定 $A,B$ ，输出区间 $[A,B]$ 中所有绝对素数。

解题思路

枚举 $A$ 到 $B$ 中的每个数 $x$ 。

判断两个条件：

$x$ 是素数；
交换十位和个位后的数也是素数。

交换数字可以这样做：

rev = x % 10 \times 10 + x / 10

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
bool pri(int x) {
    if (x < 2) return false;
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) return false;
    }
    return true;
}
int a, b;
inline void solve() {
    cin >> a >> b;
    for (int x = a; x <= b; x++) {
        int y = x % 10 * 10 + x / 10;
        if (pri(x) && pri(y)) {
            printf("%d\n", x);
        }
    }
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

2. 填幻方

题目大意

给定一个奇数 $N$ ，按照题目给出的规则构造一个 $N \times N$ 的幻方。规则是先把 $1$ 填在第一行正中央，然后不断尝试向右上方移动，如果右上方已经有数，则改为向下移动。

解题思路

使用二维数组模拟。

当前位置为 $(r,c)$ 。

每次填完当前数字后，尝试移动到：

(r-1+n)%n,\ (c+1)%n

如果这个位置没有填过，就移动过去；否则移动到当前格子的下一行：

(r+1)%n,\ c

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e2 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, a[N][N];
inline void solve() {
    cin >> n;
    int r = 0;
    int c = n / 2;
    for (int x = 1; x <= n * n; x++) {
        a[r][c] = x;
        int nr = (r - 1 + n) % n;
        int nc = (c + 1) % n;
        if (a[nr][nc] == 0) {
            r = nr;
            c = nc;
        } else {
            r = (r + 1) % n;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (j) printf(" ");
            printf("%d", a[i][j]);
        }
        printf("\n");
    }
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

3. 幸运数

题目大意

一个正整数从个位开始编号，个位是第 $1$ 位。偶数位不变，奇数位要乘以 $7$ ，如果结果大于 $9$ ，就不断求数位和直到变成一位数。最后把所有变换后的数字求和，如果和是 $8$ 的倍数，则这个数是幸运数。

解题思路

因为数字小于 $10^{12}$ ，可以直接用字符串处理。

从右往左枚举每一位：

位置编号为奇数时，做乘 $7$ 并反复求数位和；
位置编号为偶数时，直接保留；
最后判断总和是否能被 $8$ 整除。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int digsum(int x) {
    int s = 0;
    while (x > 0) {
        s += x % 10;
        x /= 10;
    }
    return s;
}

int trans(int d) {
    int x = d * 7;
    while (x > 9) {
        x = digsum(x);
    }
    return x;
}
string s;
inline void solve() {
    cin >> s;
    int sum = 0;
    int pos = 1;
    for (int i = (int)s.size() - 1; i >= 0; i--) {
        int d = s[i] - '0';
        if (pos % 2 == 1) sum += trans(d);
        else sum += d;
        pos++;
    }
    if (sum % 8 == 0) printf("T\n");
    else printf("F\n");
    
}
int main() {
    int _ = 1; cin >> _;
    while (_--) solve();
    return 0;
}

4. B3851 图像压缩

题目大意

给定一幅 $256$ 级灰阶图像，每个像素由两位十六进制表示。现在要压缩成 $16$ 级灰阶：先选出出现次数最多的 $16$ 种灰阶，次数相同则灰阶值小的优先。其他灰阶转换到这 $16$ 种灰阶中灰度值最接近的一种；若距离相同，则选编号较小的。

解题思路

步骤如下：

读入所有像素，统计每个灰阶 $0\sim255$ 出现次数；
按照 次数多优先，灰阶小优先 排序，取前 $16$ 个；
输出这 $16$ 个灰阶的两位十六进制编码；
对每个原像素，找到距离最近的选中灰阶，输出它的编号。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int val(char c) {
    if ('0' <= c && c <= '9') return c - '0';
    return c - 'A' + 10;
}

string hx2(int x) {
    string s = "0123456789ABCDEF";
    string res;
    res += s[x / 16];
    res += s[x % 16];
    return res;
}

char hx1(int x) {
    string s = "0123456789ABCDEF";
    return s[x];
}
int n;
string img[N];
vector<vector<int> > pix(N);
vector<int> cnt(256, 0);
vector<int> all, use;
inline void solve() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> img[i];
        for (int j = 0; j < (int)img[i].size(); j += 2) {
            int x = val(img[i][j]) * 16 + val(img[i][j + 1]);
            pix[i].push_back(x);
            cnt[x]++;
        }
    }
    for (int i = 0; i < 256; i++) all.push_back(i);
    sort(all.begin(), all.end(), [&](int a, int b) {
        if (cnt[a] != cnt[b]) return cnt[a] > cnt[b];
        return a < b;
    });
    for (int i = 0; i < 16; i++) use.push_back(all[i]);
    for (int x : use) cout << hx2(x); 
    cout << '\n';
    for (int i = 0; i < n; i++) {
        for (int x : pix[i]) {
            int id = 0;
            int best = abs(x - use[0]);
            for (int j = 1; j < 16; j++) {
                int d = abs(x - use[j]);
                if (d < best) {
                    best = d;
                    id = j;
                }
            }
            cout << hx1(id);
        }
        cout << '\n';
    }
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

5. 进制转换

题目大意

输入 $N$ 个不同进制的数，每个数给出它的进制 $K$ 和表示形式，要求把它们转换成十进制数。进制范围为 $2$ 到 $16$ 。

解题思路

从左到右处理字符串，维护当前十进制值：

ans = ans \times K + 当前数码

其中 $\texttt{A}$ 到 $\texttt{F}$ 分别表示 $10$ 到 $15$ 。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int get(char c) {
    if ('0' <= c && c <= '9') return c - '0';
    return c - 'A' + 10;
}
int k;
string s;
inline void solve() {
    cin >> k >> s;
    LL Ans = 0;

    for (char c : s) {
        Ans = Ans * k + get(c);
    }
    printf("%lld\n", Ans);
}
int main() {
    int _ = 1; cin >> _;
    while (_--) solve();
    return 0;
}

6. 变长编码

题目大意

给定一个非负整数 $N$ ，按照题目中的变长编码规则输出它的编码结果。规则是将二进制数从低位到高位每 $7$ 位分组，每组前面加一个最高位；如果后面还有组，则最高位为 $1$ ，否则为 $0$ 。最后每个字节用两位十六进制输出。

解题思路

本质上就是不断取出 $N$ 的低 $7$ 位。

每次：

byte = N % 128

然后：

N = N / 128

如果取完这一组后 $N$ 还不为 $0$ ，说明后面还有字节，需要把最高位加上 $128$ 。

特殊情况： $N=0$ 时输出 $\texttt{00}$ 。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
string hx(int x) {
    string s = "0123456789ABCDEF";
    string res;
    res += s[x / 16];
    res += s[x % 16];
    return res;
}
LL n;
vector<int> Ans;
inline void solve() {
    cin >> n;
    if (n == 0) {
        Ans.push_back(0);
    } else {
        while (n > 0) {
            int b = n % 128;
            n /= 128;
            if (n > 0) b += 128;
            Ans.push_back(b);
        }
    }
    for (int i = 0; i < (int)Ans.size(); i++) {
        if (i) cout << ' ';
        cout << hx(Ans[i]);
    }
    cout << '\n';
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

7. 小杨的字典

题目大意

给定一本 A 语言到 B 语言的字典，再给定一段由小写单词和标点符号组成的文章。需要把文章中的每个单词翻译成对应的 B 语言单词；如果字典里没有，则替换成 $\texttt{UNK}$ 。标点符号原样保留。

解题思路

逐字符扫描文章：

如果是小写字母，就加入当前单词；
如果是标点，先把当前单词翻译输出，再输出标点；
扫描结束后，别忘了处理最后一个单词。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
bool ok(char c) {
    return 'a' <= c && c <= 'z';
}
int n;
string s;
map<string, string> mp;
inline void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        string a, b;
        cin >> a >> b;
        mp[a] = b;
    }
    cin >> s;
    string cur;
    for (char c : s) {
        if (ok(c)) {
            cur += c;
        } else {
            if (!cur.empty()) {
                if (mp.count(cur)) cout << mp[cur];
                else cout << "UNK";
                cur.clear();
            }
            cout << c;
        }
    }
    if (!cur.empty()) {
        if (mp.count(cur)) cout << mp[cur];
        else cout << "UNK";
    }
    cout << '\n';
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

8. 田忌赛马

题目大意

你和田忌各有 $N$ 匹马，田忌会按给定顺序出马。你可以安排自己的出马顺序，求最多能赢几轮。所有马匹速度两两不同，不会出现平局。

解题思路

贪心策略：

对于田忌当前出的一匹马，使用自己 刚好能赢它的最慢马 。

如果没有马能赢它，就派出自己当前最慢的马牺牲。

用 $\text{multiset}$ 维护自己的马速，每次用 $\text{upper_bound(v)}$ 找到第一匹速度大于 $v$ 的马。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, v[N];
multiset<int> st;
inline void solve() {
    cin >> n;
    for (int i = 1, x; i <= n; i++) {
        cin >> x;
        st.insert(x);
    }
    for (int i = 1; i <= n; i++) cin >> v[i];
    int Ans = 0;
    for (int i = 1; i <= n; i++) {
        auto it = st.upper_bound(v[i]);
        if (it != st.end()) {
            Ans++;
            st.erase(it);
        } else {
            st.erase(st.begin());
        }
    }
    printf("%d\n", Ans);
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

或者用双指针

#include <stdio.h>
#include <iostream>
#include <string>
#include <string.h>
#include <map>
#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n;
int u[N], v[N];
inline void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> u[i];
    for (int i = 1; i <= n; i++) cin >> v[i];
    sort(u + 1, u + n + 1);
    sort(v + 1, v + n + 1);
    int i = 1, j = 1;
    int Ans = 0;
    while (i <= n && j <= n) {
        if (u[i] < v[j]) i++;
        else {
            i++, j++;
            Ans++;
        }
    }
    printf("%d\n", Ans);
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

9. 相似字符串

题目大意

如果字符串 $A$ 可以通过删除一个字符、插入一个字符或修改一个字符变成字符串 $B$ ，则称它们相似。两个完全相同的字符串也算相似。判断多组字符串是否相似。

解题思路

分情况讨论：

长度相同：最多只能有一个位置不同；
长度差为 $1$ ：用双指针判断较长串能否删除一个字符变成较短串；
长度差超过 $1$ ：一定不相似。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
bool sameLen(string a, string b) {
    int cnt = 0;
    for (int i = 0; i < (int)a.size(); i++) {
        if (a[i] != b[i]) cnt++;
    }
    return cnt <= 1;
}
bool diffOne(string a, string b) {
    if (a.size() < b.size()) swap(a, b);
    int i = 0, j = 0;
    int cnt = 0;
    while (i < (int)a.size() && j < (int)b.size()) {
        if (a[i] == b[j]) {
            i++, j++;
        } else {
            cnt++, i++;
        }
    }
    return cnt <= 1;
}
bool check(string a, string b) {
    int x = a.size();
    int y = b.size();
    if (abs(x - y) > 1) return false;
    if (x == y) return sameLen(a, b);
    return diffOne(a, b);
}
string a, b;
inline void solve() {
    cin >> a >> b;
    if (check(a, b)) printf("similar\n");
    else printf("not similar\n");
}
int main() {
    int _ = 1; cin >> _;
    while (_--) solve();
    return 0;
}

10. 做题

题目大意

第 $k$ 天小杨必须完成 $k$ 道题。现在有 $n$ 套题单，每套题单只能用一次，每天最多用一套题单。对于一套题单，不必做完全部题。求小杨最多能坚持多少天。

解题思路

贪心。

把题单题数从小到大排序。

当前想完成第 $day$ 天，需要找到一套题数至少为 $day$ 的题单。从小到大扫描，能用就用，这样不会浪费大题单。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n;
LL a[N];
inline void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    int day = 1;
    for (int i = 1; i <= n; i++) {
        if (a[i] >= day) {
            day++;
        }
    }
    printf("%d\n", day - 1);
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

11. 黑白方块

题目大意

给定一个 $n \times m$ 的黑白网格。黑格和白格数量相同的子矩形称为平衡子矩形。求最大的平衡子矩形包含多少个格子。数据范围 $n,m \le 10$ 。

解题思路

把白色 $\texttt{0}$ 看成 $-1$ ，黑色 $\texttt{1}$ 看成 $1$ 。

这样一个子矩形中黑白数量相同，等价于这个子矩形的和为 $0$ 。

用二维前缀和快速求任意子矩形的和，然后枚举所有子矩形。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e3 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, m, sum[N][N];
inline void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        for (int j = 1; j <= m; j++) {
            int v = (s[j - 1] == '1') ? 1 : -1;
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + v;
        }
    }
    int Ans = 0;
    for (int x1 = 1; x1 <= n; x1++) {
        for (int y1 = 1; y1 <= m; y1++) {
            for (int x2 = x1; x2 <= n; x2++) {
                for (int y2 = y1; y2 <= m; y2++) {
                    int Sum = sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1];
                    if (Sum == 0) {
                        Ans = max(Ans, (x2 - x1 + 1) * (y2 - y1 + 1));
                    }
                }
            }
        }
    }
    printf("%d\n", Ans);
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

12. 宝箱

题目大意

有 $n$ 个宝箱，第 $i$ 个价值为 $a_i$ 。选择一些宝箱放入背包，要求所选宝箱最大价值和最小价值的差不超过 $k$ 。求能带走的宝箱总价值最大是多少。

解题思路

因为宝箱价值都是正数，只要某个区间内的宝箱价值差不超过 $k$ ，就应该全部拿走。

先排序，再用双指针维护一个满足：

a_r-a_l \le k

的区间，同时维护区间和。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, k, a[N];
inline void solve() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    LL Ans = 0, sum = 0;
    int l = 1;
    for (int r = 1; r <= n; r++) {
        sum += a[r];
        while (a[r] - a[l] > k) {
            sum -= a[l];
            l++;
        }
        Ans = max(Ans, sum);
    }
    printf("%lld\n", Ans);
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

13. 黑白方块

题目大意

判断一个黑白网格中是否存在一个 $4 \times 4$ 子矩形，形状必须为：

其中 $\texttt{0}$ 表示白色， $\texttt{1}$ 表示黑色。

解题思路

直接枚举每个可能的左上角 $(i,j)$ 。

检查它对应的 $4 \times 4$ 子矩形是否等于目标图案。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e3 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
bool check(vector<string> &g, int x, int y) {
    string p[4] = {
        "0000",
        "0110",
        "0110",
        "0000"
    };
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            if (g[x + i][y + j] != p[i][j]) {
                return false;
            }
        }
    }
    return true;
}
int n, m;
vector<string> g(N);
inline void solve() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> g[i];
    bool ok = false;
    for (int i = 0; i + 3 < n; i++) {
        for (int j = 0; j + 3 < m; j++) {
            if (check(g, i, j)) {
                ok = true;
            }
        }
    }
    if (ok) printf("Yes\n");
    else printf("No\n");
}
int main() {
    int _ = 1; cin >> _;
    while (_--) solve();
    return 0;
}

14. 区间排序

题目大意

给定一个长度为 $n$ 的序列，接着进行 $q$ 次操作。每次给定区间 $[l,r]$ ，把这个区间内的数字升序排序。求所有操作后的序列。数据范围 $n,q \le 100$ 。

解题思路

数据很小，直接模拟即可。

每次读入 $l,r$ 后调用：

sort(a + l, a + r + 1);

注意如果数组从 $1$ 开始存，下标正好对应题目。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, a[N], q;
inline void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        sort(a + l, a + r + 1);
    }
    for (int i = 1; i <= n; i++) {
        if (i > 1) printf(" ");
        printf("%d", a[i]);
    }
    printf("\n");
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

15. Recamán

题目大意

Recamán 数列定义为： $a_1=1$ 。对于第 $k$ 项，如果 $a_{k-1}-k$ 是正整数且没出现过，则 $a_k=a_{k-1}-k$ ；否则 $a_k=a_{k-1}+k$ 。给定 $n$ ，输出前 $n$ 项从小到大排序后的结果。

解题思路

按照定义模拟生成前 $n$ 项。

用 $\text{set}$ 记录已经出现过的值。

生成完成后排序输出。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n;
vector<int> a;
set<int> vis;
inline void solve() {
    cin >> n;
    int last = 1;
    a.push_back(last);
    vis.insert(last);
    for (int k = 2; k <= n; k++) {
        int x = last - k;
        if (x > 0 && !vis.count(x)) {
            last = x;
        } else {
            last = last + k;
        }
        a.push_back(last);
        vis.insert(last);
    }
    sort(a.begin(), a.end());
    for (int i = 0; i < n; i++) {
        if (i) printf(" ");
        printf("%d", a[i]);
    }
    printf("\n");
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

16. 字符排序

题目大意

给定 $n$ 个只含小写字母的字符串，问能否把这些字符串按某种顺序拼接成一个整体非降字符串。也就是拼接后的每个字符都不小于前一个字符。

解题思路

要让最终字符串非降，需要满足两点：

每个字符串内部本身必须是非降的；
字符串之间可以按顺序连接，即前一个字符串的最后字符不大于后一个字符串的第一个字符。

因此先检查每个字符串内部是否非降。

然后按每个字符串的首字符排序，首字符相同则按尾字符排序。最后检查相邻两个字符串是否能连接。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
bool inside(string s) {
    for (int i = 1; i < (int)s.size(); i++) {
        if (s[i] < s[i - 1]) return false;
    }
    return true;
}
int n;
inline void solve() {
    cin >> n;
    vector<string> s(n);
    bool ok = true;
    for (int i = 0; i < n; i++) {
        cin >> s[i];
        if (!inside(s[i])) {
            ok = false;
        }
    }
    sort(s.begin(), s.end(), [](string a, string b) {
        if (a[0] != b[0]) return a[0] < b[0];
        return a.back() < b.back();
    });
    for (int i = 1; i < n; i++) {
        if (s[i - 1].back() > s[i][0]) {
            ok = false;
        }
    }
    printf("%d\n", (ok ? 1 : 0));
}
int main() {
    int _ = 1; cin >> _;
    while (_--) solve();
    return 0;
}

17. 荒地开垦

题目大意

一个 $n \times m$ 网格中， $\texttt{.}$ 表示荒地， $\texttt{#}$ 表示杂物。一块荒地可以开垦，当且仅当它上下左右相邻的格子都不是杂物。现在最多可以清除一个杂物，求最多能开垦多少块荒地。

解题思路

先计算不清除杂物时有多少块可开垦荒地，记为 $\text{base}$ 。

如果清除某个 $\texttt{#}$ ，只会影响它自己和上下左右最多 $4$ 个格子的可开垦状态，其他格子不变。

所以枚举每个 $\texttt{#}$ ，只重新计算这最多 $5$ 个格子的贡献变化。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, m;
vector<string> g;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
bool inside(int x, int y) {
    return 0 <= x && x < n && 0 <= y && y < m;
}
bool good(int x, int y, int cx, int cy) {
    if (g[x][y] == '#' && !(x == cx && y == cy)) {
        return false;
    }
    for (int d = 0; d < 4; d++) {
        int nx = x + dx[d];
        int ny = y + dy[d];
        if (!inside(nx, ny)) continue;
        if (g[nx][ny] == '#' && !(nx == cx && ny == cy)) {
            return false;
        }
    }
    return true;
}
inline void solve() {
    cin >> n >> m;
    g.resize(n);
    for (int i = 0; i < n; i++) cin >> g[i];
    int base = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (good(i, j, -1, -1)) {
                base++;
            }
        }
    }
    int Ans = base;
    for (int x = 0; x < n; x++) {
        for (int y = 0; y < m; y++) {
            if (g[x][y] != '#') continue;
            vector<pair<int, int> > cells;
            cells.push_back({x, y});
            for (int d = 0; d < 4; d++) {
                int nx = x + dx[d];
                int ny = y + dy[d];
                if (inside(nx, ny)) {
                    cells.push_back({nx, ny});
                }
            }
            sort(cells.begin(), cells.end());
            cells.erase(unique(cells.begin(), cells.end()), cells.end());
            int cur = base;
            for (auto p : cells) {
                int i = p.first;
                int j = p.second;
                if (good(i, j, -1, -1)) cur--;
                if (good(i, j, x, y)) cur++;
            }
            Ans = max(Ans, cur);
        }
    }
    printf("%d\n", Ans);
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

18. 二阶矩阵

题目大意

给定一个 $n \times m$ 矩阵，统计其中有多少个 $2 \times 2$ 子矩阵满足：

D_{1,1}\times D_{2,2}=D_{1,2}\times D_{2,1}

解题思路

直接枚举所有相邻的 $2 \times 2$ 子矩阵。

对于左上角为 $(i,j)$ 的子矩阵，判断：

$$a_{i,j}\times a_{i+1,j+1}=a_{i,j+1}\times a_{i+1,j} $$

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e3 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, m;
LL a[N][N];
inline void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    LL Ans = 0;
    for (int i = 1; i + 1 <= n; i++) {
        for (int j = 1; j + 1 <= m; j++) {
            if (a[i][j] * a[i + 1][j + 1] == a[i][j + 1] * a[i + 1][j]) {
                Ans++;
            }
        }
    }
    printf("%lld\n", Ans);
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

19. 画布裁剪

题目大意

给定一个 $h \times w$ 的字符矩阵，以及保留区域的边界 $x_1,x_2,y_1,y_2$ ，输出这个子矩阵。

解题思路

直接按照给定范围输出：

行从 $x_1$ 到 $x_2$ ，列从 $y_1$ 到 $y_2$ 。

注意题目下标从 $1$ 开始，字符串下标从 $0$ 开始，所以访问时列要减 $1$ 。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int h, w, xx1, xx2, yy1, yy2;
inline void solve() {
    cin >> h >> w >> xx1 >> xx2 >> yy1 >> yy2;
    vector<string> s(h + 1);
    for (int i = 1; i <= h; i++) cin >> s[i];
    for (int i = xx1; i <= xx2; i++) {
        for (int j = yy1; j <= yy2; j++) {
            cout << s[i][j - 1];
        }
        cout << '\n';
    }
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

20. 排序

题目大意

有 $n$ 名同学排成一队，每人有身高和体重。目标顺序为：身高从高到低；如果身高相同，则体重从重到轻。每次只能交换相邻两人，求最少交换次数。

解题思路

相邻交换排序的最少次数等于 逆序对数量 。

对于原队伍中的两个人 $i<j$ ，如果第 $j$ 个人在目标排序中应该排在第 $i$ 个人前面，那么这两个人最终一定要交换一次相对顺序。

也就是满足：

$h_j > h_i$ ；
或者 $h_j = h_i$ 且 $w_j > w_i$ 。

直接 $O(n^2)$ 统计即可， $n \le 3000$ 可以通过。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
struct Stu {
    LL h, w;
}a[N];
int n;
inline void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].h >> a[i].w;
    }
    LL Ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (a[j].h > a[i].h || (a[j].h == a[i].h && a[j].w > a[i].w)) {
                Ans++;
            }
        }
    }
    printf("%lld\n", Ans);
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

21. 排兵布阵

题目大意

给定一个 $n \times m$ 的 $0/1$ 矩阵， $\texttt{1}$ 表示适合排兵， $\texttt{0}$ 表示不适合排兵。需要选择一个全是 $\texttt{1}$ 的矩形区域，求最大面积。

解题思路

数据范围 $n,m \le 12$ ，可以直接枚举所有矩形。

用二维前缀和快速计算矩形内 $\texttt{1}$ 的数量。

如果某个矩形内 $\texttt{1}$ 的数量等于矩形面积，说明它全是 $\texttt{1}$ 。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e3 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, m, sum[N][N];
inline void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1, x; j <= m; j++) {
            cin >> x;
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + x;
        }
    }
    int Ans = 0;
    for (int x1 = 1; x1 <= n; x1++) {
        for (int y1 = 1; y1 <= m; y1++) {
            for (int x2 = x1; x2 <= n; x2++) {
                for (int y2 = y1; y2 <= m; y2++) {
                    int area = (x2 - x1 + 1) * (y2 - y1 + 1);
                    int Sum = sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1];
                    if (Sum == area) {
                        Ans = max(Ans, area);
                    }
                }
            }
        }
    }
    printf("%d\n", Ans);
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

22. 最长连续段

题目大意

给定一个数组，可以任意重排元素顺序。问重排后，所有连续段子数组中最长长度是多少。连续段要求相邻元素满足：

b_{i+1}=b_i+1

解题思路

因为可以任意重排，所以问题变成：

数组中最多能选出多少个不同的整数，使它们构成一段连续整数。

重复数字不能同时出现在同一个连续段里。

因此：

排序；
去重；
统计最长的连续整数段。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n;
inline void solve() {
    cin >> n;
    vector<LL> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());
    int Ans = 1, cur = 1;
    for (int i = 1; i < (int)a.size(); i++) {
        if (a[i] == a[i - 1] + 1) {
            cur++;
        } else {
            cur = 1;
        }
        Ans = max(Ans, cur);
    }
    printf("%d\n", Ans);
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

23. 建造

题目大意

给定一个 $M \times N$ 的高度矩阵。停机坪是一个 $3 \times 3$ 区域，要求这个区域中最大高度和最小高度之差不超过 $H$ 。在所有合法区域中，求 $9$ 个点的高度和最大值。

解题思路

直接枚举每个 $3 \times 3$ 区域的左上角。

对区域内 $9$ 个数求：

最大值；
最小值；
总和。

如果：

max-min \le H

就用它的总和更新答案。

复杂度为 $O(MN \times 9)$ ，可以通过。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e3 + 10, inf = 1e9 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int m, n, h, a[N][N];
inline void solve() {
    cin >> m >> n >> h;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
        }
    }
    LL Ans = 0;
    for (int i = 1; i + 2 <= m; i++) {
        for (int j = 1; j + 2 <= n; j++) {
            int mx = 0, mn = inf;
            LL sum = 0;
            for (int x = i; x <= i + 2; x++) {
                for (int y = j; y <= j + 2; y++) {
                    mx = max(mx, a[x][y]);
                    mn = min(mn, a[x][y]);
                    sum += a[x][y];
                }
            }
            if (mx - mn <= h) {
                Ans = max(Ans, sum);
            }
        }
    }
    printf("%lld\n", Ans);
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

24. 优先购买

题目大意

有 $N$ 个商品，每个商品有名称、价格和优先级。优先级数字越小，优先级越高。小 A 按如下顺序考虑商品：优先级高的优先；优先级相同，价格低的优先；仍相同，名字字典序小的优先。若当前商品买得起就购买，否则跳过。最后把买到的商品名按字典序输出。

解题思路

先按照购买优先顺序排序：

优先级 $V$ 从小到大；
价格 $P$ 从小到大；
名字 $S$ 字典序从小到大。

然后依次判断预算是否足够：

如果够，买下并扣钱；
如果不够，跳过。

最后把买到的商品名排序输出。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
struct Item {
    string s;
    int p, v;
}a[N];
int m, n;
vector<string> buy;
inline void solve() {
    cin >> m >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].s >> a[i].p >> a[i].v;
    }
    sort(a + 1, a + n + 1, [](Item A, Item B) {
        if (A.v != B.v) return A.v < B.v;
        if (A.p != B.p) return A.p < B.p;
        return A.s < B.s;
    });
    for (int i = 1; i <= n; i++) {
        if (m >= a[i].p) {
            m -= a[i].p;
            buy.push_back(a[i].s);
        }
    }
    sort(buy.begin(), buy.end());
    for (int i = 0; i < (int)buy.size(); i++) {
        if (i) cout << '\n';
        cout << buy[i];
    }
    cout << '\n';
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

25. 山之谷

题目大意

给定一个 $N \times M$ 的海拔矩阵。如果一个格子的海拔不高于它所有相邻格子的海拔，则称它为山谷。相邻包括八个方向。求山谷数量。

解题思路

枚举每个格子 $(i,j)$ 。

再枚举八个方向的相邻格子。

如果存在某个相邻格子的海拔比当前格子低，则当前格子不是山谷。

否则它就是山谷。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e3 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
int n, m, h[N][N];
inline void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> h[i][j];
        }
    }
    int Ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            bool ok = true;
            for (int d = 0; d < 8; d++) {
                int x = i + dx[d];
                int y = j + dy[d];
                if (x < 1 || x > n || y < 1 || y > m) continue;
                if (h[i][j] > h[x][y]) {
                    ok = false;
                }
            }
            if (ok) Ans++;
        }
    }
    printf("%d\n", Ans);
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

26. 礼盒排序

题目大意

有 $n$ 个礼盒，每个礼盒有 $k$ 件商品。排序规则依次为：总价格从小到大；总价格相同则最贵商品价格从小到大；仍相同则最便宜商品价格从小到大；仍相同则礼盒编号从小到大。输出排序后的礼盒编号。

解题思路

对每个礼盒预处理出：

编号；
总价；
最大商品价格；
最小商品价格。

然后按照题目规则排序即可。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10, inf = 1e9 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
struct Box {
    int id, sum, mx, mn;
}a[N];
int n, k;
inline void solve() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        a[i].id = i, a[i].sum = 0, a[i].mx = 0, a[i].mn = inf;
        for (int j = 1, x; j <= k; j++) {
            cin >> x;
            a[i].sum += x;
            a[i].mx = max(a[i].mx, x);
            a[i].mn = min(a[i].mn, x);
        }
    }
    sort(a + 1, a + n + 1, [](Box A, Box B) {
        if (A.sum != B.sum) return A.sum < B.sum;
        if (A.mx != B.mx) return A.mx < B.mx;
        if (A.mn != B.mn) return A.mn < B.mn;
        return A.id < B.id;
    });
    for (int i = 1; i <= n; i++) {
        if (i != 1) cout << ' ';
        cout << a[i].id;
    }
    cout << '\n';
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}