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

1. 逛商场

题目大意

小明有 $X$ 元钱，依次遇到 $N$ 件想买的物品。
如果当前钱够买某件物品，就买下来，并扣掉对应价格；否则跳过。
求最后一共买了多少件物品。

解题思路

按顺序模拟即可。

对于每个价格 $a_i$：

• 如果 $X \ge a_i$，说明可以买；
• 答案加 $1$；
• 钱数减少 $a_i$。

代码

#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], x;
inline void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    cin >> x;
    int Ans = 0;
    for (int i = 1; i <= n; i++) {
        if (x >= a[i]) {
            x -= a[i];
            Ans++;
        }
    }
    printf("%d\n", Ans);
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

2. 进制转换

题目大意

给定十进制正整数 $N$ 和进制 $R$，其中 $2 \le R \le 36$，输出 $N$ 的 $R$ 进制表示。

超过 $9$ 的数字用大写字母表示：

• $10$ 用 $\texttt{A}$；
• $11$ 用 $\texttt{B}$；
• $\cdots$
• $35$ 用 $\texttt{Z}$。

解题思路

不断对 $R$ 取余。

例如：

$$N \bmod R$$

就是当前最低位。

然后令：

$$N = N / R$$

继续处理。

由于先得到的是低位，所以最后要反转字符串。

代码

#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;
}
char gc(int x) {
    if (x <= 9) return char('0' + x);
    return char('A' + x - 10);
}
int n, r;
inline void solve() {
    cin >> n >> r;
    string Ans;
    while (n > 0) {
        Ans += gc(n % r);
        n /= r;
    }
    reverse(Ans.begin(), Ans.end());
    cout << Ans << '\n';
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

3. 春游

题目大意

班上有 $N$ 位同学，编号为 $0$ 到 $N-1$。 集合时，同学们一共报出了 $M$ 次编号，已经到达的同学可能会重复报编号。 要求输出没有到达的同学编号。

如果所有同学都到了，输出 $N$。

解题思路

用数组 $\text{vis}$ 记录某个编号是否出现过。

读入每个编号 $x$ 后，令：

vis[x] = true;

最后从 $0$ 到 $N-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, m, vis[N];
inline void solve() {
    cin >> n >> m;
    for (int i = 1, x; i <= m; i++) {
        cin >> x;
        vis[x] = 1;
    }
    bool all = true;
    bool first = true;
    for (int i = 0; i < n; i++) {
        if (!vis[i]) {
            all = false;
            if (!first) printf(" ");
            printf("%d", i);
            first = false;
        }
    }
    if (all) printf("%d\n", n);
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

4. 密码合规

题目大意

输入一个用英文逗号分隔的字符串，每一段都是一个待检测密码。 合规密码需要满足：

1. 长度在 $6$ 到 $12$ 之间；
2. 只能包含小写字母、大写字母、数字、\texttt{!@#\$}；
3. 大写字母、小写字母、数字三类中至少包含两类；
4. 至少包含一个特殊字符 \texttt{!@#\$}。

输出所有合规密码。

解题思路

先按照逗号 $\texttt{,}$ 把字符串切分成多个密码。

对每个密码检查：

• 长度是否合法；
• 是否有非法字符；
• 是否包含大写字母；
• 是否包含小写字母；
• 是否包含数字；
• 是否包含特殊字符。

如果满足条件，就输出。

代码

#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 check(string s) {
    if (s.size() < 6 || s.size() > 12) return false;
    bool Low = false, Up = false, Num = false, Spe = false;
    for (char c : s) {
        if ('a' <= c && c <= 'z') Low = true;
        else if ('A' <= c && c <= 'Z') Up = true;
        else if ('0' <= c && c <= '9') Num = true;
        else if (c == '!' || c == '@' || c == '#' || c == '$') Spe = true;
        else return false;
    }
    int Cnt = 0;
    if (Low) Cnt++;
    if (Up) Cnt++;
    if (Num) Cnt++;
    return Cnt >= 2 && Spe;
}
inline void solve() {
    string s;
    cin >> s;
    string cur;
    for (int i = 0; i <= (int)s.size(); i++) {
        if (i == (int)s.size() || s[i] == ',') {
            if (check(cur)) {
                cout << cur << '\n';
            }
            cur.clear();
        } else {
            cur += s[i];
        }
    }
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

5. 小杨的储蓄

题目大意

小杨有 $N$ 个储蓄罐，编号为 $0$ 到 $N-1$。 第 $i$ 天，他会往编号为 $a_i$ 的储蓄罐里存入 $i$ 元。 给定 $D$ 天的存钱记录，输出每个储蓄罐最后的钱数。

解题思路

用数组 $\text{s}$ 存每个储蓄罐的钱数。

第 $i$ 天读入 $x$，表示存入编号为 $x$ 的储蓄罐：

$$s_x = s_x + i$$

最后输出整个数组。

代码

#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, d, s[N];
inline void solve() {
    cin >> n >> d;
    for (int i = 1, x; i <= d; i++) {
        cin >> x;
        s[x] += i;
    }
    for (int i = 0; i < n; i++) {
        if (i) printf(" ");
        printf("%d", s[i]);
    }
    printf("\n");
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

6. 进制判断

题目大意

给定若干字符串，判断它们是否可能是：

1. 二进制数；
2. 八进制数；
3. 十进制数；
4. 十六进制数。

字符串可能有前导零，只包含数字和大写字母。

解题思路

分别检查每个字符是否符合对应进制要求：

• 二进制：只能有 $\text{0}$、$\text{1}$；
• 八进制：只能有 $\text{0}$ 到 $\text{7}$；
• 十进制：只能有 $\text{0}$ 到 $\text{9}$；
• 十六进制：只能有 $\text{0}$ 到 $\text{9}$ 和 $\texttt{A}$ 到 $\texttt{F}$。

每个字符串输出四个 $\text{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;
}
bool ok2(char c) {return c == '0' || c == '1';}
bool ok8(char c) {return '0' <= c && c <= '7';}
bool ok10(char c) {return '0' <= c && c <= '9';}
bool ok16(char c) {return ('0' <= c && c <= '9') || ('A' <= c && c <= 'F');}
string s;
inline void solve() {
    cin >> s;
    int a = 1, b = 1, c = 1, d = 1;
    for (char ch : s) {
        if (!ok2(ch)) a = 0;
        if (!ok8(ch)) b = 0;
        if (!ok10(ch)) c = 0;
        if (!ok16(ch)) d = 0;
    }
    printf("%d %d %d %d\n", a, b, c, d);
}
int main() {
    int _ = 1; cin >> _;
    while (_--) solve();
    return 0;
}

7. 小猫分鱼

题目大意

有 $N$ 只小猫分一堆鱼。 每只小猫依次进行如下操作：

1. 把当前鱼分成 $N$ 份；
2. 多出 $i$ 条鱼，把这 $i$ 条鱼扔掉；
3. 自己拿走其中一份；
4. 剩下的鱼给下一只小猫继续分。

求最少一开始有多少条鱼，使得每只小猫都能吃到鱼。

解题思路

这题正向枚举初始鱼数很慢，可以从最后一只小猫倒推。

假设最后一只小猫拿走了 $x$ 条鱼。 那么最后一只小猫分之前，应有：

$$x \times N + i$$

条鱼。

如果已知某只小猫操作后的鱼数为 $cur$，那么操作前的鱼数应满足：

$$cur = (N - 1) \times p$$

所以 $cur$ 必须能被 $N-1$ 整除。 操作前鱼数为：

$$\frac{cur}{N-1} \times N + 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;
}
LL n, i;
inline void solve() {
    cin >> n >> i;
    for (LL x = 1; ; x++) {
        LL cur = x * n + i;
        bool ok = true;
        for (int j = 1; j <= n - 1; j++) {
            if (cur % (n - 1) != 0) {
                ok = false;
                break;
            }
            cur = cur / (n - 1) * n + i;
        }
        if (ok) {
            printf("%lld\n", cur);
            break;
        }
    }
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

8. 单位转换

题目大意

输入若干个单位转换题，格式为：

x 单位1 = ? 单位2

只会从大单位转成小单位。 长度单位包括 $\text{km}$、$\text{m}$、$\text{mm}$。 重量单位包括 $\text{kg}$、$\text{g}$、$\text{mg}$。

要求把 $\text{?}$ 替换成正确答案，其余内容原样输出。

解题思路

把每个单位转换成最小单位的倍数：

长度：

• $\text{mm = 1}$
• $\text{m = 1000}$
• $\text{km = 1000000}$

重量：

• $\text{mg = 1}$
• $\text{g = 1000}$
• $\text{kg = 1000000}$

答案为：

$$x \times \frac{value[单位1]}{value[单位2]}$$

代码

#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;
}
LL x;
string u1, eq, q, u2;
map<string, LL> mp;
inline void solve() {
    cin >> x >> u1 >> eq >> q >> u2;
    LL Ans = x * mp[u1] / mp[u2];
    cout << x << ' ' << u1 << " = " << Ans << ' ' << u2 << '\n';
}
int main() {
    mp["mm"] = 1;
    mp["m"] = 1000;
    mp["km"] = 1000000;
    mp["mg"] = 1;
    mp["g"] = 1000;
    mp["kg"] = 1000000;
    int _ = 1; cin >> _;
    while (_--) solve();
    return 0;
}

9. 字母求和

题目大意

给定一个只包含大小写字母的字符串。 每个小写字母代表它在字母表中的位置：

$$a=1,b=2,\ldots,z=26$$

每个大写字母代表它的 ASCII 码的相反数。

求所有字符对应数值的总和。

解题思路

逐个字符处理：

• 如果是小写字母，贡献为：

$$c - \texttt{a} + 1$$

• 如果是大写字母，贡献为：

$$-ASCII(c)$$

在 C++ 中，字符可以直接转换成整数。

代码

#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;
string s;
inline void solve() {
    cin >> n >> s;
    LL Ans = 0;
    for (char c : s) {
        if ('a' <= c && c <= 'z') {
            Ans += c - 'a' + 1;
        } else {
            Ans -= (int)c;
        }
    }
    printf("%lld\n", Ans);
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

10. 完全平方数

题目大意

给定一个长度为 $n$ 的非负整数序列 $A$。 统计有多少对下标 $(i,j)$，满足：

$$1 \le i < j \le n$$

并且：

$$A_i + A_j$$

是完全平方数。

解题思路

因为 $n \le 1000$，可以直接枚举所有二元组。

对于每一对 $(i,j)$：

1. 计算 $s = A_i + A_j$；
2. 令 $x = \sqrt{s}$；
3. 如果 $x \times x = 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;
}
bool ok(int x) {
    int t = sqrt(x);
    return t * t == x;
}
int n, a[N];
inline void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    LL Ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (ok(a[i] + a[j])) {
                Ans++;
            }
        }
    }
    printf("%lld\n", Ans);
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

11. 移位

题目大意

给定偏移量 $n$，把大写字母表：

ABCDEFGHIJKLMNOPQRSTUVWXYZ

整体向后偏移 $n$ 位，输出偏移后的字母表。

例如 $n=3$ 时，输出：

DEFGHIJKLMNOPQRSTUVWXYZABC

解题思路

对每个字母编号 $0$ 到 $25$。

偏移后的位置为：

$$(i+n) \bmod 26$$

输出对应字符即可。

代码

#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;
    n %= 26;
    for (int i = 0; i < 26; i++) {
        printf("%c", ('A' + (i + n) % 26));
    }
    printf("\n");
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

12. 寻找倍数

题目大意

给定一个正整数序列 $A$。 判断是否存在某个 $a_i$，使得它是序列中所有数的倍数。

也就是对于所有 $a_k$，都有：

$$a_i \bmod a_k = 0$$

解题思路

如果一个数是所有数的倍数，那么它一定不小于所有数。 所以只需要检查序列最大值是否能被所有数整除。

设最大值为 $mx$，如果对所有 $a_i$ 都满足：

$$mx \bmod a_i = 0$$

则输出 $\texttt{Yes}$，否则输出 $\texttt{No}$。

代码

#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], mx;
inline void solve() {
    cin >> n;
    mx = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        mx = max(mx, a[i]);
    }
    bool ok = true;
    for (int i = 1; i <= n; i++) {
        if (mx % a[i] != 0) {
            ok = false;
            break;
        }
    }
    if (ok)printf("Yes\n");
    else printf("No\n");
}
int main() {
    int _ = 1; cin >> _;
    while (_--) solve();
    return 0;
}

13. 平衡序列

题目大意

给定一个长度为 $n$ 的正整数序列。 判断是否存在一个位置 $i$，满足：

$$1 \le i < n$$

并且：

$$a_1+a_2+\cdots+a_i = a_{i+1}+a_{i+2}+\cdots+a_n$$

如果存在，输出 $\texttt{Yes}$，否则输出 $\texttt{No}$。

解题思路

先求总和 $sum$。

然后从左到右维护前缀和 $pre$。

如果某个位置满足：

$$pre = sum - pre$$

说明左右两部分和相等。

注意 $i < n$，所以只能枚举到 $n-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];
inline void solve() {
    cin >> n;
    LL sum = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum += a[i];
    }
    LL pre = 0;
    bool ok = false;
    for (int i = 1; i < n; i++) {
        pre += a[i];
        if (pre == sum - pre) {
            ok = true;
            break;
        }
    }
    if (ok) printf("Yes\n");
    else printf("No\n");
}
int main() {
    int _ = 1; cin >> _;
    while (_--) solve();
    return 0;
}

14. 回文拼接

题目大意

给定若干个小写字母字符串。 判断每个字符串是否可以由两个长度至少为 $2$ 的回文串前后拼接而成。

解题思路

枚举分割点。

假设字符串长度为 $len$。 第一个回文串长度至少为 $2$，第二个回文串长度也至少为 $2$，所以分割点 $p$ 的范围是：

$$2 \le p \le len-2$$

判断：

• $s[0 \ldots p-1]$ 是否回文；
• $s[p \ldots len-1]$ 是否回文。

只要存在一种分割方式满足条件，就输出 $\texttt{Yes}$。

代码

#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 isPal(string s, int l, int r) {
    while (l < r) {
        if (s[l] != s[r]) return false;
        l++;
        r--;
    }
    return true;
}
int n;
string s;
inline void solve() {
    cin >> s;
    n = s.size();
    bool ok = false;
    for (int p = 2; p <= n - 2; p++) {
        if (isPal(s, 0, p - 1) && isPal(s, p, n - 1)) {
            ok = true;
            break;
        }
    }
    if (ok) printf("Yes\n");
    else printf("No\n");
}
int main() {
    int _ = 1; cin >> _;
    while (_--) solve();
    return 0;
}

15. 数字替换

题目大意

给定一个长度为 $n$ 的整数序列 $A$ 和一个整数 $k$。

替换规则：

• 大于 $k$ 的数替换为原序列最大值；
• 小于 $k$ 的数替换为原序列最小值；
• 等于 $k$ 的数不变。

输出替换后的序列。

解题思路

先遍历数组，求出最小值 $mn$ 和最大值 $mx$。

再遍历一次：

• 如果 $a_i > k$，输出 $mx$；
• 如果 $a_i < k$，输出 $mn$；
• 否则输出 $a_i$。

代码

#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;
}
int n, k, a[N];
inline void solve() {
    cin >> n >> k;
    int mn = inf;
    int mx = -inf;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        mn = min(mn, a[i]);
        mx = max(mx, a[i]);
    }
    for (int i = 1; i <= n; i++) {
        if (i != 1) printf(" ");
        if (a[i] > k) printf("%d", mx);
        else if (a[i] < k) printf("%d", mn);
        else printf("%d", a[i]);
    }
    printf("\n");
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

16. 打印数字

题目大意

给定一个只由数字 $0$、$1$、$2$、$3$ 组成的整数 $n$。 每个数字都有固定的 $5 \times 5$ 图案，要求把整个数字横向打印出来。

解题思路

把每个数字的 $5$ 行图案存入二维字符串数组。

然后按行输出：

• 外层枚举行 $0$ 到 $4$；
• 内层枚举输入数字的每一位；
• 输出该数字在当前行的图案。

注意数字之间不额外加空格。

代码

#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 p[4][5] = {
    {
        ".....",
        ".***.",
        ".***.",
        ".***.",
        "....."
    },
    {
        "****.",
        "****.",
        "****.",
        "****.",
        "****."
    },
    {
        ".....",
        "****.",
        ".....",
        ".****",
        "....."
    },
    {
        ".....",
        "****.",
        ".....",
        "****.",
        "....."
    }
    };
string s;
inline void solve() {
    cin >> s;
    for (int row = 0; row < 5; row++) {
        for (char c : s) {
            int d = c - '0';
            cout << p[d][row];
        }
        cout << '\n';
    }
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

17. 2025

题目大意

给定整数 $x$，寻找最小正整数 $y$，满足：

$$(x \operatorname{and} y) + (x \operatorname{or} y) = 2025 $$

如果不存在，输出 $-1$。

解题思路

关键恒等式：

$$(x \& y) + (x | y) = x + y$$

所以原式等价于：

$$x + y = 2025$$

因此：

$$y = 2025 - x$$

题目保证 $0 \le x < 2025$，所以 $y$ 一定是正整数，直接输出即可。

代码

#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 x;
inline void solve() {
    cin >> x;
    printf("%d\n", (2025 - x));
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

18. 词频统计

题目大意

输入 $n$ 个单词，统计忽略大小写后出现次数最多的单词。 输出时使用小写形式。 题目保证出现次数最多的单词只有一个。

解题思路

对每个单词先转成小写。

然后用 $\text{map<string, int>}$ 统计出现次数。

最后找到次数最大的单词即可。

代码

#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;
map<string, int> cnt;
inline void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        for (char &c : s) {
            c = tolower(c);
        }
        cnt[s]++;
    }
    string Ans;
    int best = 0;
    for (auto it : cnt) {
        if (it.second > best) {
            best = it.second;
            Ans = it.first;
        }
    }
    cout << Ans << "\n";
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

19. 奇偶校验

题目大意

给定 $n$ 个非负整数。 统计这些数的二进制表示中一共有多少个 $\texttt{1}$。

如果 $\texttt{1}$ 的总数量是奇数，校验码为 $1$；否则校验码为 $0$。

输出：

1. $\texttt{1}$ 的总数量；
2. 校验码。

解题思路

对每个数不断除以 $2$，统计二进制中 $1$ 的数量。

也可以用：

__builtin_popcount(x)

这里使用手写函数，方便理解。

代码

#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 countOne(int x) {
    int cnt = 0;

    while (x > 0) {
        if (x % 2 == 1) cnt++;
        x /= 2;
    }

    return cnt;
}
int n;
inline void solve() {
    cin >> n;
    int Sum = 0;
    for (int i = 1, x; i <= n; i++) {
        cin >> x;
        Sum += countOne(x);
    }
    printf("%d %d\n", Sum, Sum % 2);
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

20. 分糖果

题目大意

有 $n$ 个小朋友排成一队。 第 $i$ 个小朋友至少需要 $a_i$ 颗糖果。 并且从第二个小朋友开始，每个人拿到的糖果数量必须比前一个人更多。

求最少一共需要多少颗糖果。

解题思路

从前往后贪心。

设当前小朋友实际拿到 $cur$ 颗糖。

第一个小朋友至少拿：

$$a_1$$

第 $i$ 个小朋友必须满足两个条件：

$$cur \ge a_i$$

并且：

$$cur > last$$

所以：

$$cur = \max(a_i, last+1)$$

累加所有 $cur$ 即可。

代码

#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;
    LL Ans = 0;
    LL last = 0;
    for (int i = 1; i <= n; i++) {
        LL a; cin >> a;
        LL cur = max(a, last + 1);
        Ans += cur;
        last = cur;
    }
    printf("%lld\n", Ans);
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

21. 数组清零

题目大意

给定一个非负整数数组。 每次操作：

1. 找到数组中的最大值，如果有多个，取下标最大的；
2. 找到数组中所有非零数中的最小值；
3. 将第一步找到的最大值减去这个最小非零值。

问需要多少次操作，才能让数组全部变成 $0$。

解题思路

数据范围很小：

$$n \le 100,\quad a_i \le 100$$

因此可以直接模拟。

每次循环：

• 找最大值位置；
• 找最小正数；
• 用最大值减去最小正数；
• 操作次数加 $1$。

当数组中最大值为 $0$ 时结束。

代码

#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;
}
int n, a[N];
inline void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int Ans = 0;
    while (true) {
        int mx = 0;
        int pos = -1;
        for (int i = 1; i <= n; i++) {
            if (a[i] >= mx) {
                mx = a[i];
                pos = i;
            }
        }
        if (mx == 0) break;
        int mn = inf;
        for (int i = 1; i <= n; i++) {
            if (a[i] > 0) {
                mn = min(mn, a[i]);
            }
        }
        a[pos] -= mn;
        Ans++;
    }
    printf("%d\n", Ans);
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

22. 日历制作

题目大意

输入月份 $m$，输出 $2025$ 年第 $m$ 月的日历。 第一行固定输出：

MON TUE WED THU FRI SAT SUN

后面输出这个月的日期，并让日期的个位与星期缩写最后一个字母对齐。

解题思路

需要知道：

1. 每个月有多少天；
2. 每个月 $1$ 号是星期几。

$2025$ 年 $1$ 月 $1$ 日是星期三。 用数组记录每个月天数，然后从 $1$ 月推到目标月份。

输出时，每个日期占 $3$ 个字符宽度，用 $\text{setw(3)}$ 右对齐， 或者可以用 \text{printf("%3d\n", 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 day[13] = {
    0,
    31, 28, 31, 30, 31, 30,
    31, 31, 30, 31, 30, 31
};
int m;
inline void solve() {
    cin >> m;
    int start = 3; 
    for (int i = 1; i < m; i++) {
        start = (start + day[i]) % 7;
        if (start == 0) start = 7;
    }
    printf("MON TUE WED THU FRI SAT SUN\n");
    int week = 1;
    for (int i = 1; i < start; i++) {
        if (i > 1) printf(" ");
        printf("   ");
        week++;
    }
    for (int d = 1; d <= day[m]; d++) {
        if (week > 1) printf(" ");
        printf("%3d", d);

        if (week == 7) {
            printf("\n");
            week = 1;
        } else {
            week++;
        }
    }
    if (week != 1) printf("\n");
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

23. 密码强度

题目大意

判断若干个密码是否安全。

安全密码需要满足：

1. 长度至少为 $8$；
2. 至少包含一个大写字母；
3. 至少包含一个数字。

满足输出 $\texttt{Y}$，否则输出 $\texttt{N}$。

解题思路

逐个字符扫描字符串。

记录：

• 是否出现大写字母；
• 是否出现数字；
• 长度是否至少为 $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;
}
string s;
inline void solve() {
    cin >> s;
    bool hasUp = false;
    bool hasNum = false;
    for (char c : s) {
        if ('A' <= c && c <= 'Z') hasUp = true;
        if ('0' <= c && c <= '9') hasNum = true;
    }
    if ((int)s.size() >= 8 && hasUp && hasNum) {
        printf("Y\n");
    } else {
        printf("N\n");
    }
}
int main() {
    int _ = 1; cin >> _;
    while (_--) solve();
    return 0;
}

24. 小杨的智慧购物

题目大意

商店中有 $N$ 件文具，分成 $M$ 种。 每件文具有：

• 种类编号 $K_i$；
• 价格 $P_i$。

小杨每种文具都要买一件，并且每种只买最便宜的那一件。 求买齐 $M$ 种文具的最小总花费。

解题思路

用数组 $\text{mn[k]}$ 记录第 $k$ 种文具的最低价格。

初始化为很大值。

读入每个商品后：

$$mn[K_i] = \min(mn[K_i], P_i)$$

最后把 $mn[1]$ 到 $mn[M]$ 加起来。

代码

#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;
}
int m, n, mn[N];
inline void solve() {
    cin >> m >> n;
    for (int i = 0; i <= m; i++) mn[i] = inf;
    for (int i = 1, k, p; i <= n; i++) {
        cin >> k >> p;
        mn[k] = min(mn[k], p);
    }
    LL Ans = 0;
    for (int i = 1; i <= m; i++) {
        Ans += mn[i];
    }
    printf("%lld\n", Ans);
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

25. 二进制回文串

题目大意

对于一个正整数，把它转换为不含前导零的二进制表示。 如果这个二进制串从左往右读和从右往左读一样，则称它为二进制回文数。

给定 $n$，统计 $1$ 到 $n$ 中有多少个二进制回文数。

解题思路

枚举 $1$ 到 $n$。

对每个数：

1. 转成二进制字符串；
2. 判断这个字符串是否回文；
3. 如果是，答案加 $1$。

$n \le 10^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;
}
string toBin(int x) {
    string s;
    while (x > 0) {
        s += char('0' + x % 2);
        x /= 2;
    }
    reverse(s.begin(), s.end());
    return s;
}
bool isP(string s) {
    int l = 0;
    int r = s.size() - 1;
    while (l < r) {
        if (s[l] != s[r]) return false;
        l++;
        r--;
    }
    return true;
}
int n;
inline void solve() {
    cin >> n;
    int Ans = 0;
    for (int i = 1; i <= n; i++) {
        if (isP(toBin(i))) {
            Ans++;
        }
    }
    printf("%d\n", Ans);
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

26. 凯撒密码

题目大意

给定三行字符串：

1. 已知明文；
2. 对应密文；
3. 待破解密文。

三者使用相同的凯撒密码偏移量。 要求根据前两行推出偏移量，再把第三行密文还原成明文。

解题思路

凯撒密码是把字母向后偏移固定距离。

用已知明文和密文的第一个字符求偏移量：

$$k = (cipher_0 - plain_0 + 26) \bmod 26$$

解密时，每个密文字符向前偏移 $k$ 位：

$$plain = (cipher - \texttt{A} - k + 26) \bmod 26 + \texttt{A} $$

代码

#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 a, b, c;
inline void solve() {
    cin >> a >> b >> c;
    int k = (b[0] - a[0] + 26) % 26;
    for (char &ch : c) {
        ch = char('A' + (ch - 'A' - k + 26) % 26);
    }
    cout << c << '\n';
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}