GESP 5级
B3941 [GESP样题 五级] 小杨的锻炼¶
提示1-先把周期翻译成倍数
20分做法，\(n=2\)。
50分做法，\(n=4\)。
看全部数据范围，\(n\le 10\)，\(a_{i}\le 50\)。
我先看两个人：相遇的天数必须同时是两个周期的倍数，最早的一天就是最小公倍数。
提示2-一次合并一个周期
我先求前两人的最小公倍数，再和第三人的周期合并，依次做下去。
我用这个公式合并两个周期：
先除后乘，结果用 long long，不能用 int。
代码-满分-逐次求最小公倍数
时间 \(O(n\log A)\)，额外空间 \(O(1)\)，\(A\le 50\)。所有人数范围都使用同一算法。
#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) {
while (b != 0) {
long long r = a % b;
a = b;
b = r;
}
return a;
}
int main() {
int n;
cin >> n;
long long ans = 1;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
// 我把已有的共同周期和新周期合并，先除再乘。
ans = ans / gcd(ans, x) * x;
}
cout << ans;
return 0;
}
B3951 [GESP样题 五级] 小杨的队列¶
提示1-交换次数不等于人数
50分做法，身高互不相同。
看全部数据范围，\(m\le n\le 2000\)，身高可达 int 上限。
我先试队伍 2、2、4，新来身高 1：和一个 2 交换，再和 4 交换，只用两次，不是三次。
提示2-每种更高的身高只需一次
原队伍已经排好，我让新来的同学和每一组更高身高的第一人依次交换，就能排好。
每个不同身高的更高组都要有人换位，至少一次。
因此我只统计已经入队、且更高的不同身高数量。
代码-满分-用集合记录身高
时间 \(O(m^{2}+m\log m)\)，空间 \(O(n)\)。set 自动合并相同身高，不需要实际模拟队伍。
#include <bits/stdc++.h>
using namespace std;
const int N = 2005;
int height[N];
int main() {
int n, m;
cin >> n;
for (int i = 0; i < n; i++) cin >> height[i];
cin >> m;
set<int> appeared;
for (int t = 0; t < m; t++) {
int id, ans = 0;
cin >> id;
// 我数的是更高的身高种类，不是更高的人数。
for (int h : appeared) {
if (h > height[id]) ans++;
}
appeared.insert(height[id]);
if (t > 0) cout << '\n';
cout << ans;
}
return 0;
}
B3871 [GESP202309 五级] 因数分解¶
提示1-不用试到 n
看全部数据范围，\(n\le 10^{12}\)。
我从 2 开始试除，每找到一个因数就除干净。
较小因数已经去掉，后来能整除的因数自然是质数。
提示2-剩下的数别漏掉
试到 \(p^2\) 大于剩余数就可以停，此时若还剩一个大于 1 的数，它就是最后一个质因数。
我用 \(p\le \frac{n}{p}\) 避免平方溢出。
输出时，只有前面输出过因子才加乘号。
代码-满分-试除分解
时间 \(O(\sqrt{n})\)，额外空间 \(O(1)\)。\(n\) 和试除因子都用 long long。
#include <bits/stdc++.h>
using namespace std;
int main() {
long long n;
cin >> n;
bool first = true;
for (long long p = 2; p <= n / p; p++) {
if (n % p != 0) continue;
int count = 0;
while (n % p == 0) {
n /= p;
count++;
}
// 我先处理分隔符，第一次输出前不加乘号。
if (!first) cout << " * ";
cout << p;
if (count > 1) cout << '^' << count;
first = false;
}
if (n > 1) {
if (!first) cout << " * ";
cout << n;
}
return 0;
}
B3872 [GESP202309 五级] 巧夺大奖¶
提示1-奖励高的不一定先做
看全部数据范围，\(n\le 500\)，期限\(\le n\)，奖励\(\le 1000\)。
我先按奖励从大到小考虑，但不能一律塞到最早的时间：这样可能挡住期限更紧的游戏。
提示2-给后面的游戏留余地
当前游戏值得选，我就把它放到期限内最晚的空位，把前面的空位留给期限更紧的游戏。
没有空位就跳过。
数据只有 500，直接向前找空位足够，不必再用复杂结构。
代码-满分-按奖励安排最晚空位
时间 \(O(n^{2})\)，空间 \(O(n)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 505;
struct Game {
int deadline, reward;
};
Game a[N];
bool used[N];
bool cmp(Game x, Game y) {
return x.reward > y.reward;
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i].deadline;
for (int i = 1; i <= n; i++) cin >> a[i].reward;
sort(a + 1, a + n + 1, cmp);
int ans = 0;
for (int i = 1; i <= n; i++) {
// 我尽量晚做当前游戏，把早的空位留给期限更紧的游戏。
for (int time = a[i].deadline; time >= 1; time--) {
if (used[time]) continue;
used[time] = true;
ans += a[i].reward;
break;
}
}
cout << ans;
return 0;
}
B3929 [GESP202312 五级] 小杨的幸运数¶
提示1-先标记，不逐次猜
30分做法，\(a,x,n\le 100\)。
60分做法，\(a,x\le 10^{6}\)。
看全部数据范围，\(n\le 2\times 10^{5}\)，\(x\le 1000001\)。
我发现幸运数是平方数的倍数，就像筛法一样，枚举满足条件的平方数，标记它的所有倍数。
提示2-查询上界之外也要准备
非幸运数的答案可能超过查询上界。
我找到 \(1001^2=1002001\)，它大于所有查询数，且一定是超级幸运数。
标记到这里，再从右向左记录最近的幸运数，每次查询就能直接回答。
代码-满分-筛倍数与倒序预处理
设预处理上界 \(U=1002001\)，时间 \(O(U+n)\)，空间 \(O(U)\)。平方数倍数标记总量由 \(U\sum_{i=1}^{\lfloor\sqrt{U}\rfloor}\frac{1}{i^{2}}=O(U)\) 控制。
#include <bits/stdc++.h>
using namespace std;
const int U = 1002001, N = U + 5;
bool lucky[N];
int next_lucky[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int a, n;
cin >> a >> n;
for (int i = 1; i <= U / i; i++) {
int square = i * i;
if (square < a) continue;
for (int j = square; j <= U; j += square) lucky[j] = true;
}
// 我把上界外的答案也准备好，再从右往左找最近的幸运数。
int nearest = U;
for (int i = U; i >= 1; i--) {
if (lucky[i]) nearest = i;
next_lucky[i] = nearest;
}
for (int t = 0; t < n; t++) {
int x;
cin >> x;
if (t > 0) cout << '\n';
if (lucky[x]) cout << "lucky";
else cout << next_lucky[x];
}
return 0;
}
B3930 [GESP202312 五级] 烹饪问题¶
提示1-先写两层循环
40分做法，\(n\le 1000\)。
看全部数据范围，\(n\le 10^{6}\)，\(0\le a_{i}\le 2147483647\)。
小范围我直接枚举一对食材。
百万个数不能逐对比较，但每个数只有 31 个有效二进制位。
提示2-高位能取 1 就取 1
我从高位往低位试着把答案这一位设成 1，检查至少两个数是否同时包含答案里所有的 1。
若能找到，就保留这一位。
否则放弃。
一个高位比所有低位加起来还大，所以不能为了低位牺牲它。
代码-40分-枚举食材对
时间 \(O(n^{2})\)，空间 \(O(n)\)，覆盖 \(n\le 1000\) 的测试点。
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int a[N];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
int ans = 0;
// 我先比较每一对食材，确认按位与的含义。
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) ans = max(ans, a[i] & a[j]);
}
cout << ans;
return 0;
}
代码-满分-按位贪心
时间 \(O(31n)\)，空间 \(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 = 1; i <= n; i++) cin >> a[i];
int ans = 0;
for (int bit = 30; bit >= 0; bit--) {
int candidate = ans | (1 << bit), count = 0;
// 我检查的是所有已选高位，不能只检查新试的这一位。
for (int i = 1; i <= n; i++) {
if ((a[i] & candidate) == candidate) {
count++;
if (count == 2) break;
}
}
if (count >= 2) ans = candidate;
}
cout << ans;
return 0;
}
B3968 [GESP202403 五级] 成绩排序¶
提示1-把规则依次写清
30分做法，\(n\le 100\)且总分不同。
看全部数据范围，\(n\le 10^{4}\)，各科\(\le 150\)。
我依次比较总分、语数总分、语数最高分，前一项分出高低后就不看后面的项。
提示2-名次相同，不等于下一名紧接着
排序后，三项都相同就沿用前一个人的名次。
否则名次就是当前下标加 1。
我还要记住原编号，把算好的名次放回原位置，不能按排名输出编号。
代码-满分-排序并还原顺序
时间 \(O(n\log n)\)，空间 \(O(n)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 10005;
struct Student {
int total, two, best, id;
};
Student a[N];
int ranking[N];
bool cmp(Student x, Student y) {
if (x.total != y.total) return x.total > y.total;
if (x.two != y.two) return x.two > y.two;
return x.best > y.best;
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int c, m, e;
cin >> c >> m >> e;
a[i] = {c + m + e, c + m, max(c, m), i};
}
sort(a, a + n, cmp);
int rank = 1;
for (int i = 0; i < n; i++) {
// 我在出现新的成绩组时按实际位置定名次，保留并列后的空位。
if (i == 0 || cmp(a[i - 1], a[i])) rank = i + 1;
ranking[a[i].id] = rank;
}
for (int i = 0; i < n; i++) {
if (i > 0) cout << '\n';
cout << ranking[i];
}
return 0;
}
B3969 [GESP202403 五级] B-smooth 数¶
提示1-先逐个分解
30分做法，\(n\le 1000\)。
另外30分做法，\(B\ge \sqrt{n}\)。
看全部数据范围，\(n,B\le 10^{6}\)。
我先逐个分解质因数，得到最大质因数。
1 没有质因数，题目把它算在答案里。
提示2-用筛法一起求
百万个数逐个分解会重复试除，我改用筛法：每个质数 \(p\) 更新它的所有倍数。
质数从小到大处理，最后留下的就是最大质因数，再统计不超过 \(B\) 的数。
代码-30分-逐个试除
时间 \(O(n\sqrt{n})\)，额外空间 \(O(1)\)，覆盖 \(n\le 1000\) 的子任务。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, b;
cin >> n >> b;
int ans = 0;
for (int i = 1; i <= n; i++) {
int x = i, largest = 1;
for (int p = 2; p <= x / p; p++) {
if (x % p != 0) continue;
largest = p;
while (x % p == 0) x /= p;
}
if (x > 1) largest = x;
// 我让1的最大质因数记作1，使它自然计入答案。
if (largest <= b) ans++;
}
cout << ans;
return 0;
}
代码-满分-筛最大质因数
时间 \(O(n\log\log n)\)，空间 \(O(n)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 1000005;
int largest[N];
int main() {
int n, b;
cin >> n >> b;
largest[1] = 1;
for (int p = 2; p <= n; p++) {
if (largest[p] != 0) continue;
// 我按质数从小到大覆盖，最后留下的因数就是最大的。
for (int j = p; j <= n; j += p) largest[j] = p;
}
int ans = 0;
for (int i = 1; i <= n; i++) {
if (largest[i] <= b) ans++;
}
cout << ans;
return 0;
}
P10719 [GESP202406 五级] 黑白格¶
提示1-先枚举小范围
20分做法，\(n,m\le 10\)。
另外40分做法，\(n=1\)。
看全部数据范围，\(n,m\le 100\)。
我先枚举四条边，再逐格数黑格子。
小矩阵和只有一行时，这个直接的办法就能覆盖前两个子任务。
提示2-固定上下两行
大矩阵要少枚举一条边。
我先固定上、下边界，把每一列在这两行之间的黑格子数加起来，就变成一排非负数。
提示3-非负数可以用双指针
列区间的和达到 \(k\) 后，我尝试缩短左边，直到不能再缩。
右边继续向前，寻找更好的面积。
上边界不能超过下边界。
每组上下边界只扫描一遍所有列。
代码-60分-逐格枚举矩形
时间 \(O(n^{3}m^{3})\)，空间 \(O(nm)\)，覆盖 \(n,m\le 10\) 和 \(n=1\) 两个子任务，不适用于一般最大规模。
#include <bits/stdc++.h>
using namespace std;
const int N = 105, INF = 1000000000;
int a[N][N];
int main() {
int n, m, k;
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) {
string s;
cin >> s;
for (int j = 1; j <= m; j++) a[i][j] = s[j - 1] - '0';
}
int ans = INF;
for (int top = 1; top <= n; top++) {
for (int bottom = top; bottom <= n; bottom++) {
for (int l = 1; l <= m; l++) {
for (int r = l; r <= m; r++) {
// 我先按题意逐格数，得到可以验证的小范围答案。
int count = 0;
for (int i = top; i <= bottom; i++) {
for (int j = l; j <= r; j++) count += a[i][j];
}
if (count >= k) ans = min(ans, (bottom - top + 1) * (r - l + 1));
}
}
}
}
cout << (ans == INF ? 0 : ans);
return 0;
}
代码-满分-压缩行与双指针
时间 \(O(n^{2}m)\)，空间 \(O(nm)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 105, INF = 1000000000;
int a[N][N], column[N];
int main() {
int n, m, k;
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) {
string s;
cin >> s;
for (int j = 1; j <= m; j++) a[i][j] = s[j - 1] - '0';
}
int ans = INF;
for (int top = 1; top <= n; top++) {
fill(column, column + m + 1, 0);
for (int bottom = top; bottom <= n; bottom++) {
for (int j = 1; j <= m; j++) column[j] += a[bottom][j];
int l = 1, sum = 0;
for (int r = 1; r <= m; r++) {
sum += column[r];
// 我利用列和非负，尽量收紧左边界。
while (l <= r && sum - column[l] >= k) sum -= column[l++];
if (sum >= k) ans = min(ans, (bottom - top + 1) * (r - l + 1));
}
}
}
cout << (ans == INF ? 0 : ans);
return 0;
}
P10720 [GESP202406 五级] 小杨的幸运数字¶
提示1-重复的质因数只算一种
40分做法，\(n\le 100\)、数值\(\le 10^{5}\)。
看全部数据范围，\(n\le 10^{4}\)、数值\(\le 10^{6}\)。
我先试 \(12=2\times 2\times 3\)：虽然有三个质因数相乘，但只有两种。
找到一个质因数后，要把它除干净再计一次。
提示2-查询多，先筛出答案
很多数重复分解不划算。
我让每个质数给自己的所有倍数加 1，得到每个数的不同质因数种类数。
筛到输入的最大值，查询时只检查计数是否为 2。
代码-40分-逐个试除
每个数时间 \(O(\sqrt{A})\)，额外空间 \(O(1)\)，覆盖第一个子任务。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
for (int t = 0; t < n; t++) {
int x, count = 0;
cin >> x;
for (int p = 2; p <= x / p; p++) {
if (x % p != 0) continue;
// 我把同一种质因数一次除干净，只计一种。
while (x % p == 0) x /= p;
count++;
}
if (x > 1) count++;
if (t > 0) cout << '\n';
cout << (count == 2 ? 1 : 0);
}
return 0;
}
代码-满分-筛质因数种类数
时间 \(O(A\log\log A+n)\)，空间 \(O(A+n)\)，\(A\) 为输入最大值。
#include <bits/stdc++.h>
using namespace std;
const int N = 1000005, M = 10005;
int count_prime[N], a[M];
int main() {
int n, largest = 0;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
largest = max(largest, a[i]);
}
for (int p = 2; p <= largest; p++) {
if (count_prime[p] != 0) continue;
// 我让每个质数只给自己的倍数加一次，不看它出现几次。
for (int j = p; j <= largest; j += p) count_prime[j]++;
}
for (int i = 0; i < n; i++) {
if (i > 0) cout << '\n';
cout << (count_prime[a[i]] == 2 ? 1 : 0);
}
return 0;
}
B4050 [GESP202409 五级] 挑战怪物¶
提示1-魔法放在最后也可以
20分做法，\(h\le 10\)。
40分做法，\(h\le 100\)。
看全部数据范围，\(t\le 10\)、\(h\le 10^{5}\)。
我先固定物理攻击次数 \(k\)，它们的总伤害就是 \(1+2+\cdots+2^{k-1}=2^k-1\)。
魔法可以移到最后，剩余血量就是要检查的数。
提示2-只枚举物理攻击次数
剩余为 0，答案候选是 \(k\)。
剩余是质数，答案候选是 \(k+1\)。
其他情况不能用一次魔法补上。
物理总伤害超过 \(h\) 就停，一共只需检查十几次，直接试除判质数足够。
代码-满分-枚举物理攻击次数
每组时间 \(O(\log h\sqrt{h})\)，额外空间 \(O(1)\)。
#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000000;
bool is_prime(int x) {
if (x < 2) return false;
for (int p = 2; p <= x / p; p++) {
if (x % p == 0) return false;
}
return true;
}
int main() {
int t;
cin >> t;
for (int test = 0; test < t; test++) {
int h;
cin >> h;
int ans = INF;
// 我只枚举物理攻击次数，剩余伤害交给至多一次魔法。
for (int k = 0, damage = 0; damage <= h; k++) {
if (damage == h) ans = min(ans, k);
else if (is_prime(h - damage)) ans = min(ans, k + 1);
damage += 1 << k;
}
if (test > 0) cout << '\n';
cout << (ans == INF ? -1 : ans);
}
return 0;
}
B4051 [GESP202409 五级] 小杨的武器¶
提示1-把好处集中起来
20分做法，\(n=1\)。
另外20分做法，\(m=2\)。
看全部数据范围，\(n,m\le 10^{5}\)，熟练度和变化量的绝对值\(\le 10^{4}\)。
有至少两件武器时，我把正的变化都给初始熟练度最高的武器，负的变化交给另一件。
提示2-只有一件武器是例外
我会拿 \(n=1\) 检查：每场战斗都必须参加，负数也躲不开，只能把所有变化都加上。
初始熟练度可能全为负数，不能把最大值初始化成 0。
代码-满分-集中正收益
时间 \(O(n+m)\)，额外空间 \(O(1)\)，覆盖全部子任务。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
long long best;
cin >> best;
for (int i = 2; i <= n; i++) {
long long x;
cin >> x;
best = max(best, x);
}
for (int i = 1; i <= m; i++) {
int x;
cin >> x;
// 我有第二件武器时可以转移负收益，只有一件就必须全接下。
if (n == 1 || x > 0) best += x;
}
cout << best;
return 0;
}
B4070 [GESP202412 五级] 奇妙数字¶
提示1-把不同质数分开考虑
40分做法，\(n\le 1000\)。
看全部数据范围，\(n\le 10^{12}\)。
我先分解 \(n\)。
不同质数互不影响，只要分别看每个质因数的指数够用几次。
提示2-指数先用最小的
同一个质数 \(p\)，\(p\)、\(p^{2}\)、\(p^{3}\) 都不同。
想选得最多，我先消耗指数 1，再消耗 2、3……
指数总量只有几十，直接依次扣掉即可。
瓶颈是分解 \(n\)，不是这几次加减。
代码-满分-分解与依次扣指数
时间 \(O(\sqrt{n})\)，额外空间 \(O(1)\)。
#include <bits/stdc++.h>
using namespace std;
int take(int count) {
int ans = 0;
// 我先用最小的指数，给后面的不同幂留下最多余量。
for (int exponent = 1; exponent <= count; exponent++) {
count -= exponent;
ans++;
}
return ans;
}
int main() {
long long n;
cin >> n;
int ans = 0;
for (long long p = 2; p <= n / p; p++) {
if (n % p != 0) continue;
int count = 0;
while (n % p == 0) {
n /= p;
count++;
}
ans += take(count);
}
if (n > 1) ans++;
cout << ans;
return 0;
}
B4071 [GESP202412 五级] 武器强化¶
提示1-不要只盯着当前最多的一类
20分做法，\(n\le 2\)。
另外20分做法，\(m\le 2\)。
看全部数据范围，\(n,m\le 1000\)，费用\(\le 10^{9}\)。
只有两种武器时，改一份材料能让一边加 1、另一边减 1。
但种类多了，处理一类后还要照顾其他类，直接贪心不够稳。
提示2-先假设武器 1 的目标数量
我枚举武器 1 至少达到 \(\operatorname{target}\) 份。
其他类最多只能留 \(\operatorname{target}-1\) 份，多出来的必须转给武器 1。
每类先转最便宜的材料。
如果武器 1 仍不够，再从所有剩余材料里选最便宜的补上。
提示3-为什么只转给武器 1
改给其他武器既不增加武器 1，也可能增加竞争者。
我把同样的材料改给武器 1，不会更差。
枚举所有目标数量，取最小费用。
原本就严格最多时，答案可以是 0。
费用和用 long long。
代码-20分-只有两种武器
时间 \(O(m\log m)\)，空间 \(O(m)\)，覆盖 \(n\le 2\) 的子任务。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m, first = 0;
vector<int> cost;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int p, c;
cin >> p >> c;
if (p == 1) first++;
else cost.push_back(c);
}
sort(cost.begin(), cost.end());
int second = cost.size(), need = 0;
if (n == 2 && second >= first) need = (second - first) / 2 + 1;
long long ans = 0;
// 我每转一份，武器1加一份，武器2少一份。
for (int i = 0; i < need; i++) ans += cost[i];
cout << ans;
return 0;
}
代码-满分-枚举目标数量
时间 \(O(m^{2}\log m+mn)\)，空间 \(O(n+m)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
const long long INF = 1LL << 60;
vector<int> material[N];
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int p, cost;
cin >> p >> cost;
material[p].push_back(cost);
}
for (int i = 1; i <= n; i++) sort(material[i].begin(), material[i].end());
long long ans = INF;
for (int target = max(1, (int)material[1].size()); target <= m; target++) {
int now = material[1].size();
long long cost = 0;
vector<int> remaining;
for (int i = 2; i <= n; i++) {
int count = material[i].size();
// 我先把每个竞争者压到target-1，必选的是该类最便宜的材料。
int need = max(0, count - target + 1);
now += need;
for (int j = 0; j < need; j++) cost += material[i][j];
for (int j = need; j < count; j++) remaining.push_back(material[i][j]);
}
if (now < target) {
sort(remaining.begin(), remaining.end());
for (int c : remaining) {
if (now >= target) break;
cost += c;
now++;
}
}
ans = min(ans, cost);
}
cout << ans;
return 0;
}
P11960 [GESP202503 五级] 平均分配¶
提示1-小范围先枚举分配
20分做法，\(n\le 8\)。
另外20分做法，出价只有 0、1。
看全部数据范围，\(n\le 10^{5}\)，出价\(\le 10^{9}\)。
我先枚举哪些物品给 \(B\)，检查恰好选了 \(n\) 件，其余给 \(C\)。
提示2-先全部卖给 C 再改主意
全部卖给 \(C\) 的收入固定。
第 \(i\) 件改卖给 \(B\)，收入变化是 \(b_{i}-c_{i}\)。
我只需选最大的 \(n\) 个差值。
差值即使为负也得选够 \(n\) 件，不能只选正数。
代码-20分-枚举分配集合
时间 \(O(n2^{2n})\)，空间 \(O(n)\)，只适用于 \(n\le 8\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 20;
const long long NEG = -(1LL << 60);
int b[N], c[N];
int main() {
int n;
cin >> n;
for (int i = 0; i < 2 * n; i++) cin >> b[i];
for (int i = 0; i < 2 * n; i++) cin >> c[i];
long long ans = NEG;
for (int mask = 0; mask < (1 << (2 * n)); mask++) {
int count = 0;
long long sum = 0;
for (int i = 0; i < 2 * n; i++) {
if ((mask >> i) & 1) {
count++;
sum += b[i];
} else sum += c[i];
}
// 我只接受两个人各拿n件的分配。
if (count == n) ans = max(ans, sum);
}
cout << ans;
return 0;
}
代码-满分-按差值排序
时间 \(O(n\log n)\)，空间 \(O(n)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
int b[N];
long long difference[N];
bool cmp(long long x, long long y) {
return x > y;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
long long ans = 0;
cin >> n;
for (int i = 0; i < 2 * n; i++) cin >> b[i];
for (int i = 0; i < 2 * n; i++) {
int c;
cin >> c;
ans += c;
difference[i] = 1LL * b[i] - c;
}
// 我先全部卖给C，再挑收益变化最大的n件改给B。
sort(difference, difference + 2 * n, cmp);
for (int i = 0; i < n; i++) ans += difference[i];
cout << ans;
return 0;
}
P11961 [GESP202503 五级] 原根判断¶
提示1-先照定义计算
40分做法，\(p\le 1000\)。
看全部数据范围，\(t\le 20\)，\(p\le 10^{9}\)，\(p\) 为质数，\(1<a<p\)。
我先逐次乘 \(a\) 并取模，记录第一次出现 1 的指数。
它恰好等于 \(p-1\)，就符合定义。
提示2-大范围需要一个数学性质
逐次乘到十亿不行。
这里需要补一个性质：\(p\) 为质数时，第一次出现 1 的指数一定整除 \(p-1\)。
所以若提前出现，它就是 \(p-1\) 的一个真因数。
提示3-只检查几个关键指数
我分解 \(p-1\)。
对每个不同质因数 \(q\)，检查 \(a^{\frac{p-1}{q}}\equiv 1\pmod p\) 是否成立。
任何真因数都能整除其中某个指数，所以这些检查能排除所有提前出现 1 的情况。
幂用快速幂计算。
代码-40分-按定义枚举指数
每组时间 \(O(p)\)，额外空间 \(O(1)\)，覆盖 \(p\le 1000\) 的测试点。
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
for (int test = 0; test < t; test++) {
int a, p;
cin >> a >> p;
long long value = 1;
int order = 0;
// 我逐次计算余数，找到第一次回到1的指数。
for (int i = 1; i <= p - 1; i++) {
value = value * a % p;
if (value == 1) {
order = i;
break;
}
}
if (test > 0) cout << '\n';
cout << (order == p - 1 ? "Yes" : "No");
}
return 0;
}
代码-满分-分解 p-1 与快速幂
每组时间 \(O(\sqrt{p}+\omega(p-1)\log p)\)，额外空间 \(O(1)\)；\(\omega\) 表示不同质因数个数。
#include <bits/stdc++.h>
using namespace std;
long long power(long long a, int exponent, int mod) {
long long result = 1;
while (exponent > 0) {
if (exponent % 2 == 1) result = result * a % mod;
a = a * a % mod;
exponent /= 2;
}
return result;
}
bool check(int a, int p) {
int x = p - 1;
for (int q = 2; q <= x / q; q++) {
if (x % q != 0) continue;
// 我只检查不同质因数对应的关键指数，不逐次计算全部幂。
if (power(a, (p - 1) / q, p) == 1) return false;
while (x % q == 0) x /= q;
}
if (x > 1 && power(a, (p - 1) / x, p) == 1) return false;
return true;
}
int main() {
int t;
cin >> t;
for (int test = 0; test < t; test++) {
int a, p;
cin >> a >> p;
if (test > 0) cout << '\n';
cout << (check(a, p) ? "Yes" : "No");
}
return 0;
}
P13013 [GESP202506 五级] 奖品兑换¶
提示1-先固定一种方式的数量
60分做法，\(n,m\le 500\)，\(a,b\le 100\)。
看全部数据范围，\(n,m\le 10^{9}\)，\(a,b\le 10^{4}\)。
我先枚举第一种换几份，再用剩余券尽量换第二种，就能解决小范围。
提示2-反过来猜总份数
大范围不能逐份枚举。
我猜能否兑换 \(k\) 份：若能换 \(k\) 份，也能换更少，所以可以二分。
让 \(a\ge b\)。
设其中 \(x\) 份用 \((a,b)\)，两种券的消耗是 \(kb+x(a-b)\)、\(ka-x(a-b)\)。
提示3-把条件变成 x 的范围
第一种券给出 \(x\) 的上界，第二种券给出下界。
再和 \(0\le x\le k\) 相交，有整数解就可行。
\(a=b\) 时单独算 \(\left\lfloor\frac{\min(n,m)}{a}\right\rfloor\)，避免除以 0。
乘法和边界都用 long long。
代码-60分-枚举第一种份数
时间 \(O\left(\min\left(\frac{n}{a},\frac{m}{b}\right)+1\right)\)，额外空间 \(O(1)\)。
#include <bits/stdc++.h>
using namespace std;
int main() {
long long n, m, a, b;
cin >> n >> m >> a >> b;
long long ans = 0;
// 我先确定第一种换几份，第二种就直接用剩余券算。
for (long long x = 0; x * a <= n && x * b <= m; x++) {
long long y = min((n - x * a) / b, (m - x * b) / a);
ans = max(ans, x + y);
}
cout << ans;
return 0;
}
代码-满分-二分答案
时间 \(O\left(\log\left(\frac{n+m}{a+b}+1\right)\right)\)，额外空间 \(O(1)\)。
#include <bits/stdc++.h>
using namespace std;
long long n, m, a, b;
bool check(long long k) {
if (k * b > n || k * b > m) return false;
long long difference = a - b;
long long l = 0;
if (k * a > m) l = (k * a - m + difference - 1) / difference;
long long r = min(k, (n - k * b) / difference);
return l <= r;
}
int main() {
cin >> n >> m >> a >> b;
long long ans = 0;
if (a == b) ans = min(n, m) / a;
else {
if (a < b) swap(a, b);
long long l = 0, r = (n + m) / (a + b);
// 我检查总份数是否可行，而不实际安排每一份。
while (l <= r) {
long long mid = (l + r) / 2;
if (check(mid)) {
ans = mid;
l = mid + 1;
} else r = mid - 1;
}
}
cout << ans;
return 0;
}
P13014 [GESP202506 五级] 最大公因数¶
提示1-先按询问直接求
60分做法，\(n\le 1000\)、\(q\le 10\)。
看全部数据范围，\(n,q\le 10^{5}\)，\(a_{i}\le 1000\)。
我先每次逐个合并 \(\gcd\)，拿到小范围的答案，再观察所有数同时加 \(i\) 后什么没有变。
提示2-两个数的差没有变
我用 \(\gcd(x,y)=\gcd(x,y-x)\)。
全部加 \(i\) 后，\(a_{j}-a_{1}\) 仍然不变。
先求所有这些差的 \(\gcd\)，记作 \(d\)。
每次只需输出 \(\gcd(a_{1}+i,d)\)。
提示3-全部相等也能自然处理
我会试 \(n=1\) 或所有数相等：这时 \(d=0\)，\(\gcd(x,0)=x\)，仍然正确。
不需要给这些情况另写一套算法。
代码-60分-逐次合并 gcd
时间 \(O(nq\log A)\)，空间 \(O(n)\)，\(A\) 为询问中数值上界。
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int a[N];
int gcd(int a, int b) {
while (b != 0) {
int r = a % b;
a = b;
b = r;
}
return a;
}
int main() {
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= q; i++) {
int ans = 0;
// 我先按定义逐个合并，作为小范围解法。
for (int j = 1; j <= n; j++) ans = gcd(ans, a[j] + i);
if (i > 1) cout << '\n';
cout << ans;
}
return 0;
}
代码-满分-预处理差值 gcd
时间 \(O((n+q)\log A)\)，额外空间 \(O(1)\)。
#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b) {
while (b != 0) {
int r = a % b;
a = b;
b = r;
}
return a;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, q, first, difference = 0;
cin >> n >> q >> first;
for (int i = 2; i <= n; i++) {
int x;
cin >> x;
// 我只保留同时加数后仍不变的差值信息。
difference = gcd(difference, abs(x - first));
}
for (int i = 1; i <= q; i++) {
if (i > 1) cout << '\n';
cout << gcd(first + i, difference);
}
return 0;
}
P14073 [GESP202509 五级] 数字选取¶
提示1-先找到一个合法方案
40分做法，\(n\le 1000\)。
看全部数据范围，\(n\le 10^{5}\)。
我可以选 1 和所有质数，它们两两互质。
接下来要证明不可能选得更多。
提示2-每个数都要占一个质因数
每个大于 1 的数至少有一个质因数。
两两互质，就不能共用质因数。
所以它们的数量最多等于质数个数，再加上 1。
用筛法统计质数即可，\(n=1\) 时答案就是 1。
代码-满分-筛法统计质数
时间 \(O(n\log\log n)\)，空间 \(O(n)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
bool composite[N];
int main() {
int n;
cin >> n;
// 我先找出所有质数，它们加上1就达到数量上界。
for (int p = 2; p <= n / p; p++) {
if (composite[p]) continue;
for (int j = p * p; j <= n; j += p) composite[j] = true;
}
int ans = 1;
for (int i = 2; i <= n; i++) {
if (!composite[i]) ans++;
}
cout << ans;
return 0;
}
P14074 [GESP202509 五级] 有趣的数字和¶
提示1-先逐个数，找规律
40分做法，\(r\le 10^{4}\)。
另外30分做法，\(l=1\)、\(r=2^{k}-1\)，\(k>1\)。
看全部数据范围，\(r\le 10^{9}\)。
我先逐个统计二进制的 1，再按四个一组观察：\(4x\)、\(4x+1\)、\(4x+2\)、\(4x+3\)。
提示2-每组的贡献固定
四个数的高位都一样，低两位分别是 00、01、10、11。
奇数个 1 的两个数，要么是两端，要么是中间两个，它们的和总是 \(8x+3\)。
提示3-整组直接求和，零头再检查
我求 0 到 \(n\) 的前缀答案。
完整组数为 \(k=\left\lfloor\frac{n+1}{4}\right\rfloor\)，贡献是 \(k(4k-1)\)，末尾至多剩三个数。
区间答案就是 \(f(r)-f(l-1)\)。
不能仍然逐组循环，十亿范围要用公式。
计算用 long long。
代码-40分-逐个检查二进制
时间 \(O((r-l+1)\log r)\)，额外空间 \(O(1)\)。
#include <bits/stdc++.h>
using namespace std;
bool interesting(long long x) {
int parity = 0;
while (x > 0) {
parity ^= x % 2;
x /= 2;
}
return parity == 1;
}
int main() {
long long l, r, ans = 0;
cin >> l >> r;
// 我先直接统计，方便验证后面找到的分组规律。
for (long long i = l; i <= r; i++) {
if (interesting(i)) ans += i;
}
cout << ans;
return 0;
}
代码-满分-四个一组求前缀和
时间 \(O(\log r)\)，额外空间 \(O(1)\)。每次前缀计算只检查至多三个零头。
#include <bits/stdc++.h>
using namespace std;
bool interesting(long long x) {
int parity = 0;
while (x > 0) {
parity ^= x % 2;
x /= 2;
}
return parity == 1;
}
long long prefix(long long n) {
long long groups = (n + 1) / 4;
// 我把所有完整组用等差数列公式一次加完，不再逐组枚举。
long long ans = groups * (4 * groups - 1);
for (long long i = groups * 4; i <= n; i++) {
if (interesting(i)) ans += i;
}
return ans;
}
int main() {
long long l, r;
cin >> l >> r;
cout << prefix(r) - prefix(l - 1);
return 0;
}
P14917 [GESP202512 五级] 数字移动¶
提示1-为什么想到枚举答案
40分做法，\(n,a_i\le 100\)。
看全部数据范围，\(n,a_i\le 10^5\)，每个值恰好出现两次。
我先想直接安排移动，但先动哪个、放在哪里，选择太多。
题目只问最小的 \(x\)，我就换个问法：如果 \(x\) 已经确定，能不能完成？
小范围的数值最多只有 \(100\)，我可以从 \(x=0\) 开始逐个试。
第一个能完成的值，就是最小答案，不用枚举每一步怎么移动。
提示2-固定答案后，哪些数不能动
大于 \(x\) 的数不能移动，它们之间的相对顺序也不能改变。
我把不超过 \(x\) 的数暂时拿掉，只检查留下的数能否按顺序两两配对。
例如序列 \(1,2,1,2\)：\(x=0\) 时都不能动，无法配对。
\(x=1\) 时拿掉两个 \(1\)，剩下 \(2,2\)，已经成对。
再把两个 \(1\) 搬到一起即可。
提示3-40分怎样枚举并判断
我依次检查 \(x=0,1,2,\ldots,A\)，其中 \(A\) 是最大元素。
检查时跳过能移动的数，把剩下的数每两个分成一组。
有一组不同，这个 \(x\) 就不行。
如果每组都相同，就能把可移动的数也按对放到序列两端，完成排列。
\(x=A\) 时所有数都能动，一定可行，所以不会漏掉答案。
每个 \(x\) 扫描一遍序列，总时间是 \(O(nA)\)。
这就是40分枚举答案的做法。
提示4-怎样从枚举改成二分
\(x\) 越大，可以移动的数越多。
原来能完成的移动，现在仍能完成，所以可行性不会从“能”变回“不能”。
我用二分寻找第一个可行的 \(x\)，不用再逐个试，时间降为 \(O(n\log A)\)。
注意操作是移动一个元素，不是交换两个元素。
代码-40分-枚举体力上限
时间 \(O(nA)\)，空间 \(O(n)\)，\(A\) 为最大元素；只适用于 \(n,A\le 100\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int a[N], n;
bool check(int limit) {
int last = 0;
for (int i = 0; i < n; i++) {
if (a[i] <= limit) continue;
if (last == 0) last = a[i];
else {
if (last != a[i]) return false;
last = 0;
}
}
return last == 0;
}
int main() {
int largest = 0;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
largest = max(largest, a[i]);
}
int ans = 0;
// 我先从小到大试上限，找到第一个能让固定数字成对的值。
while (ans <= largest && !check(ans)) ans++;
cout << ans;
return 0;
}
代码-满分-二分体力上限
时间 \(O(n\log A)\)，空间 \(O(n)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int a[N], n;
bool check(int limit) {
int last = 0;
// 我只比较不能移动的数字，保留它们原来的相对顺序。
for (int i = 0; i < n; i++) {
if (a[i] <= limit) continue;
if (last == 0) last = a[i];
else {
if (last != a[i]) return false;
last = 0;
}
}
return last == 0;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int largest = 0;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
largest = max(largest, a[i]);
}
int l = 0, r = largest;
while (l < r) {
int mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid + 1;
}
cout << l;
return 0;
}
P14918 [GESP202512 五级] 相等序列¶
提示1-把乘除换成指数加减
60分做法，\(n,a_{i}\le 100\)。
看全部数据范围，\(n,a_{i}\le 10^{5}\)。
我先分解质因数。
一次乘或除 \(p\)，只会让 \(p\) 的指数加 1 或减 1，不影响其他质数。
提示2-每个质数单独找中位数
所有数最终相等，就要让每种质因数的指数一致。
调整次数是到目标指数的距离和，中位数能让这个和最小。
没有这个质因数的数，它的指数是 0，不能漏掉。
提示3-零很多，不用真的补进数组
我只存出现过的正指数。
排序后，前面还有 \(n\) 减去记录数个 0，照这个数量定位中位数即可。
这样不会为每个质数都开一个长度 \(n\) 的数组。
先筛最小质因数，再分解每个输入数。
代码-60分-完整记录小范围指数
时间 \(O(A\sqrt{A}+An\log n)\)，空间 \(O(n)\)，仅适用于 \(n,A\le 100\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int a[N], exponent[N];
bool is_prime(int x) {
for (int p = 2; p <= x / p; p++) {
if (x % p == 0) return false;
}
return x >= 2;
}
int main() {
int n, largest = 1;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
largest = max(largest, a[i]);
}
long long ans = 0;
for (int p = 2; p <= largest; p++) {
if (!is_prime(p)) continue;
for (int i = 0; i < n; i++) {
int x = a[i];
exponent[i] = 0;
while (x % p == 0) {
x /= p;
exponent[i]++;
}
}
sort(exponent, exponent + n);
// 我把没有这个质因数的0也放进排序，再取中位数。
int middle = exponent[n / 2];
for (int i = 0; i < n; i++) ans += abs(exponent[i] - middle);
}
cout << ans;
return 0;
}
代码-满分-筛分解与稀疏指数
设 \(A\) 为最大值、\(K\) 为非零指数记录总数，时间 \(O(A\log\log A+n\log A+K\log n)\)，空间 \(O(A+n+K)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int a[N], smallest[N];
vector<int> exponent[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, largest = 1;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
largest = max(largest, a[i]);
}
for (int p = 2; p <= largest; p++) {
if (smallest[p] != 0) continue;
smallest[p] = p;
if (p > largest / p) continue;
for (int j = p * p; j <= largest; j += p) {
if (smallest[j] == 0) smallest[j] = p;
}
}
for (int i = 0; i < n; i++) {
int x = a[i];
while (x > 1) {
int p = smallest[x], count = 0;
while (x % p == 0) {
x /= p;
count++;
}
exponent[p].push_back(count);
}
}
long long ans = 0;
for (int p = 2; p <= largest; p++) {
if (exponent[p].empty()) continue;
sort(exponent[p].begin(), exponent[p].end());
int zeros = n - exponent[p].size(), middle = 0;
// 我不实际补零，只把它们的数量算进中位数的位置。
if (n / 2 >= zeros) middle = exponent[p][n / 2 - zeros];
ans += 1LL * zeros * middle;
for (int x : exponent[p]) ans += abs(x - middle);
}
cout << ans;
return 0;
}
P15798 [GESP202603 五级] 有限不循环小数¶
提示1-从小数的分母想起
看全部数据范围，\(1\le L\le R\le 10^{6}\)。
我先想有限小数是怎样写成分数的：分母可以是 10、100、1000……它们只有 2 和 5 两种质因数。
提示2-把 2 和 5 除干净
所以我检查 \(a\)：不断除掉因数 2，再不断除掉因数 5。
最后剩下 1，倒数就能化为有限小数。
区间最多一百万个数，直接逐个检查就够了。
\(a=1\) 也要计数。
代码-满分-逐个检查
时间 \(O((R-L+1)\log R)\)，额外空间 \(O(1)\)。原题未列出部分分子任务。
P15799 [GESP202603 五级] 找数¶
提示1-先逐对比较
40分做法，\(n,m\le 1000\)。
看全部数据范围，\(n,m\le 10^{5}\)，元素\(\le 10^{9}\)。
我先枚举 \(A\)、\(B\) 的每一对数，相等就计数。
数组内部没有重复，不需要额外去重。
提示2-排序后只往前走
两层循环太慢，我把两个数组都排好序，再比较当前的两个数。
较小的数不可能匹配另一个数组后面的数，就让它往前走。
相等时计数，两边都往前走。
代码-40分-两层循环
时间 \(O(nm)\)，空间 \(O(n+m)\)。仅适用于 \(n,m\le 1000\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int a[N], b[N];
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= m; i++) cin >> b[i];
int ans = 0;
// 我先直接检查每一对数，作为小范围的解法。
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a[i] == b[j]) ans++;
}
}
cout << ans;
return 0;
}
代码-满分-排序与双指针
时间 \(O(n\log n+m\log m)\)，空间 \(O(n+m)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int a[N], b[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= m; i++) cin >> b[i];
sort(a + 1, a + n + 1);
sort(b + 1, b + m + 1);
int i = 1, j = 1, ans = 0;
while (i <= n && j <= m) {
// 我让较小的数往前走，寻找可能相等的数。
if (a[i] < b[j]) i++;
else if (a[i] > b[j]) j++;
else {
ans++;
i++;
j++;
}
}
cout << ans;
return 0;
}
P17010 [GESP202606 五级] 排排坐¶
提示1-一个数会被算几次
看全部数据范围，\(n\le 1000\)，\(a_{i}\le 1000\)。
我把每个人的糖果数展开，发现第一位的数被算 \(n\) 次，第二位被算 \(n-1\) 次，最后一位只算一次。
提示2-大的数应该坐哪里
既然越靠左被算得越多，我就把大的数放前面。
交换一对前小后大的数，总量只会增加。
降序排序，再累加每个前缀和。
用 long long 保存总量。
代码-满分-降序排序
时间 \(O(n\log n)\)，空间 \(O(n)\)。原题未列出部分分子任务。
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int a[N];
bool cmp(int x, int y) {
return x > y;
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
// 我把大的数放在前面，让它被更多个前缀重复计算。
sort(a + 1, a + n + 1, cmp);
long long sum = 0, ans = 0;
for (int i = 1; i <= n; i++) {
sum += a[i];
ans += sum;
}
cout << ans;
return 0;
}
P17011 [GESP202606 五级] 晚宴¶
提示1-先看枚举够不够
看全部数据范围，\(n\le 1000\)，美味度\(\le 10^{6}\)，互不相同，保证存在合法方案。
我先算一下规模：两两组合不到五十万对，可以直接检查，不必按美味度开大数组。
提示2-互质就是最大公约数为 1
我枚举 \(i<j\)，用辗转相除法求 \(\gcd\)。
只有 \(\gcd=1\) 时，才用两数之和更新答案。
不能只取最大的两个数，它们可能不互质。
也不能把一道菜选两次。
代码-满分-枚举菜肴对
时间 \(O(n^{2}\log V)\)，空间 \(O(n)\)，\(V\) 为最大美味度。原题未列出部分分子任务。
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int a[N];
int gcd(int a, int b) {
while (b != 0) {
int r = a % b;
a = b;
b = r;
}
return a;
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
int ans = 0;
for (int i = 1; i <= n; i++) {
// 我只向后找另一道菜，避免重复枚举和选择同一道菜。
for (int j = i + 1; j <= n; j++) {
if (gcd(a[i], a[j]) == 1) ans = max(ans, a[i] + a[j]);
}
}
cout << ans;
return 0;
}
P17455 [GESP202609 五级] 哥德巴赫猜想¶
提示1-只枚举较小的那个
40分做法，\(n\le 100\)。
看全部数据范围，\(n\le 10^{6}\)。
我先枚举 \(p\)，另一个数就是 \(n-p\)。
为了不重复计数，只让 \(p\le n-p\)，也就是 \(p\le \frac{n}{2}\)。
提示2-重复判质数不划算
小范围可以每次试除。
大范围要检查很多数，我先用筛法把 \(n\) 以内的合数标出来，之后每次判断只要一次查表。
\(2+2\) 也是合法方案，1 则不是质数。
代码-40分-逐次试除
时间 \(O(n\sqrt{n})\)，额外空间 \(O(1)\)。覆盖 \(n\le 100\) 的子任务。
#include <bits/stdc++.h>
using namespace std;
bool is_prime(int x) {
if (x < 2) return false;
for (int i = 2; i <= x / i; i++) {
if (x % i == 0) return false;
}
return true;
}
int main() {
int n;
cin >> n;
int ans = 0;
// 我只枚举较小的质数，交换顺序就不会重复算。
for (int p = 2; p <= n / 2; p++) {
if (is_prime(p) && is_prime(n - p)) ans++;
}
cout << ans;
return 0;
}
代码-满分-筛法
时间 \(O(n\log\log n)\)，空间 \(O(n)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 1000005;
bool composite[N];
int main() {
int n;
cin >> n;
composite[0] = composite[1] = true;
// 我先统一标记合数，避免枚举分解时反复试除。
for (int p = 2; p <= n / p; p++) {
if (composite[p]) continue;
for (int j = p * p; j <= n; j += p) composite[j] = true;
}
int ans = 0;
for (int p = 2; p <= n / 2; p++) {
if (!composite[p] && !composite[n - p]) ans++;
}
cout << ans;
return 0;
}
P17456 [GESP202609 五级] 饮品调制¶
提示1-先弄明白怎样配出目标甜度
40分做法，\(n=2\)。
看全部数据范围，\(n\le2000\)，每种原料最多 \(100\) 升，原料甜度和目标甜度都在 \(0\) 到 \(200\) 之间。
甜度就是每升有多少克糖。我先拿目标甜度 \(10\) 举例。
一升甜度 \(14\) 的原料，比要求多 \(4\) 克糖；一升甜度 \(8\) 的原料，比要求少 \(2\) 克糖。
所以一升前者配两升后者，多出的 \(4\) 克恰好补上少的 \(4\) 克，混合后甜度就是 \(10\)。
提示2-40分：两种原料分情况考虑
有原料甜度恰好为目标值，就能直接使用。另一种若不等于目标值，混进去只会把甜度带偏。
两种都比目标甜，或者都比目标淡，就配不出来，答案为 \(0\)。
一种偏甜、一种偏淡时，我让多出的糖和少的糖恰好抵消，直到其中一种用完。
例如甜度 \(14\) 的有 \(2\) 升，甜度 \(8\) 的有 \(3\) 升，目标为 \(10\)。偏淡原料只能补上 \(6\) 克糖差，所以用 \(1.5\) 升偏甜原料和 \(3\) 升偏淡原料，共 \(4.5\) 升。
代码中的sugar表示两边能够抵消的糖差，取两边可提供糖差的较小值，再分别除以每升的偏差，得到两种原料的使用体积。
提示3-原料多了，先假设全部用上
我想让体积尽量大，不妨先把全部原料算进去，再看需要少用多少。
对每种原料，记 \(d_i=s_i-t\)。它的糖差为 \(v_i d_i\)，所有原料的总糖差为：
\(D=0\)：已经正好，全部保留。
\(D>0\)：整体偏甜，要少用一些偏甜原料。少用偏淡原料反而会更甜，不划算。
\(D<0\)：整体偏淡，道理相同，少用一些偏淡原料。
甜度恰好为目标值的原料没有糖差，始终全部保留。
提示4-为什么先少用甜度偏差最大的
目标仍为 \(10\)，假设总共多了 \(4\) 克糖差。
少用甜度 \(18\) 的原料，每少用一升，糖少了 \(18\) 克，但目标糖量也少了 \(10\) 克，所以糖差只减少 \(8\) 克。
少用甜度 \(12\) 的原料，每少用一升，糖差只减少 \(2\) 克。
因而前者只需少用 \(0.5\) 升，后者却要少用 \(2\) 升。我想保留更多体积，就应先少用偏差更大的原料。
一种原料全去掉仍不够，就继续下一种；够了就只去掉需要的小数升，立刻停止。
提示5-代码怎样统一处理偏甜和偏淡
偏甜时，正的 \(d_i\) 是需要删减的那一侧，数值越大，每少用一升越有效。
偏淡时，我把 \(D\) 和所有 \(d_i\) 都取相反数，也变成同样的处理：按 \(d_i\) 从大到小，只考虑正数。
若这份原料的糖差不超过剩余要消去的糖差，就整份去掉；否则只去掉 \(D/d_i\) 升。
我用选择排序：每轮在剩余原料中找到最大的 \(d_i\)，交换到当前位置。\(n\le2000\)，约两百万次比较就够了。
最后一次除法用小数计算。代码只用数组、结构体和普通循环，支持C++14及更早的C++11标准。
代码-40分-两种原料配平
只适用于 \(n=2\)。时间、空间均为 \(O(1)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 5;
int v[N], s[N];
int main() {
int n, t;
cin >> n >> t;
for (int i = 0; i < n; i++) cin >> v[i] >> s[i];
int d1 = s[0] - t, d2 = s[1] - t;
double ans = 0;
if (d1 == 0 || d2 == 0) {
if (d1 == 0) ans += v[0];
if (d2 == 0) ans += v[1];
} else if (d1 * d2 < 0) {
// 我先找两边最多能抵消多少糖差，再换算各自需要多少升。
int sugar = min(v[0] * abs(d1), v[1] * abs(d2));
ans = 1.0 * sugar / abs(d1) + 1.0 * sugar / abs(d2);
}
cout << fixed << setprecision(3) << ans;
return 0;
}
代码-满分-按每升糖差贪心删减
时间 \(O(n^2)\)，空间 \(O(n)\)。选择排序可处理全部范围；总糖差保留为整数，最后一次部分删减才做小数除法。
#include <bits/stdc++.h>
using namespace std;
const int N = 2005;
struct Drink {
int v, d;
} a[N];
int main() {
int n, t;
cin >> n >> t;
long long total = 0;
double ans = 0;
for (int i = 0; i < n; i++) {
int s;
cin >> a[i].v >> s;
a[i].d = s - t;
ans += a[i].v;
total += 1LL * a[i].v * a[i].d;
}
// 整体偏淡时，我把符号反过来，仍然只删减正偏差的原料。
if (total < 0) {
total = -total;
for (int i = 0; i < n; i++) a[i].d = -a[i].d;
}
// 我每轮找出剩余原料中偏差最大的，把整份记录交换过来。
for (int i = 0; i < n - 1; i++) {
int k = i;
for (int j = i + 1; j < n; j++) {
if (a[j].d > a[k].d) k = j;
}
Drink temp = a[i];
a[i] = a[k];
a[k] = temp;
}
// 我先少用每升能消去最多糖差的原料，尽量保留体积。
for (int i = 0; i < n; i++) {
if (total == 0 || a[i].d <= 0) break;
long long sugar = 1LL * a[i].v * a[i].d;
if (sugar <= total) {
ans -= a[i].v;
total -= sugar;
} else {
// 这一份只需要去掉一部分，必须用小数除法。
ans -= 1.0 * total / a[i].d;
total = 0;
}
}
cout << fixed << setprecision(3) << ans;
return 0;
}