上海市计算机学会2023年3月乙组竞赛题解
T1 卡片游戏
给定 n 张卡片，每张卡片有正反两面的数字。需要将这些卡片填入形如：
A - B + C - D + ... 的表达式中，其中每个字母代表一张卡片的一面。目标是使整个表达式的值最大。
观察表达式结构可知，一半的卡片会被加上（正号位置），另一半会被减去（负号位置）。因此策略为：
- 先假设所有卡片都以其较大的一面参与运算，总和为 sum = Σ max(a[i], b[i])。
- 接下来需从中选出 n/2 张卡片转为"被减"状态。若某张卡片从 max(a[i], b[i]) 变为 min(a[i], b[i]) 被减，则其对总和的影响是减少了 a[i] + b[i]（因为原本加了大的，现在要减小的）。
- 为了最小化损失，应优先选择 a[i] + b[i] 最小的卡片进行翻转。
算法步骤：
- 读入每张卡片的 a[i], b[i]；
- 累加 max(a[i], b[i]) 到答案；
- 计算每张卡片的 a[i] + b[i] 并排序；
- 减去前 n/2 小的 a[i] + b[i] 值。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<long long> sums;
long long total = 0;
for (int i = 0; i < n; ++i) {
long long a, b;
cin >> a >> b;
total += max(a, b);
sums.push_back(a + b);
}
sort(sums.begin(), sums.end());
for (int i = 0; i < n / 2; ++i) {
total -= sums[i];
}
cout << total << endl;
return 0;
}
T2 邀请方案数
有 a、b、c、d 四类人，分别表示：不认识任何人、只认识小爱、只认识小艾、同时认识两人。要求选出若干人，使得最终能邀请到小爱和小艾。条件是所选集合中必须存在至少一人认识小爱，且至少一人认识小艾。
合法方案分为两类：
- 包含至少一个 d 类成员（因 d 同时认识两人）；
- 不包含任何 d 成员，但至少有一个 b 和一个 c 成员。
使用容斥原理或直接分类计数：
- 第一类：d 至少选一个（2^d - 1 种方式），其余 a、b、c 可任意选（各 2^a, 2^b, 2^c）；
- 第二类：d 全不选，b 至少选一个（2^b - 1），c 至少选一个（2^c - 1），a 任意（2^a）。
总方案数为：
(2^d - 1) × 2^{a+b+c} + (2^b - 1)(2^c - 1) × 2^a
注意模运算下快速幂的实现。
#include <iostream>
using namespace std;
const int MOD = 998244353;
long long qpow(long long base, long long exp) {
long long res = 1;
while (exp) {
if (exp & 1) res = res * base % MOD;
base = base * base % MOD;
exp >>= 1;
}
return res;
}
int main() {
int T;
cin >> T;
while (T--) {
long long a, b, c, d;
cin >> a >> b >> c >> d;
long long pow_a = qpow(2, a);
long long pow_b = qpow(2, b);
long long pow_c = qpow(2, c);
long long pow_d = qpow(2, d);
long long part1 = (pow_d - 1 + MOD) % MOD;
part1 = part1 * pow_a % MOD * pow_b % MOD * pow_c % MOD;
long long part2 = (pow_b - 1 + MOD) % MOD;
part2 = part2 * ((pow_c - 1 + MOD) % MOD) % MOD;
part2 = part2 * pow_a % MOD;
cout << (part1 + part2) % MOD << '\n';
}
return 0;
}
T3 神秘信号
给定基础信号串 a 和接收串 s。a 中字符唯一，机器只能完整发送 a。s 是多个 a 的子序列交错形成。问最少需要多少台机器才能生成 s？若非法则输出 "error"。
贪心模拟法：
- 用数组 cnt[i] 表示当前正在等待匹配 a[i] 的机器数量。
- 遍历 s 中每个字符 ch，查找其在 a 中的位置 pos。
- 如果 cnt[pos] > 0，说明已有机器处于该状态，复用一台，将其推进至下一状态（即 cnt[pos+1]++）。
- 否则，若 pos == 0（即 ch 是 a 的首字符），则新开一台机器（ans++）；否则无法匹配，返回 error。
- 最后检查是否还有未完成匹配的机器（即 cnt[1..len-1] 是否全为 0）。
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
int main() {
string a, s;
cin >> a >> s;
int len = a.size();
int pos_map[256] = {0};
for (int i = 0; i < len; ++i) {
pos_map[a[i]] = i;
}
int state_count[10] = {0}; // 最多6个字符
int machines = 0;
for (char ch : s) {
int p = pos_map[ch];
if (state_count[p] > 0) {
state_count[p]--;
} else {
if (p != 0) {
cout << "error" << endl;
return 0;
}
machines++;
}
if (p + 1 < len) {
state_count[p + 1]++;
}
}
for (int i = 1; i < len; ++i) {
if (state_count[i] > 0) {
cout << "error" << endl;
return 0;
}
}
cout << machines << endl;
return 0;
}
T4 平整序列
给定序列 a 和最多 m 次修改机会，定义"不平整指数"为相邻元素差绝对值的最大值。求最小可能的不平整指数。
核心思想：二分答案 + 动态规划验证可行性。
设 f[i][j] 表示考虑前 i 个位置，保留第 i 个位置不变，并使用 j 次修改时，能达到的最小不平整指数。但更优的方法是枚举保留哪些点不变。
优化思路：
- 由于 m 较小，实际可变点有限。考虑保留 k = n - m 个点不变。
- 对于任意两个保留点 i 和 j（i < j），中间所有点均可修改，因此可以构造出一条线性变化路径，使得相邻差值不超过 ⌈|a[j]-a[i]| / (j-i)⌉。
- 整体不平整指数即为所有保留段中的最大值。
采用记忆化搜索：
- 定义 dp[i][k] 表示从位置 i 开始，还需选择 k 个保留点（包括 i）时，后续所能达到的最小最大步长。
- 枚举下一个保留点 j（满足 j ≥ i + k - 1），计算当前段的步长 cost = ceil(|a[j]-a[i]| / (j-i))，递归求解 dp[j][k-1]，取两者最大值作为候选。
- 边界：k == 1 时，无需再选，返回 0。
最终答案为所有起始点中 dp[i][k] 的最小值。
#include <iostream>
#include <vector>
#include <climits>
#include <cstring>
#include <cmath>
using namespace std;
const int MAXN = 1010;
int n, m;
vector<long long> a;
int keep;
int memo[MAXN][MAXN];
int dfs(int pos, int remain) {
if (remain == 1) return 0;
if (memo[pos][remain] != -1) return memo[pos][remain];
int res = INT_MAX;
for (int nxt = pos + 1; nxt + remain - 2 < n; ++nxt) {
int gap = nxt - pos;
int diff = abs(a[nxt] - a[pos]);
int cost = (diff + gap - 1) / gap; // ceil(diff / gap)
res = min(res, max(cost, dfs(nxt, remain - 1)));
}
return memo[pos][remain] = res;
}
int main() {
cin >> n >> m;
a.resize(n);
for (int i = 0; i < n; ++i) cin >> a[i];
keep = n - m;
if (keep == 1) {
cout << 0 << endl;
return 0;
}
memset(memo, -1, sizeof(memo));
int ans = INT_MAX;
for (int i = 0; i + keep - 1 < n; ++i) {
ans = min(ans, dfs(i, keep));
}
cout << ans << endl;
return 0;
}
