GESP 3级
B3848 [GESP样题 三级] 逛商场¶
提示1-按顺序，不能先排序
看全部数据范围，\(N\le100\)，\(0\le a_i\le10^5\)。
我先读完价格，再读预算。
题目规定遇到什么就考虑什么，不能为了多买而先按价格排序。
提示2-每买一件就扣一次钱
价格不超过剩余的钱，就扣钱并把购买数加一。
买不起就看下一件，不是停止购物；价格为 \(0\) 的商品也能买。
代码-满分
时间 \(O(N)\)，空间 \(O(N)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int price[N];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> price[i];
long long money;
cin >> money;
int ans = 0;
// 我按遇到的顺序决定是否购买，不改变商品顺序。
for (int i = 0; i < n; i++) {
if (price[i] <= money) {
money -= price[i];
ans++;
}
}
cout << ans;
return 0;
}
B3849 [GESP样题 三级] 进制转换¶
提示1-先想十进制怎样拆位
看全部数据范围，\(1\le N\le10^6\)，\(2\le R\le36\)。
我用除以 \(10\) 取余能得到个位，换成 \(R\) 进制，就用除以 \(R\) 取余。
提示2-先得到低位，最后再反转
每次余数是当前最低位，按得到的顺序保存后，需要反转才能输出。
我把所有数位字符排成一个字符串，余数就是下标，不必为每个字母写判断。
代码-满分
时间、空间均为 \(O(\log_R N+1)\)。题目保证 \(N>0\)。
B3842 [GESP202306 三级] 春游¶
提示1-重复报号不能当成多到一个人
看全部数据范围，\(2\le N,M\le1000\)。
我给每个编号开一个标记。
报过一次就标记到场，再报也不会改变这个标记。
提示2-检查每个编号，而不是比较人数
我从 \(0\) 到 \(N-1\) 检查，没标记的就是缺席者，顺序也自然是升序。
没有缺席者时，才输出 \(N\)；不能只用报号次数判断到没到齐。
代码-满分
时间 \(O(N+M)\)，空间 \(O(N)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
bool arrived[N];
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int x;
cin >> x;
arrived[x] = true;
}
bool first = true;
// 我按编号检查标记，重复报号不会让人数多算。
for (int i = 0; i < n; i++) {
if (arrived[i]) continue;
if (!first) cout << ' ';
cout << i;
first = false;
}
if (first) cout << n;
return 0;
}
B3843 [GESP202306 三级] 密码合规¶
提示1-先分出每个密码
看全部数据范围，输入总长度 \(L\le100\)。
我遇到逗号就检查刚读完的一段，逗号本身不是密码字符。
读完整行后，最后一段也要检查。
提示2-合法字符与字符种类分别检查
长度不在 \(6\) 到 \(12\) 之间，直接不合规。
出现允许范围外的字符，也不合规。
我用四个标记记录小写、大写、数字、特殊字符；前三个至少有两个为真，第四个必须为真。
代码-满分
时间、空间均为 \(O(L)\)。
#include <bits/stdc++.h>
using namespace std;
bool valid(const string &s) {
if (s.size() < 6 || s.size() > 12) return false;
bool lower = false, upper = false, number = false, special = false;
for (char c : s) {
if (c >= 'a' && c <= 'z') lower = true;
else if (c >= 'A' && c <= 'Z') upper = true;
else if (c >= '0' && c <= '9') number = true;
else if (c == '!' || c == '@' || c == '#' || c == '$') special = true;
else return false;
}
return lower + upper + number >= 2 && special;
}
int main() {
string s, password;
cin >> s;
bool first = true;
// 我补一个分隔符，让最后一段也走同一套检查流程。
s += ',';
for (char c : s) {
if (c != ',') password += c;
else {
if (valid(password)) {
if (!first) cout << '\n';
cout << password;
first = false;
}
password.clear();
}
}
return 0;
}
B3867 [GESP202309 三级] 小杨的储蓄¶
提示1-下标记罐子，数值记钱
看全部数据范围，\(N,D\le1000\)，罐子编号从 \(0\) 开始。
我让数组下标对应编号，数组初始都为 \(0\)。
提示2-存入的是天数，不是编号
第 \(i\) 天读到编号 \(x\)，就给 money[x] 加 \(i\)。
最多把所有钱存入一个罐子，总额为 \(\frac{D(D+1)}{2}\le500500\)，int 足够。
代码-满分
时间 \(O(N+D)\)，空间 \(O(N)\)。
B3868 [GESP202309 三级] 进制判断¶
提示1-只判断数位是否合法
看全部数据范围，\(N\le1000\)，串长 \(L\le10\)，只含数字和大写字母，允许前导零。
我不需要算出这个数，只要检查每个数位是否小于进制。
提示2-最大的数位决定能用哪些进制
我把数字和字母换成数位值，找到最大值 \(d\)。
对于进制 \(R\)，只要 \(d<R\) 就合法。
例如包含字母G时，连十六进制也不合法。
代码-满分
时间 \(O(NL)\)，额外空间 \(O(L)\)。
#include <bits/stdc++.h>
using namespace std;
int base[] = {2, 8, 10, 16};
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
string s;
cin >> s;
int largest = 0;
// 我只找最大数位，不把整串转换成整数。
for (char c : s) {
int x = c <= '9' ? c - '0' : c - 'A' + 10;
largest = max(largest, x);
}
if (i) cout << '\n';
for (int j = 0; j < 4; j++) {
if (j) cout << ' ';
cout << (largest < base[j] ? 1 : 0);
}
}
return 0;
}
B3925 [GESP202312 三级] 小猫分鱼¶
提示1-从最后一只拿多少条想起
看全部数据范围，\(1\le N\le9\)，\(0\le i<N\)。
我从初始鱼数逐个试，会有很多候选。
换个方向，先假设最后一只拿 \(p\) 条，那么它分之前一定有 \(Np+i\) 条。
提示2-怎样倒推前一只分之前
设当前剩余鱼数为 \(x\)。
前一只拿走一份后留下 \(N-1\) 份，所以 \(x\) 必须能被 \(N-1\) 整除。
能整除时，前一只分之前有 \(\frac{x}{N-1}N+i\) 条；不能整除，这个 \(p\) 就不行。
我从 \(p=1\) 开始试，连续倒推 \(N-1\) 次。
倒推结果随 \(p\) 增大而增大，第一个成功的就是最少初始鱼数。
提示3-每只都要吃到鱼
\(p\) 从 \(1\) 开始，保证最后一只拿到鱼；倒推时前面的份数只会更大。
只有一只猫时，直接一条鱼就够了，不能除以 \(N-1=0\)。
中间鱼数用 long long。
代码-满分
若试到的最后份数为 \(P\)，时间 \(O(NP)\)，额外空间 \(O(1)\)。\(N\ge2\) 时 \(P\le(N-1)^{N-1}\)，最大约 \(1680\) 万；多数候选在第一次整除检查就失败。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, extra;
cin >> n >> extra;
if (n == 1) {
cout << 1;
return 0;
}
// 我枚举最后一只的份数，从小到大倒推，第一次成功就停。
for (long long part = 1; ; part++) {
long long fish = n * part + extra;
bool ok = true;
for (int cat = 1; cat < n; cat++) {
if (fish % (n - 1) != 0) {
ok = false;
break;
}
fish = fish / (n - 1) * n + extra;
}
if (ok) {
cout << fish;
break;
}
}
return 0;
}
B3926 [GESP202312 三级] 单位转换¶
提示1-先统一到最小单位
看全部数据范围，\(N\le1000\)，\(0\le x\le1000\)，只做同类的大单位到小单位转换。
我把km、m、mm对应为 \(10^6,10^3,1\)，kg、g、mg也一样。
答案就是数量乘以两个单位的倍率之比。
提示2-用两个map保存单位倍率
我用mpm保存长度单位，用mpg保存重量单位。单位名作键，对应的倍率作值。
输入式子的等号和问号各读进一次字符变量c，它们只是占位，不参与计算。
先判断原单位是否在mpm中，再用对应的表计算，按题目格式输出等式。
代码-满分
设一行长度上界为 \(L\)，时间 \(O(NL)\)。两张单位表都只有三个条目，额外空间 \(O(1)\)。
#include <bits/stdc++.h>
using namespace std;
map<string, int> mpm, mpg;
int main() {
int n;
cin >> n;
mpm["mm"] = 1, mpm["m"] = 1000, mpm["km"] = 1000000;
mpg["mg"] = 1, mpg["g"] = 1000, mpg["kg"] = 1000000;
while (n--) {
int x;
string xx, yy;
char c;
cin >> x >> xx >> c >> c >> yy;
// 我先判断是哪类单位，再查对应的倍率表。
if (mpm.count(xx) != 0) {
cout << x << ' ' << xx << " = " << x * mpm[xx] / mpm[yy] << ' ' << yy << endl;
} else {
cout << x << ' ' << xx << " = " << x * mpg[xx] / mpg[yy] << ' ' << yy << endl;
}
}
return 0;
}
B3956 [GESP202403 三级] 字母求和¶
提示1-大小写的规则不同
看全部数据范围，\(n\le10^5\)，字符串只含英文字母。
我先拿a和A对比：a贡献 \(1\)，A贡献 \(-65\)，不是 \(-1\)。
提示2-逐个字符累加
小写字符减去字符a再加 \(1\)；大写字符直接取字符编码的相反数。
答案可能为负。
最小不小于 \(-90n\)，int 足够。
代码-满分
时间、空间均为 \(O(n)\)。
B3957 [GESP202403 三级] 完全平方数¶
提示1-先看有多少对需要检查
看全部数据范围，\(n\le1000\)，\(0\le a_i\le10^5\)。
最多不到五十万对，我直接枚举 \(i<j\)，不会重复，也不会让一个元素和自己配对。
提示2-把所有平方数预先标好
两数和不超过 \(2\times10^5\)。
我先标记 \(0^2,1^2,2^2,\ldots\)，每对只需一次查表。
从 \(0\) 开始标记，才能正确处理两个零相加。
相同数值在不同下标出现，也分别计数。
代码-满分
时间 \(O(n^2+\sqrt V)\)，空间 \(O(n+V)\)，其中 \(V=2\times10^5\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
const int V = 200000;
int a[N];
bool square[V + 1];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
// 我连零的平方也标记，避免漏掉两个零组成的数对。
for (int x = 0; x * x <= V; x++) square[x * x] = true;
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (square[a[i] + a[j]]) ans++;
}
}
cout << ans;
return 0;
}
B4003 [GESP202406 三级] 移位¶
提示1-超过一圈就重新从A开始
看全部数据范围，\(1\le n\le100\)。
我给A到Z编号 \(0\) 到 \(25\)。
位置 \(i\) 移动后，就是 \((i+n)\bmod26\)。
提示2-输出的是替换后的字母表
我按原来的A到Z逐个算新字母，不是只输出一个字母。
移位量是 \(26\) 的倍数时，结果应和原字母表一样，可以用它检查取模是否写对。
代码-满分
时间 \(O(26)\)，额外空间 \(O(1)\)。
B4004 [GESP202406 三级] 寻找倍数¶
提示1-不用把每个数都试一遍
看全部数据范围，\(t\le10\)，\(n\le10^5\)，\(1\le a_i\le10^9\)。
我先想符合要求的数能多小：它必须是最大元素的倍数，又来自数组，所以只能是数组最大值。
提示2-只检查最大值
找到最大值 \(x\)，逐个检查 \(x\bmod a_i\) 是否为 \(0\)。
全都整除才输出Yes。
所有元素为正，不会除以零，也不需要求可能溢出的最小公倍数。
代码-满分
时间 \(O(tn)\)，空间 \(O(n)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int a[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
for (int test = 0; test < t; test++) {
int n, largest = 0;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
largest = max(largest, a[i]);
}
bool ok = true;
// 我只检查唯一可能的候选：序列里的最大值。
for (int i = 0; i < n; i++) {
if (largest % a[i] != 0) ok = false;
}
if (test) cout << '\n';
cout << (ok ? "Yes" : "No");
}
return 0;
}
B4038 [GESP202409 三级] 平衡序列¶
提示1-先求总和，再移动分界点
看全部数据范围，\(t\le100\)，\(n,a_i\le10^4\)。
我先求总和 \(S\)。
左边已经累加到 \(L\) 时，右边就是 \(S-L\)，不必再求一遍。
提示2-不能切出空的一边
只尝试前 \(1\) 到 \(n-1\) 个元素作为左边。
满足 \(L=S-L\) 就可以。
只有一个元素时没有分界点，答案为No。
每组的总和、左和、判断结果都重新初始化。
代码-满分
时间 \(O(tn)\)，空间 \(O(n)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 10005;
int a[N];
int main() {
int t;
cin >> t;
for (int test = 0; test < t; test++) {
int n;
cin >> n;
long long total = 0;
for (int i = 0; i < n; i++) {
cin >> a[i];
total += a[i];
}
long long left = 0;
bool ok = false;
// 我只在元素之间切，不能把右边切成空序列。
for (int i = 0; i + 1 < n; i++) {
left += a[i];
if (left == total - left) ok = true;
}
if (test) cout << '\n';
cout << (ok ? "Yes" : "No");
}
return 0;
}
B4039 [GESP202409 三级] 回文拼接¶
提示1-两段都有长度要求
看全部数据范围，字符串数 \(n\le10\)，每个串长度 \(L\le100\)。
我枚举左段长度 \(k\)，它至少为 \(2\)，右段也要至少为 \(2\)，所以 \(2\le k\le L-2\)。
提示2-回文从两头往中间检查
我用两个下标比较首尾，相等就向中间靠近，遇到不同就失败。
每个切点分别检查左右两段，两段都回文才行。
原串本身是回文，并不代表一定能按要求切开。
代码-满分
时间 \(O(nL^2)\)，额外空间 \(O(L)\)。
#include <bits/stdc++.h>
using namespace std;
bool palindrome(const string &s, int left, int right) {
while (left < right) {
if (s[left] != s[right]) return false;
left++;
right--;
}
return true;
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
string s;
cin >> s;
int length = s.size();
bool ok = false;
// 我给左右各留至少两个字符，再试中间的分界点。
for (int k = 2; k <= length - 2; k++) {
if (palindrome(s, 0, k - 1) && palindrome(s, k, length - 1)) {
ok = true;
break;
}
}
if (i) cout << '\n';
cout << (ok ? "Yes" : "No");
}
return 0;
}
B4066 [GESP202412 三级] 数字替换¶
提示1-原序列的最大值和最小值先找好
看全部数据范围，\(n\le10^5\)，\(|k|,|a_i|\le10^5\)。
我先读完整个数组求最大、最小值，再统一替换，不能读一个就立刻替换。
提示2-等于k时不动
大于、小于、等于分开考虑。
数组可能全为负数，最大值不能随便初始化为 \(0\)；我用第一个元素初始化最大、最小值。
代码-满分
时间、空间均为 \(O(n)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int a[N];
int main() {
int n, k;
cin >> n >> k;
for (int i = 0; i < n; i++) cin >> a[i];
int largest = a[0], smallest = a[0];
for (int i = 1; i < n; i++) {
largest = max(largest, a[i]);
smallest = min(smallest, a[i]);
}
// 我先求原序列的极值，等于阈值的元素不改变。
for (int i = 0; i < n; i++) {
int x = a[i];
if (x > k) x = largest;
else if (x < k) x = smallest;
if (i) cout << ' ';
cout << x;
}
return 0;
}
B4067 [GESP202412 三级] 打印数字¶
提示1-把固定图案当成数据
看全部数据范围，\(0\le n\le10^6\)，数位只有0到3。
我把四种数字各自的五行存在二维字符串数组里。
按字符读入数字，\(0\) 也能正常打印。
提示2-先输出整幅图的第一行
不能先打印完一个数字再打印下一个，那样会竖着排。
我先枚举图案行号，再枚举输入数的每一位，输出这一位对应的当前行。
五行都这样拼接。
代码-满分
设数位数为 \(L\)，输出 \(25L\) 个图案字符，时间、空间均为 \(O(L)\)。
#include <bits/stdc++.h>
using namespace std;
string pattern[4][5] = {
{".....", ".***.", ".***.", ".***.", "....."},
{"****.", "****.", "****.", "****.", "****."},
{".....", "****.", ".....", ".****", "....."},
{".....", "****.", ".....", "****.", "....."}
};
int main() {
string s;
cin >> s;
// 我先按图案行号输出，再把每个数字的这一行接在后面。
for (int row = 0; row < 5; row++) {
if (row) cout << '\n';
for (char c : s) cout << pattern[c - '0'][row];
}
return 0;
}
B4261 [GESP202503 三级] 2025¶
提示1-答案范围小，先枚举
看全部数据范围，\(0\le x<2025\)。
按位或的结果不会小于 \(y\)，按位与的结果非负。
因此能满足等式的 \(y\) 不会超过 \(2025\)。
我从 \(y=1\) 开始试，找到第一个就停，不需要猜一个很大的上界。
提示2-两个位运算都要加括号
C++中按位与用 &，按位或用 |。
我把两个结果分别放在括号里，再相加比较。
也可以观察每一位：按位与和按位或的贡献之和等于两个原数的贡献，所以原式等于 \(x+y\)，答案其实是 \(2025-x\)。
先用枚举验证这个规律，再理解它。
代码-满分
时间 \(O(2025)\)，额外空间 \(O(1)\)，可覆盖全部测试点。
B4262 [GESP202503 三级] 词频统计¶
提示1-先把大小写统一
看全部数据范围，\(n\le100\)，单词长度 \(L\le30\)。
我先把大写字母转成小写，再比较单词。
否则Apple和apple会被误当成两个词。
提示2-一百个词，直接两层循环
我枚举一个单词，再扫描所有单词，数有多少个和它相同。
最多一万次字符串比较，直接写就够了，不一定要用 map。
只在频数更大时更新答案；题目保证最多的词唯一。
代码-满分
时间 \(O(n^2L)\)，空间 \(O(nL)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
string word[N];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> word[i];
for (char &c : word[i]) {
if (c >= 'A' && c <= 'Z') c = c - 'A' + 'a';
}
}
int best = 0, most = 0;
// 单词不多，我先统一大小写，再直接数每个词出现了几次。
for (int i = 0; i < n; i++) {
int count = 0;
for (int j = 0; j < n; j++) {
if (word[i] == word[j]) count++;
}
if (count > most) {
most = count;
best = i;
}
}
cout << word[best];
return 0;
}
B4358 [GESP202506 三级] 奇偶校验¶
提示1-取余得到最低二进制位
看全部数据范围，\(n\le100\)，\(0\le c_i\le255\)。
我用除以 \(2\) 取余查看最低位，再整除 \(2\)，继续检查剩下的位。
提示2-统计的是各个数的二进制位
每个数最多 \(8\) 位，总共最多 \(800\) 个1。
不能先把所有数相加，再数总和的1，那会受到进位影响。
输入 \(0\) 时贡献为 \(0\)，最后输出总数和总数模 \(2\)。
代码-满分
时间 \(O(8n)\)，额外空间 \(O(1)\)。
B4359 [GESP202506 三级] 分糖果¶
提示1-当前只要满足两个下界
看全部数据范围，\(n\le1000\)，\(1\le a_i\le10^9\)。
我先给第一个人恰好需要的数量。
后面的人既要达到自己的要求，也至少比前一个多一颗。
提示2-少给当前，也给后面留余地
当前最少数量是 \(\max(a_i,b_{i-1}+1)\)，其中 \(b_{i-1}\) 是前一人实际拿到的数量。
多给当前不会降低后面的需求，所以逐个取这个最小值就能得到最小总和。
总和可能超过 int，用 long long。
代码-满分
时间 \(O(n)\)，额外空间 \(O(1)\)。
B4413 [GESP202509 三级] 数组清零¶
提示1-数据小，可以直接模拟
看全部数据范围，\(n\le100\)，\(0\le a_i\le100\)。
我每次按题意找最大值和最小非零值，再做一次减法。
每次总和至少减少 \(1\)，所以最多 \(10^4\) 次操作。
提示2-两个容易漏掉的条件
最大值有多个，要选下标最大的。
我从左往右找，遇到相等也更新下标。
最小值只看非零元素，不能拿 \(0\) 去减，否则永远不会结束。
全为零时直接停止，答案是 \(0\)。
代码-满分
设初始总和为 \(S\le10^4\)，时间 \(O(n(S+1))\)，空间 \(O(n)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
const int INF = 101;
int a[N];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
int ans = 0;
// 我按题意逐次操作，并用总和一定减少来保证循环结束。
while (true) {
int place = -1, smallest = INF;
for (int i = 0; i < n; i++) {
if (a[i] == 0) continue;
smallest = min(smallest, a[i]);
if (place == -1 || a[i] >= a[place]) place = i;
}
if (place == -1) break;
a[place] -= smallest;
ans++;
}
cout << ans;
return 0;
}
B4414 [GESP202509 三级] 日历制作¶
提示1-先确定这个月一号是星期几
看全部数据范围，\(1\le m\le12\)，年份固定为2025。
我以星期一为 \(0\)，星期日为 \(6\)。
2025年1月1日是星期三，编号为 \(2\)；加上之前各月天数，再模 \(7\)，就得到当月一号的列号。
2025不是闰年，二月有 \(28\) 天。
提示2-把空位和日期都当成格子
一号之前先输出空格子，再依次填日期；每填七格就换行。
每列宽 \(3\) 个字符，列间再留一个空格。
个位就能与MON、TUE等缩写的最后一个字符对齐。
我用 setw(3) 右对齐日期，它只控制紧接着的一次输出，所以每个日期都要设置。
代码-满分
时间 \(O(m+d)\)，额外空间 \(O(1)\)，其中 \(d\le31\) 为当月天数。
#include <bits/stdc++.h>
using namespace std;
int days[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int main() {
int month;
cin >> month;
int start = 2;
for (int i = 1; i < month; i++) start = (start + days[i]) % 7;
cout << "MON TUE WED THU FRI SAT SUN";
// 我把一号前的空位也算作格子，每七格开始下一行。
for (int cell = 0; cell < start + days[month]; cell++) {
if (cell % 7 == 0) cout << '\n';
else cout << ' ';
if (cell < start) cout << " ";
else cout << setw(3) << cell - start + 1; // setw让日期在三格内右对齐。
}
return 0;
}
B4449 [GESP202512 三级] 密码强度¶
提示1-把三个条件分别记清
看全部数据范围，\(T\le100\)，长度 \(L\le100\)，字符只含字母和数字。
我分别检查长度、大写字母、数字，三个条件必须同时满足。
提示2-出现过就记为真
扫描时遇到大写字母就标记，遇到数字也标记，不需要统计每类出现几次。
每组密码都重新设置两个标记，不能沿用上一组的结果。
代码-满分
时间 \(O(TL)\)，额外空间 \(O(L)\)。
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
for (int i = 0; i < t; i++) {
string s;
cin >> s;
bool upper = false, number = false;
// 我只记录是否出现，每组密码都重新初始化。
for (char c : s) {
if (c >= 'A' && c <= 'Z') upper = true;
if (c >= '0' && c <= '9') number = true;
}
bool ok = s.size() >= 8 && upper && number;
if (i) cout << '\n';
cout << (ok ? 'Y' : 'N');
}
return 0;
}
B4450 [GESP202512 三级] 小杨的智慧购物¶
提示1-每种文具单独比较
看全部数据范围，\(1\le M\le N\le10^5\)，价格不超过 \(1000\)。
我给每种文具记一个当前最低价。
读到同类新商品，只在它更便宜时替换。
提示2-初始值要比所有价格大
最低价不能初始化为 \(0\)，否则后面正价格永远无法更新。
我初始化为 \(1001\)，读完后再把每类最低价相加。
总价最多 \(10^8\)，int 足够；同价多件仍只买一件。
代码-满分
时间 \(O(N+M)\)，空间 \(O(M)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
const int INF = 1001;
int cheapest[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int m, n;
cin >> m >> n;
for (int i = 1; i <= m; i++) cheapest[i] = INF;
// 我只保留每类最低价，不保存所有同类商品。
for (int i = 0; i < n; i++) {
int kind, price;
cin >> kind >> price;
cheapest[kind] = min(cheapest[kind], price);
}
int ans = 0;
for (int i = 1; i <= m; i++) ans += cheapest[i];
cout << ans;
return 0;
}
B4499 [GESP202603 三级] 二进制回文串¶
提示1-十万范围，逐个检查即可
看全部数据范围，\(1\le n\le10^5\)。
我枚举每个整数，用除以 \(2\) 取余得到它的二进制字符，再检查是否回文。
最多只有 \(17\) 位。
提示2-倒序得到二进制，也不影响回文判断
取余得到的是从低位到高位的顺序，但一个串是否回文，反转后不会改变。
因此不必先反转，我直接用两端下标比较。
不要补前导零，也不要把十进制回文当成二进制回文。
代码-满分
时间 \(O(n\log n)\)，额外空间 \(O(\log n)\)。
#include <bits/stdc++.h>
using namespace std;
bool palindrome(int x) {
string s;
while (x > 0) {
s += char('0' + x % 2);
x /= 2;
}
int l = 0, r = (int)s.size() - 1;
while (l < r) {
if (s[l] != s[r]) return false;
l++;
r--;
}
return true;
}
int main() {
int n;
cin >> n;
int ans = 0;
// 我逐个拆出二进制，倒序串和正序串有相同的回文性质。
for (int x = 1; x <= n; x++) {
if (palindrome(x)) ans++;
}
cout << ans;
return 0;
}
B4500 [GESP202603 三级] 凯撒密码¶
提示1-先从一对字母找偏移量
看全部数据范围，每行长度不超过 \(1000\)，所有字符为大写字母。
我用已知密文的首字母减明文的首字母，得到偏移量，再加 \(26\) 取模，处理绕回A的情况。
提示2-解密要减去偏移量
加密向后移，解密就向前移。
设字母编号为 \(p\)，解密后是 \((p-k+26)\bmod26\)。
先加 \(26\) 再取模，避免C++负数取余的结果仍为负。
偏移量为 \(0\) 时，原样输出。
代码-满分
设三行总长度为 \(L\)，时间、空间均为 \(O(L)\)。
B4555 [GESP202606 三级] 加密¶
提示1-密码本下标就是原数字
看全部数据范围，数字数量 \(n\le20000\)，数字和替换值均在 \(0\) 到 \(9\)，替换表无重复。
我让 code[0] 保存0变成什么，依次存到 code[9]。
直接用原数字当下标即可。
提示2-替换一次，不追着替换下去
若0变成9、9变成8，原来的0只变成9，不能再变成8。
替换表在序列之后输入，所以先存原序列，读完表再输出。
代码-满分
时间 \(O(n+10)\)，空间 \(O(n)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 20005;
int a[N], code[10];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < 10; i++) cin >> code[i];
// 我始终用原数字查一次表，不再对替换结果继续加密。
for (int i = 0; i < n; i++) {
if (i) cout << ' ';
cout << code[a[i]];
}
return 0;
}
B4556 [GESP202606 三级] 字符转换¶
提示1-三种字符分别处理
看全部数据范围，长度 \(n\le1000\)，只含英文字母和数字。
我先判断当前字符属于哪类。
大小写之间用字符a与字符A的差转换，数字直接输出星号。
提示2-只处理原字符所属的一类
我用 if、else if、else，让每个字符只进入一个分支。
不能先把大写改成小写，又用另一个独立判断把它改回来。
输出字符之间不加空格。
代码-满分
时间、空间均为 \(O(n)\)。
B4577 [GESP202609 三级] 公共二进制位¶
提示1-先想怎样保留共同的1
看全部数据范围，\(2\le n\le20000\)，\(0\le a_i\le10^9\)。
按位与只有两边都为1时才为1。
我把所有数依次按位与，留下的就只有公共的1。
提示2-初始值不能设成零
我用第一个输入数初始化结果，再和后面的数做与。
若从 \(0\) 开始，与任何数都会得到 \(0\)。
最后除以 \(2\) 拆位，数结果里有几个1。
只要某个输入为 \(0\)，答案自然就是 \(0\)。
代码-满分
时间 \(O(n+\log(A+1))\)，额外空间 \(O(1)\)，其中 \(A\le10^9\)。
B4578 [GESP202609 三级] 分割字符串¶
提示1-整行读入，不能用cin直接读字符串
看全部数据范围，长度 \(L\le1000\)，只含字母、数字和空格，不以空格结尾。
我用 getline 读整行。
空格本身决定怎么分割，不能跳过它，也不能把所有空格都当分隔符。
提示2-记录这一次需要几个连续空格
开始需要 \(1\) 个，分割成功后需要量加一。
我从左到右数连续空格，遇到非空格就把计数清零。
当连续数达到当前需要量，就在这里切开；只消耗这几个空格，多出的空格仍在右侧，继续参与下一轮。
提示3-空段也必须输出
例如AbCd后有三个空格：先消耗一个，输出AbCd；再消耗两个，输出空行；最后输出999。
我记住当前段的开始下标，切开时输出它到分隔符之前的内容。
扫描结束后，再输出最后一段，不要删它开头留下的空格。
代码-满分
时间、空间均为 \(O(L)\)。每个字符只扫描一次，各段的输出总长度不超过 \(L\)。
#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
getline(cin, s);
int start = 0, need = 1, count = 0;
// 我只消耗当前需要的空格，多出的空格留给下一次分割。
for (int i = 0; i < (int)s.size(); i++) {
if (s[i] == ' ') count++;
else count = 0;
if (count == need) {
int end = i - need + 1;
cout << s.substr(start, end - start) << '\n';
start = i + 1;
need++;
count = 0;
}
}
cout << s.substr(start);
return 0;
}