CSP-J 复赛
2019T1-P5660数字游戏¶
提示1-到底要算什么
我先只看输出：要求的是 1 的个数，还是这个二进制数的大小？试着手算 00100001。
提示2-特殊条件能省掉什么
全 0 的 20% 数据，答案直接为 0；但只有 8 个字符，逐个计数已经很简单。这种特殊条件值得看懂，不需要重复写代码。
提示3-直接逐个看
字符串固定只有 8 位，逐个字符判断就够了。全 0 的性质覆盖 20% 数据，但同一种计数方法已经能处理全部数据，不必另写一版。
代码-满分
遇到字符 1 就计数。时间 \(O(|s|)\)，额外空间 \(O(1)\)。
2019T2-P5661公交换乘¶
提示1-先还原一张票的变化
我先给每张地铁优惠票记价格、时间和是否使用。公交到来时，应该怎样排除过期票，并找到最早的一张可用票？
提示2-特殊条件能省掉什么
所有票价相等的两组数据各占 15%，合计 30 分。此时价格判断消失，最早的有效票一定能用，我只需维护一个按时间排列的队列。小规模的 30% 数据也可扫描所有旧票；一般数据则利用 45 分钟窗口。
提示3-看似枚举，其实很短
30% 数据的 \(n\le1000\) 可以直接模拟。全部数据 \(n\le10^5\)，但时间是严格递增的整数：包含当前时刻在内的 45 分钟窗口最多只有 46 个记录，所以检查有效票不会退化成 \(O(n^2)\)。价格全相同的两组性质还能简化查找。
提示4-两个指针与使用标记
我按获得顺序存票，head 跳过过期票，tail 指向下一张票的位置。公交按顺序查找价格够且未使用的票，成功就标记，否则付款。差恰好 45 分钟仍有效；公交本身不产生优惠票。
代码-30分
仅适用于所有票价相等的两组特殊数据，共 30 分。时间 \(O(n)\)，空间 \(O(n)\)。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
queue<int> tickets;
long long answer = 0;
for (int i = 0; i < n; i++) {
int type, price, t;
cin >> type >> price >> t;
while (!tickets.empty() && t - tickets.front() > 45) tickets.pop();
if (type == 0) {
answer += price;
tickets.push(t);
} else if (!tickets.empty()) {
// 我看到票价相等，就不再逐张比较价格。
tickets.pop();
} else {
answer += price;
}
}
cout << answer;
return 0;
}
代码-满分
时间 \(O(46n)\)，空间 \(O(n)\)。总费用最多 \(10^8\)，这里用 long long 保存答案。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int price[N], timeUsed[N];
bool used[N];
int main() {
int n;
cin >> n;
int head = 0, tail = 0;
long long answer = 0;
for (int i = 0; i < n; i++) {
int type, p, t;
cin >> type >> p >> t;
if (type == 0) {
answer += p;
price[tail] = p;
timeUsed[tail] = t;
tail++;
} else {
while (head < tail && t - timeUsed[head] > 45) head++;
bool freeRide = false;
// 我按获得时间查找，找到第一张可用票就停止。
for (int j = head; j < tail; j++) {
if (!used[j] && price[j] >= p) {
used[j] = true;
freeRide = true;
break;
}
}
if (!freeRide) answer += p;
}
}
cout << answer;
return 0;
}
2019T3-P5662纪念品¶
提示1-先把天数缩小
我先试 \(T=1\)：当天买卖价格相同，能增加金币吗？这一性质对应 10 分。再只看今天和明天，研究一笔交易的收益。
提示2-特殊条件能省掉什么
除了 \(T=1\) 的 10 分，还有 \(N=1\) 的另 15 分：只有一种商品，明天涨价就尽量买，降价或不变就持币，不再需要背包。\(T=2\) 的另 15 分则只剩一次完全背包。别把这两种性质混成同一个条件。
提示3-为什么可以逐天处理
\(T,N\le100\)，任意时刻金币不超过 \(10^4\)。把持有物在每天先卖掉，再按同价买回，不会损失，因此可以把多天拆成相邻两天的选择。一天能换回的钱越多，之后的选择也不会更少。
提示4-钱就是背包容量
设 profit[c] 为今天最多花 c 枚金币买入、明天卖出能得到的最大额外收益。纪念品的费用是今日价格，收益是明日价格减今日价格；可以重复买，所以容量正序转移：profit[c] 取它与 profit[c−cost]+gain 的较大值。
提示5-检查不交易与剩余钱
我只考虑价格上涨的品种；不交易、未花完的钱都应保留。每天 money 增加 profit[money]，数组要覆盖题目保证的金币上限，而不是只覆盖最初的 \(M\le1000\)。
代码-10分
仅适用于 \(T=1\)，对应 10% 子任务；其他天数不作正确性保证。
代码-15分
仅适用于 \(N=1\) 的另 15% 数据。时间 \(O(T)\)，空间 \(O(T)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int price[N];
int main() {
int days, n, money;
cin >> days >> n >> money;
for (int i = 1; i <= days; i++) cin >> price[i];
for (int i = 1; i < days; i++) {
// 我只在明天涨价时买入，卖出后再考虑下一天。
if (price[i + 1] > price[i]) {
money += money / price[i] * (price[i + 1] - price[i]);
}
}
cout << money;
return 0;
}
代码-满分
时间 \(O(TN C)\)，其中 \(C\le10^4\) 是每天的金币数上限；空间 \(O(TN+C)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
const int M = 1e4 + 10;
int price[N][N], profit[M];
int main() {
int days, n, money;
cin >> days >> n >> money;
for (int day = 1; day <= days; day++) {
for (int i = 1; i <= n; i++) cin >> price[day][i];
}
for (int day = 1; day < days; day++) {
memset(profit, 0, sizeof profit);
for (int i = 1; i <= n; i++) {
int cost = price[day][i];
int gain = price[day + 1][i] - cost;
if (gain <= 0) continue;
// 同一种可以买多件，我让容量正序更新。
for (int cash = cost; cash <= money; cash++) {
profit[cash] = max(profit[cash], profit[cash - cost] + gain);
}
}
money += profit[money];
}
cout << money;
return 0;
}
2019T4-P5663加工零件¶
提示1-从一两个阶段画图
我先做 \(L=1\)，再画 \(L=2\) 的依赖。原材料需求相当于从工单工人出发走恰好 L 条边，最后能不能到 1 号工人？重复经过工人是允许的。
提示2-特殊条件能省掉什么
\(L=1\) 的 20 分是查邻接关系。前 16 个测试点还满足 \(n,m,L\le1000\)，共 80 分：设 can[t][u] 表示恰好走 t 步能到 u，每层沿边转移，预处理后直接回答。这是按步数的可达性 DP，不是普通最短路；大 \(L\) 才迫使我继续找奇偶规律。
提示3-长度很大，不能按层展开
前四个测试点 \(L=1\)，对应 20 分。前 16 个点的规模较小；全部数据 \(n,m,q\le10^5\)、\(L\le10^9\)，不能为每个长度逐层递推。来回走一条无向边，会增加多少步？
提示4-分别找奇数步和偶数步
我设 dist[u][p] 为从 1 到 u、步数奇偶为 p 的最短长度。每走一条边，奇偶翻转；在两个状态的图上 BFS。距离不超过 L 且奇偶相同，就能通过来回走补上剩余偶数步。
提示5-零步可达有一个例外
1 号点若没有任何边，只能走零步，不能凭空补成两步。查询的 L 是正数，所以此时全部回答 No；其他不可达状态也必须保持为无穷大。
代码-20分
仅适用于 \(L=1\)，对应测试点 1—4。每次检查工单工人是否与 1 号工人相邻。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
vector<int> h[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, q;
cin >> n >> m >> q;
while (m--) {
int u, v;
cin >> u >> v;
h[u].push_back(v);
h[v].push_back(u);
}
while (q--) {
int a, length;
cin >> a >> length;
bool found = false;
for (int v : h[a]) {
if (v == 1) found = true;
}
// 这一版只处理 length=1，需要直接相邻。
cout << (found ? "Yes" : "No");
if (q) cout << '\n';
}
return 0;
}
代码-80分
适用于 \(n,m,L\le1000\)，覆盖测试点 1—16，共 80 分。时间 \(O(Lm+q)\)，空间 \(O(Ln+m)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
vector<int> h[N];
bool can[N][N];
int main() {
int n, m, q;
cin >> n >> m >> q;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
h[u].push_back(v);
h[v].push_back(u);
}
vector<pair<int, int>> queries(q);
int steps = 0;
for (auto &query : queries) {
cin >> query.first >> query.second;
steps = max(steps, query.second);
}
can[0][1] = true;
for (int t = 1; t <= steps; t++) {
for (int u = 1; u <= n; u++) {
if (!can[t - 1][u]) continue;
// 我保留恰好 t 步的状态，不能用“至多 t 步”代替。
for (int v : h[u]) can[t][v] = true;
}
}
for (int i = 0; i < q; i++) {
if (i) cout << '\n';
cout << (can[queries[i].second][queries[i].first] ? "Yes" : "No");
}
return 0;
}
代码-满分
时间 \(O(n+m+q)\)，空间 \(O(n+m)\)。BFS 使用队列，无递归深度问题。
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
vector<int> h[N];
int dist[N][2];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, q;
cin >> n >> m >> q;
while (m--) {
int u, v;
cin >> u >> v;
h[u].push_back(v);
h[v].push_back(u);
}
memset(dist, 0x3f, sizeof dist);
queue<PII> que;
dist[1][0] = 0;
que.push({1, 0});
while (!que.empty()) {
PII now = que.front();
que.pop();
int u = now.first, parity = now.second;
for (int v : h[u]) {
int next = parity ^ 1;
if (dist[v][next] == INF) {
dist[v][next] = dist[u][parity] + 1;
que.push({v, next});
}
}
}
while (q--) {
int a, length;
cin >> a >> length;
// 1 号点没有边时，零步可达不能扩展成正数步。
bool ok = !h[1].empty() && dist[a][length % 2] <= length;
cout << (ok ? "Yes" : "No");
if (q) cout << '\n';
}
return 0;
}
2020T1-P7071优秀的拆分¶
提示1-先试着拆几个小数
我先试 6、10、7。拆出的数必须互不相同，而且不能使用 1，这与普通的任意正整数拆分有什么不同？
提示2-特殊条件能省掉什么
另有 20% 数据保证 n 为奇数，直接输出 −1；另有 20% 保证 n 是 2 的正整数次幂，直接输出 n。\(n\le10\) 的 20% 可以手列 2、4、8 的组合。它们能帮助发现规律，最后的二进制算法已同样简短。
提示3-把要求放到二进制里看
\(n\le10^7\)，二进制位数很少。每个为 1 的位对应一个不同的 2 的幂；奇数一定需要最低位的 1，因此无解。小数、奇数、单个 2 的幂这些性质，都可以用同一算法处理。
提示4-顺序与边界
我从高位到低位输出为 1 的位，保证从大到小。检查 n=1、n=2 和 n=10；注意 2 的零次幂不允许输出。
代码-满分
时间 \(O(\log n)\)，额外空间 \(O(1)\)。
2020T2-P7072直播获奖¶
提示1-先确定排名的位置
我先把当前成绩排好。计划获奖人数应该如何计算？同分人数变多，会改变要找的那个排名吗？
提示2-特殊条件能省掉什么
这题没有额外的输入性质，关键是两个不同范围：人数逐渐变多，而分数始终只有 0—600。小人数让我先用排序，大人数加小值域让我换成计数。
提示3-排序的对象能不能缩小
前十个点 \(n\le2000\)，对应 50 分，重新排序可以作为起步。全部数据 \(n\le10^5\)，成绩却只有 0—600；我想到只保存每个分数出现的人数。
提示4-从高分累计人数
第 i 人公布后，要找第 max(1,i*w/100) 名。自 600 向下累计人数，第一次达到这个名次的分数就是分数线。同分自动一起获奖；用整数计算名额，避免浮点误差，别漏掉 0 分。
代码-50分
适用于 \(n\le2000\)，对应测试点 1—10。时间 \(O(n^2\log n)\)，空间 \(O(n)\)；不承诺旧笔记中的 65 分。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, w;
cin >> n >> w;
vector<int> values;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
values.push_back(x);
sort(values.rbegin(), values.rend());
int rank = max(1, i * w / 100);
if (i > 1) cout << ' ';
cout << values[rank - 1];
}
return 0;
}
代码-满分
时间 \(O(601n)\)，额外空间 \(O(601)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 610;
int countScore[N];
int main() {
int n, w;
cin >> n >> w;
for (int i = 1; i <= n; i++) {
int score;
cin >> score;
countScore[score]++;
int rank = max(1, i * w / 100);
int total = 0;
for (int value = 600; value >= 0; value--) {
total += countScore[value];
if (total >= rank) {
if (i > 1) cout << ' ';
cout << value;
break;
}
}
}
return 0;
}
2020T3-P7073表达式¶
提示1-先让一次询问正确
我先用栈还原后缀表达式，试着取反一个变量，再重新求值。每次修改是临时的，所以回答完要恢复。
提示2-特殊条件能省掉什么
仅含 & 或仅含 | 的 20% 数据，可以变成计数题：与表达式只需数 0，或表达式只需数 1；取反一次，就临时调整这个数量。另 20% 的初值全相同，混合运算依然可能存在，不能只数 0 或 1 来处理。
提示3-什么时候重算会太慢
30% 子任务满足 \(|s|,n,q\le1000\)，重算可行。全部数据 \(|s|\le10^6\)、\(q\le10^5\)，不能每次扫完整个表达式。仅含与或仅含或的 20% 性质提示我：某些兄弟子树已经能决定父节点的值。
提示4-变化能否传到根
我先求出所有子表达式的值，再标记 active[u]：取反节点 u 的结果是否会改变整棵树的值。根为真；非运算一定传递变化；与运算只有兄弟为 1 时才传递，或运算只有兄弟为 0 时才传递。每个变量恰好出现一次，保证只有一条向根的路径。
提示5-不用深递归
建树时儿子编号小于父亲，正序求值、倒序传播 active，就不怕长链导致栈溢出。查询输出原根值与 active[变量叶子] 的异或。全 0、全 1 的性质也由此处理。
代码-20分
仅适用于表达式只含 & 或只含 | 的 20% 数据。时间 \(O(|s|+n+q)\)，空间 \(O(n+|s|)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int value[N];
int main() {
string s;
getline(cin, s);
bool useAnd = s.find('&') != string::npos;
int n, ones = 0;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> value[i];
ones += value[i];
}
int q;
cin >> q;
for (int i = 0; i < q; i++) {
int x;
cin >> x;
// 我只临时改变 1 的数量，各次询问互不影响。
int count = ones + (value[x] == 0 ? 1 : -1);
int answer = useAnd ? (count == n) : (count > 0);
if (i) cout << '\n';
cout << answer;
}
return 0;
}
代码-30分
适用于 \(|s|,n,q\le1000\)，对应 30% 子任务。每次重算并恢复，时间 \(O(|s|+q(|s|+n))\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
const int M = 1e5 + 10;
int leftChild[N], rightChild[N], value[N], leaf[M];
char op[N];
bool active[N];
int nodes;
void calculate() {
// 儿子先建、父亲后建，按编号正序就能先算子表达式。
for (int u = 1; u <= nodes; u++) {
if (op[u] == '!') value[u] = !value[leftChild[u]];
if (op[u] == '&') value[u] = value[leftChild[u]] & value[rightChild[u]];
if (op[u] == '|') value[u] = value[leftChild[u]] | value[rightChild[u]];
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string expression;
getline(cin, expression);
istringstream input(expression);
stack<int> st;
string token;
while (input >> token) {
nodes++;
int u = nodes;
if (token[0] == 'x') {
int id = stoi(token.substr(1));
leaf[id] = u;
op[u] = 'x';
} else {
op[u] = token[0];
int last = st.top();
st.pop();
if (op[u] == '!') leftChild[u] = last;
else {
rightChild[u] = last;
leftChild[u] = st.top();
st.pop();
}
}
st.push(u);
}
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> value[leaf[i]];
int root = st.top();
int q;
cin >> q;
while (q--) {
int id;
cin >> id;
value[leaf[id]] ^= 1;
calculate();
cout << value[root];
if (q) cout << '\n';
// 我恢复原值，因为各次询问互不影响。
value[leaf[id]] ^= 1;
}
return 0;
}
代码-满分
建树、求值和传播合计 \(O(|s|+n)\)，每次询问 \(O(1)\)；总时间 \(O(|s|+n+q)\)，空间 \(O(|s|+n)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
const int M = 1e5 + 10;
int leftChild[N], rightChild[N], value[N], leaf[M];
char op[N];
bool active[N];
int nodes;
void calculate() {
// 儿子先建、父亲后建，按编号正序就能先算子表达式。
for (int u = 1; u <= nodes; u++) {
if (op[u] == '!') value[u] = !value[leftChild[u]];
if (op[u] == '&') value[u] = value[leftChild[u]] & value[rightChild[u]];
if (op[u] == '|') value[u] = value[leftChild[u]] | value[rightChild[u]];
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string expression;
getline(cin, expression);
istringstream input(expression);
stack<int> st;
string token;
while (input >> token) {
nodes++;
int u = nodes;
if (token[0] == 'x') {
int id = stoi(token.substr(1));
leaf[id] = u;
op[u] = 'x';
} else {
op[u] = token[0];
int last = st.top();
st.pop();
if (op[u] == '!') leftChild[u] = last;
else {
rightChild[u] = last;
leftChild[u] = st.top();
st.pop();
}
}
st.push(u);
}
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> value[leaf[i]];
int root = st.top();
calculate();
active[root] = true;
for (int u = nodes; u >= 1; u--) {
if (!active[u]) continue;
if (op[u] == '!') active[leftChild[u]] = true;
if (op[u] == '&') {
active[leftChild[u]] = (value[rightChild[u]] == 1);
active[rightChild[u]] = (value[leftChild[u]] == 1);
}
if (op[u] == '|') {
active[leftChild[u]] = (value[rightChild[u]] == 0);
active[rightChild[u]] = (value[leftChild[u]] == 0);
}
}
int q;
cin >> q;
while (q--) {
int id;
cin >> id;
cout << (value[root] ^ active[leaf[id]]);
if (q) cout << '\n';
}
return 0;
}
2020T4-P7074方格取数¶
提示1-为什么直接搜索会重复
我先想每条合法路径，注意不能走回访问过的格子。再看移动方向：只能向右，不能向左，离开一列后还能回来吗？
提示2-特殊条件能省掉什么
这里没有额外的测试点性质，只有规模变化。\(n,m\le5\) 的 20% 数据，可以回溯枚举不重复经过格子的路径，先保证起点和终点处理正确；大数据再利用“不能向左”这个所有输入都有的性质，逐列 DP。
提示3-一列里能怎样移动
\(n,m\le1000\)，全路径枚举不可行；\(n,m\le5\) 的 20% 小数据适合检查暴力，但不必把它当主要解法。在同一列里，一旦向下走后再向上，就会重复经过，所以这一列只能保持一个竖直方向。
提示4-定义两个方向的状态
best[i] 表示上一列结束在第 i 行的最大和。down[i] 表示当前列向下走到第 i 行的最大和，来自左边 best[i] 或上方 down[i−1]，再加当前格子；up[i] 对称地来自左边或下方。两次扫描结束后才令 best[i]=max(down[i],up[i])。
提示5-负数与大答案
第一列只有第 1 行能从起点进入，其余初始状态不可达。格子绝对值最多 \(10^4\)，路径和可能超过 int，所以我使用 long long 和足够小的负数。检查全负、一行、一列。
代码-20分
适用于 \(n,m\le5\) 的 20% 数据。枚举不重复格子的合法路径。每列只有一个竖直方向，至多选择 n 个离开位置，时间粗略上界 \(O(mn^{m+1})\)，空间 \(O(nm)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 10;
const int dx[3] = {-1, 1, 0};
const int dy[3] = {0, 0, 1};
const long long NEG = -(1LL << 60);
int n, m, a[N][N];
bool used[N][N];
long long answer = NEG;
void dfs(int x, int y, long long sum) {
if (x == n && y == m) {
answer = max(answer, sum);
return;
}
for (int d = 0; d < 3; d++) {
int nx = x + dx[d], ny = y + dy[d];
if (nx < 1 || nx > n || ny < 1 || ny > m || used[nx][ny]) continue;
// 我在返回时撤销标记，让下一条候选路径仍能使用这个格子。
used[nx][ny] = true;
dfs(nx, ny, sum + a[nx][ny]);
used[nx][ny] = false;
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) cin >> a[i][j];
}
used[1][1] = true;
dfs(1, 1, a[1][1]);
cout << answer;
return 0;
}
代码-满分
时间 \(O(nm)\)，空间 \(O(nm+n)\)。没有递归，也不会把不同方向的本列状态错误地混用。
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
const long long NEG = -(1LL << 60);
int a[N][N];
long long best[N], down[N], up[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) cin >> a[i][j];
}
fill(best, best + N, NEG);
best[1] = 0;
for (int j = 1; j <= m; j++) {
down[0] = up[n + 1] = NEG;
for (int i = 1; i <= n; i++) {
down[i] = max(best[i], down[i - 1]) + a[i][j];
}
for (int i = n; i >= 1; i--) {
up[i] = max(best[i], up[i + 1]) + a[i][j];
}
// 两个方向都算完后，才更新上一列答案。
for (int i = 1; i <= n; i++) best[i] = max(down[i], up[i]);
}
cout << best[n];
return 0;
}
2021T1-P7909分糖果¶
提示1-把奖励和总所得分清
我先只关心分完后篮子剩下多少，不把平均分到的那份算进奖励。选 k 颗糖果，奖励是否就是 k 除以 n 的余数？
提示2-特殊条件能省掉什么
测试点 5 的 \(R-L=0\)，选法只有一种，直接算 L%n。测试点 1—7 都有 \(R-L\le10^5\)，共 70 分，即使 L、R 接近 \(10^9\)，枚举区间仍然不大。这里真正影响暴力次数的是区间长度，不是端点大小。
提示3-区间很大但余数会重复
\(R\le10^9\)，不能遍历整个区间；区间很短和 L=R 的测试点可以枚举，但完整解法也不复杂。写出一段连续数的余数，观察什么时候回到 0。
提示4-只看有没有跨过一个整倍数
如果 L/n 与 R/n 相同，余数在区间内递增，答案是 R%n；不同则跨过了一个倍数，它前面的数在区间内，余数为 n−1。检查 L=R、跨界和端点恰好是倍数。
代码-70分
适用于 \(R-L\le10^5\)，覆盖测试点 1—7，共 70 分。时间 \(O(R-L+1)\)，空间 \(O(1)\)。
代码-满分
时间、额外空间均为 \(O(1)\)。
2021T2-P7910插入排序¶
提示1-相等的元素还要分先后
我先把每个数与原位置绑在一起。插入排序只在严格小于时交换，所以相同数保留原顺序，相当于按 (值,原编号) 排序。
提示2-特殊条件能省掉什么
测试点 1—13 的 \(n,Q\le1500\)，共 52 分。询问时扫描原数组，统计比目标小的元素，并把同值且编号更小的元素算在前面，就能得到名次，连排序也不用。互不相同的性质只是去掉同值比较；“修改至多 5000 次”则决定满分方案把耗时放在哪里。
提示3-数据提醒我优化哪一种操作
\(n\le8000\)、\(Q\le2\times10^5\)，但修改最多 5000 次。我可以让查询 \(O(1)\)，把工作放到修改上；小数据可每次排序，互不相同的性质能省去同值处理，但一般情况必须保留编号。
提示4-一个数变了，谁的名次会变
rankPos[i] 保存原位置 i 的元素当前名次。修改 x 后，对于每个其他元素，先减掉“旧 x 比它小”带来的那一名，再加上“新 x 比它小”带来的那一名；新 x 的名次则是比它小的元素数加一。
提示5-检查稳定性与不动的修改
我用一串相等的值测试编号比较，再测试把值改成原值，以及移动到最前、最后。始终维护原数组，不要把排序后的下标当成询问下标。
代码-52分
适用于 \(n,Q\le1500\)，覆盖测试点 1—13，共 52 分。时间 \(O(nQ+n)\)，空间 \(O(n)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 1510;
int a[N];
int main() {
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
bool first = true;
while (q--) {
int type, x;
cin >> type >> x;
if (type == 1) {
cin >> a[x];
} else {
int rank = 1;
for (int i = 1; i <= n; i++) {
// 我把同值且更早出现的元素也排在目标之前。
if (a[i] < a[x] || (a[i] == a[x] && i < x)) rank++;
}
if (!first) cout << '\n';
cout << rank;
first = false;
}
}
return 0;
}
代码-满分
初始化 \(O(n\log n)\)，每次修改 \(O(n)\)，查询 \(O(1)\)；总时间 \(O(n\log n+Un+Q)\)，\(U\le5000\)，空间 \(O(n)\)。
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 8010;
int a[N], rankPos[N];
PII sorted[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> a[i];
sorted[i] = {a[i], i};
}
sort(sorted + 1, sorted + n + 1);
for (int i = 1; i <= n; i++) rankPos[sorted[i].second] = i;
bool first = true;
while (q--) {
int type, x;
cin >> type >> x;
if (type == 1) {
int v;
cin >> v;
PII before = {a[x], x}, after = {v, x};
int position = 1;
for (int i = 1; i <= n; i++) {
if (i == x) continue;
PII item = {a[i], i};
// 我只调整被修改元素越过的那些元素。
if (before < item) rankPos[i]--;
if (after < item) rankPos[i]++;
if (item < after) position++;
}
a[x] = v;
rankPos[x] = position;
} else {
if (!first) cout << '\n';
cout << rankPos[x];
first = false;
}
}
return 0;
}
2021T3-P7911网络连接¶
提示1-先拆成两件事
我先判断地址是否合规，再处理连接；非法地址的操作直接忽略，不能留下服务器记录。拿 192.168.00.1:80 与 192.168.0.1:80 比较。
提示2-特殊条件能省掉什么
性质 1 保证地址全部合法，覆盖测试点 1—11，共 55 分，题目先变成字符串查找与登记。性质 2 去掉同类重复，性质 3 让服务器全部在客户之前；性质 4 只省去格式和前导零检查，仍要检查数值上限；性质 5 也没有保证地址合法。
提示3-小数据也需要完整规则
\(n\le1000\)、地址长度不超过 25，逐字符检查很轻松。性质 1 省去格式判断，性质 2 省去同类重复，性质 3 让服务器先出现；一般数据不能依赖它们。
提示4-一段一段读，及时拒绝错误
依次读五个非空数字段，分隔符应为三个点和一个冒号。前四段至多 255，最后至多 65535；除单独的 0 外不能有前导零。我读到越界就拒绝，避免很长的数字溢出，最后确认整串都读完。
提示5-只保存成功的服务器
用 map 保存地址到成功服务器编号。合法服务器重复则 FAIL；合法客户端找到已有服务器就输出编号，否则 FAIL。检查客户端早于服务器、重复服务器和末尾多余字符。
代码-55分
仅适用于性质 1，覆盖测试点 1—11，共 55 分。时间 \(O(n\log n)\) 次字符串比较，空间 \(O(n)\)；地址长度至多 25。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
map<string, int> server;
for (int i = 1; i <= n; i++) {
string type, address;
cin >> type >> address;
if (i > 1) cout << '\n';
// 我利用地址保证合法的条件，只处理登记和查找。
if (type == "Server") {
if (server.count(address)) cout << "FAIL";
else {
server[address] = i;
cout << "OK";
}
} else {
if (server.count(address)) cout << server[address];
else cout << "FAIL";
}
}
return 0;
}
代码-满分
设最大地址长度为 L，时间 \(O(nL\log n)\)，空间 \(O(nL)\)。
#include <bits/stdc++.h>
using namespace std;
bool valid(const string &s) {
int pos = 0;
for (int part = 0; part < 5; part++) {
if (pos == int(s.size()) || s[pos] < '0' || s[pos] > '9') return false;
int begin = pos, value = 0;
int limit = (part == 4 ? 65535 : 255);
while (pos < int(s.size()) && '0' <= s[pos] && s[pos] <= '9') {
value = value * 10 + s[pos] - '0';
// 我及时拒绝越界值，避免长数字继续累乘而溢出。
if (value > limit) return false;
pos++;
}
if (pos - begin > 1 && s[begin] == '0') return false;
if (part < 4) {
char separator = (part == 3 ? ':' : '.');
if (pos == int(s.size()) || s[pos] != separator) return false;
pos++;
}
}
return pos == int(s.size());
}
int main() {
int n;
cin >> n;
map<string, int> server;
for (int id = 1; id <= n; id++) {
string type, address;
cin >> type >> address;
if (id > 1) cout << '\n';
if (!valid(address)) cout << "ERR";
else if (type == "Server") {
if (server.count(address)) cout << "FAIL";
else {
server[address] = id;
cout << "OK";
}
} else {
if (server.count(address)) cout << server[address];
else cout << "FAIL";
}
}
return 0;
}
2021T4-P7912小熊的果篮¶
提示1-一轮结束后再看新块
我先画 1 1 0 1 1：每个旧块拿一个，拿完后相同类型才合并。如果删着删着立刻对新块再拿一次，会不会多拿？
提示2-特殊条件能省掉什么
没有额外特殊性质，但 \(n\le1000\) 的 30% 允许每轮扫描剩余水果，把各段首个水果取出，再保存未取出的水果。最坏每轮只取一个，约 \(O(n^2)\)；这个版本先把“本轮一起取”做正确，再考虑减少重复扫描。
提示3-瓶颈是反复扫描
\(n\le2\times10^5\)。每轮扫全部剩余水果，在全同类时会退化成 \(O(n^2)\)；\(n\le1000\) 的 30% 子任务适合这种起步做法，但大数据要只处理块首。
提示4-链表加块首列表
leftPos、rightPos 保存还存在的相邻水果。heads 按从左到右保存本轮块首。删除块首 u 后，只要右邻仍是 u 的类型、且与左邻不同，它就是下一轮的新块首。列表只保留仍需处理的位置。
提示5-为什么可以边删边整理下一轮
我仍按本轮固定列表从左到右删除，右侧尚未删除的旧块首会阻隔提前合并；因此不会漏删本轮水果。每次处理必删掉一个水果，合计 O(n) 次。检查全同类、交替、一个水果，以及删除中间单元素块后合并。
代码-30分
适用于 \(n\le1000\) 的 30% 数据。时间 \(O(n^2)\)，空间 \(O(n)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int type[N];
int main() {
int n;
cin >> n;
vector<int> remaining;
for (int i = 1; i <= n; i++) {
cin >> type[i];
remaining.push_back(i);
}
bool firstRound = true;
while (!remaining.empty()) {
vector<int> next;
int lastType = -1;
bool firstFruit = true;
if (!firstRound) cout << '\n';
for (int id : remaining) {
// 我按本轮开始时的分段取首个，合并留给下一轮。
if (type[id] != lastType) {
if (!firstFruit) cout << ' ';
cout << id;
firstFruit = false;
} else {
next.push_back(id);
}
lastType = type[id];
}
remaining = next;
firstRound = false;
}
return 0;
}
代码-满分
时间、空间均为 \(O(n)\)。两端用类型 −1 的哨兵，防止边界被误认成真实水果。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int type[N], leftPos[N], rightPos[N], heads[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
type[0] = type[n + 1] = -1;
rightPos[0] = 1;
leftPos[n + 1] = n;
int blocks = 0;
for (int i = 1; i <= n; i++) {
cin >> type[i];
leftPos[i] = i - 1;
rightPos[i] = i + 1;
if (type[i] != type[i - 1]) heads[blocks++] = i;
}
bool firstRound = true;
while (blocks > 0) {
if (!firstRound) cout << '\n';
firstRound = false;
int nextBlocks = 0;
for (int i = 0; i < blocks; i++) {
int u = heads[i];
if (i) cout << ' ';
cout << u;
int l = leftPos[u], r = rightPos[u];
rightPos[l] = r;
leftPos[r] = l;
// 我从左往右删块首，右侧尚未删除的块首会阻隔合并。
if (type[r] == type[u] && type[r] != type[l]) {
heads[nextBlocks++] = r;
}
}
blocks = nextBlocks;
}
return 0;
}
2022T1-P8813乘方¶
提示1-不一定要算出巨大整数
我先看输出要求：一旦结果超过 \(10^9\)，只需要输出 −1。能不能在继续乘之前就知道下一步会超限？
提示2-特殊条件能省掉什么
\(b=1\) 的 10% 直接输出 a，\(b\le2\) 的 30% 最多乘两次。\(b\le30\) 且结果不超过 \(10^{18}\) 的 60% 可用 long long 直接循环乘；一般 b 很大时，先处理 a=1，再利用超过上限就停，让循环仍然很短。
提示3-指数很大，循环为何仍可行
\(a,b\le10^9\)，但 a≥2 时最多乘约 30 次就会超限。a=1 是例外，要直接返回；b=1、b≤2 等子任务也由这一方法覆盖。
提示4-先除后乘避免溢出
当 answer>LIMIT/a 时，下一次乘法必超限，立即停止，否则安全相乘。检查 \(10^9\) 恰好不超限、2 的 29/30 次方和 a=1。
代码-满分
a≥2 时最多做 \(O(\log_a 10^9)\) 次乘法，额外空间 \(O(1)\)；a=1 直接返回。
#include <bits/stdc++.h>
using namespace std;
const long long LIMIT = 1e9;
int main() {
long long a, b;
cin >> a >> b;
if (a == 1) {
cout << 1;
return 0;
}
long long answer = 1;
while (b--) {
// 我在乘法前检查，既能提前停止，也避免先溢出再判断。
if (answer > LIMIT / a) {
cout << -1;
return 0;
}
answer *= a;
}
cout << answer;
return 0;
}
2022T2-P8814解密¶
提示1-先展开关系再枚举
我先展开 ed=(p−1)(q−1)+1，结合 pq=n，试着把未知量缩成一个。你能得到 p+q 吗？注意输入顺序是 n、d、e。
提示2-特殊条件能省掉什么
我同时看两个性质：测试点 1—4 的 \(m=p+q\le60000\)、询问数至多 1000，共 40 分，可以枚举较小的 p 并检查 p(m−p)=n。测试点 7 的 10 分保证若有解则 p=q，于是候选只剩 m/2；保证有解的其他点并不代表答案可以随意输出。
提示3-范围允许二分
令 sum=n−ed+2，题目保证 \(1\le sum\le10^9\)。取较小的 p，则 \(1\le p\le sum/2\)、q=sum−p，乘积 p(sum−p) 在这段递增；可二分寻找等于 n 的位置。小 n 可枚举，p=q 的性质可直接检查，但同一二分已经覆盖全部数据。
提示4-大整数与无解
\(n,ed\le10^{18}\)、询问至多 \(10^5\)，使用 long long。候选乘积至多 sum²/4，不会溢出；sum=1 时搜索区间为空，直接无解。输出 p≤q，不能只判断有近似实根。
代码-10分
仅适用于测试点 7“若有解则 p=q”，共 10 分。时间 \(O(k)\)，空间 \(O(1)\)。
#include <bits/stdc++.h>
using namespace std;
int main() {
int tests;
cin >> tests;
for (int i = 0; i < tests; i++) {
long long n, e, d;
cin >> n >> e >> d;
long long sum = n - e * d + 2;
long long p = sum / 2;
if (i) cout << '\n';
// 我检查唯一候选，性质并没有保证一定有解。
if (sum % 2 == 0 && p >= 1 && p * p == n) cout << p << ' ' << p;
else cout << "NO";
}
return 0;
}
代码-40分
适用于 \(m=n-ed+2\le60000\)、询问数至多 1000，覆盖测试点 1—4，共 40 分。时间 \(O(km)\)，空间 \(O(1)\)。
#include <bits/stdc++.h>
using namespace std;
int main() {
int tests;
cin >> tests;
for (int i = 0; i < tests; i++) {
long long n, e, d;
cin >> n >> e >> d;
long long sum = n - e * d + 2;
bool found = false;
if (i) cout << '\n';
// 我知道两数之和，只需枚举较小的那个数。
for (long long p = 1; p <= sum / 2; p++) {
long long q = sum - p;
if (p * q == n) {
cout << p << ' ' << q;
found = true;
break;
}
}
if (!found) cout << "NO";
}
return 0;
}
代码-满分
每次 \(O(\log sum)\)，额外空间 \(O(1)\)。用整数二分避免浮点平方根误差。
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
long long n, d, e;
cin >> n >> d >> e;
long long sum = n - d * e + 2;
long long left = 1, right = sum / 2, answer = -1;
while (left <= right) {
long long p = (left + right) / 2;
long long product = p * (sum - p);
if (product == n) {
answer = p;
break;
}
if (product < n) left = p + 1;
else right = p - 1;
}
if (answer == -1) cout << "NO";
else cout << answer << ' ' << sum - answer;
if (T) cout << '\n';
}
return 0;
}
2022T3-P8815逻辑表达式¶
提示1-先分清跳过了什么
我先比较 0&1 与 1|(0&1)。右边被外层短路跳过时，里面的短路还应该计数吗？同类运算从左到右，且 & 比 | 优先。
提示2-特殊条件能省掉什么
没有括号的性质 3 覆盖测试点 7、15—17，共 20 分：表达式可以分成由 | 连接的若干个与运算段，不需要括号栈。没有 & 或没有 | 的两种性质也能减少运算种类，但括号仍会影响短路次数，例如 1|(0|0) 和 (1|0)|0 的次数不同，不能简单数所有运算符。
提示3-不要逐次截取子串
字符串最长 \(10^6\)，深递归可能爆栈，反复找括号也可能很慢。没有 &、没有 |、没有括号的性质可以简化，但栈按优先级处理能覆盖全部情况。
提示4-每个子表达式保存三个结果
我为一个子表达式保存值、与短路次数、或短路次数。合并左右两部分时，总是保留左边的次数；如果左边已触发短路，只新增这一次，不加入右边次数；否则加入右边次数并取右边的值。
提示5-括号与左结合
读到运算符时，先处理栈顶优先级不低于它的运算；右括号则处理到左括号为止。每个符号只入栈、出栈一次。检查 1|1|0、0&1&1 和 1|(0&1)；最后一个不应统计内部的与短路。
代码-20分
仅适用于性质 3（没有括号），覆盖测试点 7、15—17，共 20 分。时间 \(O(|s|)\)，空间 \(O(|s|)\)（保存输入）。
#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
cin >> s;
int answer = 0, andCount = 0, orCount = 0;
int length = s.size();
for (int left = 0; left < length; ) {
int right = left;
while (right < length && s[right] != '|') right++;
if (left > 0 && answer == 1) {
// 我已得到真，整个右侧与运算段都不会执行。
orCount++;
} else {
int value = s[left] - '0';
for (int pos = left + 1; pos < right; pos += 2) {
if (value == 0) andCount++;
else value = s[pos + 1] - '0';
}
answer |= value;
}
left = right + 1;
}
cout << answer << '\n' << andCount << ' ' << orCount;
return 0;
}
代码-满分
时间、空间均为 \(O(|s|)\)。用栈合并结果，不需要递归执行百万长度的表达式。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int value[N];
int shortAnd[N], shortOr[N], nodes;
stack<int> numbers;
stack<char> operators;
int priority(char c) {
if (c == '&') return 2;
if (c == '|') return 1;
return 0;
}
void calculate() {
int r = numbers.top();
numbers.pop();
int l = numbers.top();
numbers.pop();
char c = operators.top();
operators.pop();
nodes++;
int u = nodes;
shortAnd[u] = shortAnd[l];
shortOr[u] = shortOr[l];
// 左边触发短路时，我不把右子树的短路次数加进来。
if (c == '&' && value[l] == 0) {
value[u] = 0;
shortAnd[u]++;
} else if (c == '|' && value[l] == 1) {
value[u] = 1;
shortOr[u]++;
} else {
value[u] = value[r];
shortAnd[u] += shortAnd[r];
shortOr[u] += shortOr[r];
}
numbers.push(u);
}
int main() {
string s;
cin >> s;
for (char c : s) {
if (c == '0' || c == '1') {
nodes++;
value[nodes] = c - '0';
numbers.push(nodes);
} else if (c == '(') operators.push(c);
else if (c == ')') {
while (operators.top() != '(') calculate();
operators.pop();
} else {
while (!operators.empty() && priority(operators.top()) >= priority(c)) {
calculate();
}
operators.push(c);
}
}
while (!operators.empty()) calculate();
int root = numbers.top();
cout << value[root] << '\n';
cout << shortAnd[root] << ' ' << shortOr[root];
return 0;
}
2022T4-P8816上升点列¶
提示1-先不添加新点
我先看测试点的特殊条件：测试点 1—2、5—10 都有 \(k=0\)，共 40 分。不添加新点后，只需在原有点中找最长点列，问题一下就简单了。
我借用 LIS 的思路：先排序，再枚举前驱。设 f[i] 表示以第 i 个点结束的最长点列，初值为 1。只有 j 能向右或向上走一步到 i，才用 f[j]+1 更新 f[i]。注意，坐标递增还不够，相邻两点的距离必须恰好为 1。
提示2-坐标大，点数却很少
\(n\le500\)、\(k\le100\)、坐标至多 \(10^9\)，不能铺整个平面。我按坐标排序，尝试枚举前驱点；两点之间需要补多少点，只与坐标差有关。
提示3-把自由点预算放进状态
dp[i][b] 表示以第 i 个原有点结束、至多补 b 个点的最长点列。若前驱 j 的两个坐标都不超过 i，曼哈顿距离为 distance，中间需要 distance−1 个自由点，转移增加 distance 个位置。初值 b+1，表示在这个点之前补点。
提示4-预算不能凭空增加
只在费用不超过 b 时转移。预算是“至多”，所以在点列末尾再补自由点的方案，也可等价挪到最前面的初始化中。距离可能接近 \(2\times10^9\)，先用 long long 计算；原点互不重合，因此费用不会是负数。
代码-40分
适用于 \(k=0\)，覆盖测试点 1—2、5—10，共 40 分。时间 \(O(n^2)\)，空间 \(O(n)\)；不适用于需要添加点的数据。
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 510;
PII a[N];
int f[N];
int main() {
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i].first >> a[i].second;
sort(a + 1, a + n + 1);
int answer = 1;
for (int i = 1; i <= n; i++) {
f[i] = 1;
for (int j = 1; j < i; j++) {
// 我只接一步就能到达的前驱，不能跨过缺失的点。
bool right = a[i].first == a[j].first + 1
&& a[i].second == a[j].second;
bool up = a[i].first == a[j].first
&& a[i].second == a[j].second + 1;
if (right || up) f[i] = max(f[i], f[j] + 1);
}
answer = max(answer, f[i]);
}
cout << answer;
return 0;
}
代码-满分
时间 \(O(n^2(k+1))\)，空间 \(O(n(k+1))\)。
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 510;
const int K = 110;
PII a[N];
int dp[N][K];
int main() {
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i].first >> a[i].second;
sort(a + 1, a + n + 1);
int answer = k + 1;
for (int i = 1; i <= n; i++) {
for (int used = 0; used <= k; used++) {
// 我把预算理解为“至多”，自由点可接在首个原有点之前。
dp[i][used] = used + 1;
for (int j = 1; j < i; j++) {
if (a[j].first > a[i].first || a[j].second > a[i].second) continue;
long long distance = 1LL * a[i].first - a[j].first
+ a[i].second - a[j].second;
if (distance - 1 > used) continue;
int cost = int(distance) - 1;
dp[i][used] = max(dp[i][used], dp[j][used - cost] + cost + 1);
}
answer = max(answer, dp[i][used]);
}
}
cout << answer;
return 0;
}
2023T1-P9748小苹果¶
提示1-先手写两轮编号
我先列 n=8 的过程。每天取的是当前第 1、4、7……个，剩余苹果会重新编号，不是固定取原编号为 1 模 3 的苹果。
提示2-特殊条件能省掉什么
测试点 1—5 的 \(n\le1000\)，共 50 分，可以真的保存苹果编号并逐天筛掉第 1、4、7……个。测试点 6—7 保证最后一个苹果第一天就被拿走，第二问直接为 1；第一问仍需计算，不能把整个题的答案都设为 1。
提示3-能不能只保存数量
\(n\le10^9\)，不能为每个苹果开数组。每轮拿走 ceil(n/3) 个，剩余数量足以确定下一轮规模；原来的最后一个若没被拿走，仍是剩余队列的最后一个。
提示4-最后一个什么时候被拿走
当前数量 n 满足 n%3=1 时，最后一个属于本轮要拿走的位置，首次出现就记录天数。检查 n=1、n=3、n=8；特殊性质“第一天拿走最后一个”也正是这个判断。
代码-50分
适用于 \(n\le1000\)，覆盖测试点 1—5，共 50 分。时间 \(O(n)\)：每轮剩余数量约缩为原来的三分之二；空间 \(O(n)\)。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> apples;
for (int i = 1; i <= n; i++) apples.push_back(i);
int days = 0, lastDay = 0;
while (!apples.empty()) {
days++;
vector<int> remaining;
for (int i = 0; i < int(apples.size()); i++) {
// 我按今天的新编号筛选，但保留原编号来认出最后一个。
if (i % 3 == 0) {
if (apples[i] == n) lastDay = days;
} else {
remaining.push_back(apples[i]);
}
}
apples = remaining;
}
cout << days << ' ' << lastDay;
return 0;
}
代码-满分
数量每轮约乘 2/3，时间 \(O(\log n)\)，额外空间 \(O(1)\)。
2023T2-P9749公路¶
提示1-先想下一段的油从哪里来
我先只看走到下一站还缺多少油。油箱不限，先前更便宜的站点可以提前买，所以不应只看当前站的价格。
提示2-特殊条件能省掉什么
性质 A 覆盖测试点 11—13，共 15 分：第一站最便宜，全部油都在那里买，总量为总路程除以 d 向上取整。性质 B 覆盖测试点 14—16，共 15 分：每段路程都是 d 的倍数，可以把每段所需油量乘以此前最低油价，不再处理余油。
提示3-观察两个性质
\(n\le10^5\)，要线性处理。性质 A 的第一站最便宜，全部油都能在那里买；性质 B 的路长是 d 的倍数，没有余油问题。这两类简化提醒我：一般情况要同时记录最低油价和余油。
提示4-把油换成还能走的公里数
distance 是累计路程，available 是已买油对应的总里程。每次缺口为 distance−available，购买 ceil(缺口/d) 升，按此前最低油价计费。这个记账相当于在最便宜的已到站提前购入，不是倒车回去买。
提示5-取整与大答案
路程和最多接近 \(10^{10}\)，费用可到 \(10^{15}\)，都用 long long。检查 n=1、刚好够油、剩一点油和途中出现更低价格。
代码-30分
仅适用于性质 A 或 B，覆盖测试点 11—16，共 30 分。时间 \(O(n)\)，空间 \(O(n)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int distancePart[N], price[N];
int main() {
int n, d;
cin >> n >> d;
long long total = 0;
for (int i = 1; i < n; i++) {
cin >> distancePart[i];
total += distancePart[i];
}
bool firstCheapest = true;
for (int i = 1; i <= n; i++) {
cin >> price[i];
if (price[i] < price[1]) firstCheapest = false;
}
long long answer = 0;
if (firstCheapest) {
// 我利用第一站最便宜，把所有需要的油提前买齐。
answer = (total + d - 1) / d * price[1];
} else {
int cheapest = price[1];
for (int i = 1; i < n; i++) {
cheapest = min(cheapest, price[i]);
answer += 1LL * (distancePart[i] / d) * cheapest;
}
}
cout << answer;
return 0;
}
代码-满分
时间 \(O(n)\)，空间 \(O(n)\)；价格与距离按输入先后分别读入。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int distanceToNext[N], price[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, d;
cin >> n >> d;
for (int i = 1; i < n; i++) cin >> distanceToNext[i];
for (int i = 1; i <= n; i++) cin >> price[i];
long long distance = 0, available = 0, answer = 0;
int cheapest = price[1];
for (int i = 1; i < n; i++) {
cheapest = min(cheapest, price[i]);
distance += distanceToNext[i];
if (distance > available) {
long long buy = (distance - available + d - 1) / d;
available += buy * d;
// 我用此前最低油价补上缺口，相当于在那里提前购买。
answer += buy * cheapest;
}
}
cout << answer;
return 0;
}
2023T3-P9750一元二次方程¶
提示1-先把求根与输出分开
我先算判别式，分清无实根、有理根、无理根。别急着用小数输出：题目要求约分后的分数和化简后的根式。
提示2-特殊条件能省掉什么
性质 B 是 c=0，覆盖测试点 1、5、6，共 30 分，方程变成 x(ax+b)=0，两根直接是 0 和 −b/a，只需比较、约分。性质 A 是 b=0，要解 x²=−c/a，仍可能有根式，不能误认为一定有整数根。性质 C 的 50 分则已有整数根示范。
提示3-从整数根拿到一个起点
性质 C 保证有解时两根都是整数，测试点 1、3、5、7、8 共 50 分。性质 A 的 b=0、性质 B 的 c=0 能少一些分支，但一般情况仍要完整化简。\(|a|,|b|,|c|\le1000\)，判别式最大 \(5\times10^6\)。
提示4-较大根与分数符号
a>0 时选择 +sqrt(delta)，a<0 时选择 −sqrt(delta)。我把分数输出封装成函数：分母变正，分子分母除以 gcd；分母为 1 就只输出整数，零应输出 0。
提示5-根号外与根号内
把 delta 写成 outside²*inside，inside 不再含平方因子。较大根的根式系数是 outside/(2|a|)，一定为正；有理部分为 −b/(2a)。按题面省略零项、系数 1 和分母 1。检查重根、负 a、负有理项和 b=0。
代码-30分
仅适用于性质 B（c=0），覆盖测试点 1、5、6，共 30 分。时间 \(O(T\log M)\)，额外空间 \(O(1)\)。
#include <bits/stdc++.h>
using namespace std;
int main() {
int tests, limit;
cin >> tests >> limit;
for (int i = 0; i < tests; i++) {
long long a, b, c;
cin >> a >> b >> c;
long long numerator = -b, denominator = a;
if (denominator < 0) {
numerator = -numerator;
denominator = -denominator;
}
if (i) cout << '\n';
// 我比较 0 和 -b/a，只输出其中较大的根。
if (numerator <= 0) cout << 0;
else {
long long g = gcd(numerator, denominator);
numerator /= g;
denominator /= g;
cout << numerator;
if (denominator != 1) cout << '/' << denominator;
}
}
return 0;
}
代码-50分
仅适用于性质 C，覆盖测试点 1、3、5、7、8。不能处理一般分数根或无理根。
#include <bits/stdc++.h>
using namespace std;
int main() {
int T, M;
cin >> T >> M;
while (T--) {
long long a, b, c;
cin >> a >> b >> c;
long long delta = b * b - 4 * a * c;
if (delta < 0) cout << "NO";
else {
long long root = sqrt(delta);
long long sign = (a > 0 ? 1 : -1);
// 这一版只使用“有解时两根均为整数”的性质。
cout << (-b + sign * root) / (2 * a);
}
if (T) cout << '\n';
}
return 0;
}
代码-满分
每组试除化简的时间上界 \(O(\sqrt{\Delta})\)，额外空间 \(O(1)\)（不计短输出字符串）。所有系数用 long long 运算；整数平方根再做校正。
#include <bits/stdc++.h>
using namespace std;
long long gcdValue(long long a, long long b) {
return b == 0 ? a : gcdValue(b, a % b);
}
string fraction(long long numerator, long long denominator) {
if (denominator < 0) {
numerator = -numerator;
denominator = -denominator;
}
long long g = gcdValue(abs(numerator), denominator);
numerator /= g;
denominator /= g;
if (denominator == 1) return to_string(numerator);
return to_string(numerator) + "/" + to_string(denominator);
}
string solve(long long a, long long b, long long c) {
long long delta = b * b - 4 * a * c;
if (delta < 0) return "NO";
long long root = sqrt(delta);
while ((root + 1) * (root + 1) <= delta) root++;
while (root * root > delta) root--;
if (root * root == delta) {
long long sign = (a > 0 ? 1 : -1);
return fraction(-b + sign * root, 2 * a);
}
long long outside = 1, inside = delta;
for (long long p = 2; p * p <= inside; p++) {
while (inside % (p * p) == 0) {
inside /= p * p;
outside *= p;
}
}
string answer;
if (b != 0) answer = fraction(-b, 2 * a) + "+";
long long denominator = 2 * abs(a);
long long g = gcdValue(outside, denominator);
outside /= g;
denominator /= g;
if (outside != 1) answer += to_string(outside) + "*";
answer += "sqrt(" + to_string(inside) + ")";
if (denominator != 1) answer += "/" + to_string(denominator);
return answer;
}
int main() {
int T, M;
cin >> T >> M;
while (T--) {
long long a, b, c;
cin >> a >> b >> c;
cout << solve(a, b, c);
if (T) cout << '\n';
}
return 0;
}
2023T4-P9751旅游巴士¶
提示1-先去掉限制看基本问题
我先只看有向图和每条边耗时 1，想从入口到出口。再加上进出时刻都是 k 的倍数，同一个点的不同到达时刻是否还能合并？
提示2-特殊条件能省掉什么
全部 \(a_i=0\) 的测试点 1—2、6—7、11—13，共 35 分，道路开放限制消失，边权都是 1，可在“点、时间余数”状态上 BFS。\(k=1\) 的测试点 6—10，共 25 分，余数维度消失，但道路可能晚开放，仍需按开放时间做 Dijkstra。两组重合 10 分，不能直接加成 60 分。\(u_i\le v_i\) 也可能有自环，不能未经处理就当成严格 DAG。
提示3-时间余数是必要状态
\(n\le10^4\)、\(m\le2\times10^4\)、\(k\le100\)。设 dist[u][r] 为到 u 且时间余数为 r 的最早时刻，同一点不同余数可能有不同后续。a=0、k=1 的性质简化成普通最短路；不能把一般答案直接向上取整到班次时间。
提示4-道路未开放时如何处理
到 u 的时刻 t 早于开放时间 a，我把整个方案从入口的出发时间推迟 ceil((a−t)/k)*k，之前经过的路仍然合法，且余数不变。这里不是允许在 u 等待；接着走边得到 t+1。相同余数的较早方案可整体后移，因此只保留最早值。
提示5-为什么用 Dijkstra
转移得到的时刻不会早于当前时刻，且随当前时刻单调不减，所以用小根堆处理最早状态。同一状态的旧堆记录要跳过；最后只取 dist[n][0]，不可达输出 −1。时间值用 long long，避免依赖原有队列松弛版本的偶然表现。
代码-25分
仅适用于 \(k=1\)，覆盖测试点 6—10，共 25 分。时间 \(O((n+m)\log n)\)，空间 \(O(n+m)\)。
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
typedef pair<long long, int> PLI;
const int N = 1e4 + 10;
const long long INF = 1LL << 60;
vector<PII> h[N];
long long dist[N];
int main() {
int n, m, k;
cin >> n >> m >> k;
for (int i = 0; i < m; i++) {
int u, v, open;
cin >> u >> v >> open;
h[u].push_back({v, open});
}
fill(dist, dist + n + 1, INF);
priority_queue<PLI, vector<PLI>, greater<PLI>> q;
dist[1] = 0;
q.push({0, 1});
while (!q.empty()) {
PLI fr = q.top();
q.pop();
int u = fr.second;
if (fr.first != dist[u]) continue;
for (auto edge : h[u]) {
int v = edge.first;
// 我把从入口出发的时刻整体后移，k=1 时可移任意整数。
long long next = max(dist[u], 1LL * edge.second) + 1;
if (next < dist[v]) {
dist[v] = next;
q.push({next, v});
}
}
}
if (dist[n] == INF) cout << -1;
else cout << dist[n];
return 0;
}
代码-35分
仅适用于所有 \(a_i=0\)，覆盖测试点 1—2、6—7、11—13，共 35 分。时间 \(O(k(n+m))\)，空间 \(O(nk+m)\)。
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e4 + 10;
const int K = 110;
vector<int> h[N];
int dist[N][K];
int main() {
int n, m, k;
cin >> n >> m >> k;
for (int i = 0; i < m; i++) {
int u, v, open;
cin >> u >> v >> open;
h[u].push_back(v);
}
memset(dist, -1, sizeof dist);
queue<PII> q;
dist[1][0] = 0;
q.push({1, 0});
while (!q.empty()) {
PII fr = q.front();
q.pop();
int mod = (fr.second + 1) % k;
for (int v : h[fr.first]) {
if (dist[v][mod] != -1) continue;
// 我保留余数，走到出口还必须赶上整点班次。
dist[v][mod] = dist[fr.first][fr.second] + 1;
q.push({v, mod});
}
}
cout << dist[n][0];
return 0;
}
代码-满分
时间 \(O(nk+km\log(nk))\)，空间 \(O(nk+m)\)。不使用途中等待，也不遗漏出口的余数要求。
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
typedef pair<long long, PII> State;
const int N = 1e4 + 10;
const int K = 110;
const long long INF = 1LL << 60;
vector<PII> h[N];
long long dist[N][K];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, k;
cin >> n >> m >> k;
while (m--) {
int u, v, open;
cin >> u >> v >> open;
h[u].push_back({v, open});
}
for (int u = 1; u <= n; u++) {
for (int r = 0; r < k; r++) dist[u][r] = INF;
}
priority_queue<State, vector<State>, greater<State>> que;
dist[1][0] = 0;
que.push({0, {1, 0}});
while (!que.empty()) {
State now = que.top();
que.pop();
long long time = now.first;
int u = now.second.first, remainder = now.second.second;
if (time != dist[u][remainder]) continue;
for (PII edge : h[u]) {
int v = edge.first, open = edge.second;
long long leave = time;
if (leave < open) {
// 我整体推迟从景区入口出发的时间，不在途中等待。
leave += (open - leave + k - 1) / k * k;
}
long long arrive = leave + 1;
int next = arrive % k;
if (arrive < dist[v][next]) {
dist[v][next] = arrive;
que.push({arrive, {v, next}});
}
}
}
if (dist[n][0] == INF) cout << -1;
else cout << dist[n][0];
return 0;
}
2024T1-P11227扑克牌¶
提示1-张数和种类数一样吗
我先试两张相同的 SA：它们能补齐两种缺牌吗？性质 A 保证没有重复，52−n 适用于测试点 1—4，共 40 分。
提示2-特殊条件能省掉什么
性质 B 覆盖测试点 5—7，共 30 分。牌按固定次序给出，相同牌必然相邻，问题变成统计连续段数；不需要集合。与性质 A 的 40 分是两种不同简化方式。
提示3-小范围允许直接去重
\(n\le52\)，全部合法牌也只有 52 种。性质 B 中相同牌相邻，比较相邻即可；一般数据则可用 set 去重，或者二维标记。
提示4-最后缺多少种
我用集合大小作为已有牌的种类数，再用 52 相减。同点数不同花色要分别计数，10 用字符 T。检查全重复、完整牌组和一张牌。
代码-30分
仅适用于性质 B，覆盖测试点 5—7，共 30 分。时间 \(O(n)\)，额外空间 \(O(1)\)。
代码-40分
仅适用于性质 A，覆盖测试点 1—4；重复牌不满足这一版的假设。
代码-满分
时间 \(O(n\log n)\)，空间 \(O(n)\)。集合已经能处理全部数据，不重复列出同算法的其他写法。
2024T2-P11228地图探险¶
提示1-先只做一步
我先写一次操作：前方合法就移动，否则原地右转。右转本身消耗一步，不能转完后在同一步继续走；起点也算经过。
提示2-特殊条件能省掉什么
测试点 1—4 的 k=1，只需检查一次操作。测试点 5 是一行全空地，但仍会在边界转向；测试点 7 全为空地，也仍会重复经过格子。它们适合先手算行为，但不能直接用 k+1 当访问数，现有模拟已经能覆盖。
提示3-什么地方才需要优化
\(T\le5\)、\(n,m\le1000\)、\(k\le10^6\)，逐步模拟可行。前六个点 \(k\le2000\)，列表查重可覆盖 60 分；大数据每步再扫历史才是瓶颈。单行、全空地性质适合手算，不需要另写复杂分支。
提示4-一次标记代替历史查找
我用 seen[x][y] 保存是否到过，只在第一次到达时增加答案。方向按东、南、西、北编号，右转取 (d+1)%4。每组都重置标记；检查四面被挡、边界朝外和反复绕圈。
代码-60分
适用于 \(k\le2000\)，覆盖测试点 1—6。时间 \(O(nm+k^2)\)，空间 \(O(nm+k)\)。
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e3 + 10;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
char g[N][N];
int main() {
int T;
cin >> T;
bool firstAnswer = true;
while (T--) {
if (!firstAnswer) cout << '\n';
firstAnswer = false;
int n, m, k, x, y, d;
cin >> n >> m >> k >> x >> y >> d;
x--;
y--;
vector<string> g(n);
for (string &row : g) cin >> row;
vector<PII> visited = {{x, y}};
while (k--) {
int nx = x + dx[d], ny = y + dy[d];
if (nx < 0 || nx >= n || ny < 0 || ny >= m ||
g[nx][ny] == 'x') {
d = (d + 1) % 4;
} else {
x = nx;
y = ny;
}
PII pos = {x, y};
// 先用直观的线性查找，下一版再优化查重。
if (find(visited.begin(), visited.end(), pos) == visited.end()) {
visited.push_back(pos);
}
}
cout << visited.size();
}
return 0;
}
代码-满分
时间 \(O(nm+k)\)，空间 \(O(nm)\)。固定二维数组保存地图与访问标记。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
bool seen[N][N];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
char g[N][N];
int main() {
int T;
cin >> T;
bool firstAnswer = true;
while (T--) {
if (!firstAnswer) cout << '\n';
firstAnswer = false;
int n, m, k, x, y, d;
cin >> n >> m >> k >> x >> y >> d;
x--;
y--;
vector<string> g(n);
for (string &row : g) cin >> row;
memset(seen, 0, sizeof seen);
seen[x][y] = true;
int answer = 1;
while (k--) {
int nx = x + dx[d], ny = y + dy[d];
if (nx < 0 || nx >= n || ny < 0 || ny >= m ||
g[nx][ny] == 'x') {
d = (d + 1) % 4;
} else {
x = nx;
y = ny;
}
// 我只在第一次走到这个格子时增加答案。
if (!seen[x][y]) {
seen[x][y] = true;
answer++;
}
}
cout << answer;
}
return 0;
}
2024T3-P11229小木棍¶
提示1-先比较小答案
我先列 2、6、7、8 根的答案，再问：数值更小，应该先最小化什么？答案可能上万位，不能用整数类型保存；首位还不能是 0。
提示2-特殊条件能省掉什么
性质 A 覆盖测试点 3—5，共 30 分：n=7q，最少 q 位，每位都必须用 7 根，所以答案全是 8。性质 B 覆盖测试点 6—8，共 30 分：n=7q+1，最少 q+1 位；先用 1，再用 0，余下全用 8，得到 10 后接 q−1 个 8。这个构造也可单独拿到另一组 30 分。
提示3-从小范围 DP 观察性质
\(T\le50\)、\(n\le10^5\)。\(n\le1000\) 的测试点 1、2、3、6、9 共 50 分，可以保存最小字符串。性质 A 是 7 的倍数，性质 B 是 7q+1；每位最多用 7 根，这些性质提示我先确定最少位数。
提示4-固定长度后逐位选择
n≥2 时最少位数 L=ceil(n/7)。剩 t 位的费用范围是 [2t,7t]，2—7 的每种费用都有数字，因此每个整数费用都可实现。我从小数字开始试，只有余下费用还能填完余下位数时才选；首位从 1 开始。
提示5-为什么选小数字不会后悔
位数固定时，第一次不同的高位决定大小。每次都选最小且能完成后缀的数字，因此得到最小答案。n=1 无解；检查 n=6、8、15、18，18 的答案应为 208。
代码-50分
适用于 \(n\le1000\)，覆盖测试点 1、2、3、6、9。字符串 DP 的时间、空间上界均为 \(O(N^2)\)，大于 1000 的询问不作正确性保证。
#include <bits/stdc++.h>
using namespace std;
int cost[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
bool better(const string &a, const string &b) {
return b.empty() || a.size() < b.size() ||
(a.size() == b.size() && a < b);
}
int main() {
int T;
cin >> T;
vector<int> query(T);
for (int &n : query) cin >> n;
// 此版本只预处理到 1000，大数据需要后面的完整解法。
int N = min(1000, *max_element(query.begin(), query.end()));
vector<string> best(N + 1);
for (int d = 1; d <= 9; d++) {
if (cost[d] <= N) {
string candidate(1, char('0' + d));
if (better(candidate, best[cost[d]])) best[cost[d]] = candidate;
}
}
// 首位已经单独处理，现在才允许追加数字 0。
for (int s = 1; s <= N; s++) {
if (best[s].empty()) continue;
for (int d = 0; d <= 9; d++) {
int next = s + cost[d];
if (next > N) continue;
string candidate = best[s] + char('0' + d);
if (better(candidate, best[next])) best[next] = candidate;
}
}
bool firstAnswer = true;
for (int n : query) {
if (!firstAnswer) cout << '\n';
firstAnswer = false;
if (n > N || best[n].empty()) cout << -1;
else cout << best[n];
}
return 0;
}
代码-60分
仅适用于性质 A 或 B，覆盖测试点 3—8，共 60 分；两种性质分别覆盖 30 分。每组时间 \(O(n)\)（含输出），额外空间 \(O(1)\)。
#include <bits/stdc++.h>
using namespace std;
int main() {
int tests;
cin >> tests;
for (int i = 0; i < tests; i++) {
int n;
cin >> n;
if (i) cout << '\n';
int count = n / 7;
if (n % 7 == 0) {
for (int j = 0; j < count; j++) cout << '8';
} else {
// 我先用 1 和 0，剩余位都用费用最大的 8。
cout << "10";
for (int j = 0; j < count - 1; j++) cout << '8';
}
}
return 0;
}
代码-满分
每组时间 \(O(n)\)（含构造与输出），空间 \(O(n)\)。只保留这个线性构造，不再列等价的重复实现。
#include <bits/stdc++.h>
using namespace std;
int cost[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
int main() {
int T;
cin >> T;
bool firstAnswer = true;
while (T--) {
if (!firstAnswer) cout << '\n';
firstAnswer = false;
int n;
cin >> n;
if (n == 1) {
cout << -1;
continue;
}
int length = (n + 6) / 7;
string answer;
for (int pos = 0; pos < length; pos++) {
int remaining = length - pos - 1;
for (int d = (pos == 0 ? 1 : 0); d <= 9; d++) {
int left = n - cost[d];
// 我只选择还能恰好填完剩余位数的数字。
if (2 * remaining <= left && left <= 7 * remaining) {
answer += char('0' + d);
n = left;
break;
}
}
}
cout << answer;
}
return 0;
}
2024T4-P11230接龙¶
提示1-先接一轮，再接两轮
我先枚举从 1 开始的合法片段。第二轮除了首尾相接，还有哪个限制？如果只知道一个末尾数字可达，能判断上一个人是谁吗？
提示2-特殊条件能省掉什么
性质 A 覆盖测试点 4—6，共 15 分：k 达到上限，任何词库片段都不会超长，扫描时只需记“前面是否有可用起点”。性质 B 覆盖测试点 7—10，共 20 分：k≤5，每个起点最多枚举 4 个终点，朴素片段枚举就能处理大词库。性质 C 覆盖测试点 11—14，共 20 分：每个字符只出现至多 5 次，按字符列出位置时同值分支变少；仍须处理不同字符与参与者，不能据此说总词库很短。
提示3-看总长度和轮数
单组总长度 \(S\le2\times10^5\)、最大轮数 \(R\le100\)、数字值 \(V\le2\times10^5\)。一轮、小词库适合枚举片段，测试点 1—3 共 15 分；性质 A 放宽长度、B 限制 k≤5、C 限制每个数字出现次数，各自都能减少转移，但一般情况仍不能枚举所有片段。
提示4-参与者只需三类信息
previous[c] 记录上一轮以 c 结束的参与者：−1 为无人，正数为唯一的人，0 为至少两人。下一轮只排除一个人，这三类信息就足够。第 0 轮把数字 1 设为 0，允许任意人开始。
提示5-每个人的词库扫描一次
我记录最近一个可作起点的位置 last。当前 j 满足 1≤j−last<k 就可作为终点；更早起点只会更容易超长，所以最近起点足够。先更新终点，再把 j 作为后续起点，保证长度至少 2。检查同人不能连两轮、隔轮可以再来和多名参与者合并。
代码-70分
这版片段枚举代码在洛谷测评中获得 70 分。小规模数据和性质 B 的 \(k\le5\) 都适合先用它练习；一般数据仍需注意枚举次数。
时间上界 \(O(R(S\min(k,S)+V))\)，其中 S 是词库总长度，V 是数字值域上界。小 k 时，每个起点最多枚举 4 个终点，时间为 \(O(R(S+V))\)；空间 \(O(RV+S+n+q)\)。
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 2e5 + 10;
const int M = 1e5 + 10;
int words[N], start[M], len[M];
int previous[N], current[N];
unsigned char reachable[105][N];
void mergeState(int value, int id) {
if (current[value] == -1) current[value] = id;
else if (current[value] != id) current[value] = 0;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
bool firstAnswer = true;
int T;
cin >> T;
while (T--) {
int n, k, q, valueMax = 1;
cin >> n >> k >> q;
int total = 0;
memset(reachable, 0, sizeof reachable);
for (int id = 1; id <= n; id++) {
int length;
cin >> length;
start[id] = total;
len[id] = length;
for (int j = 0; j < length; j++) {
cin >> words[total];
valueMax = max(valueMax, words[total]);
total++;
}
}
vector<PII> queries(q);
int rounds = 0;
for (auto &query : queries) {
cin >> query.first >> query.second;
rounds = max(rounds, query.first);
valueMax = max(valueMax, query.second);
}
// -1：不可达；0：至少两个不同的人可作为末轮参与者；
// 正数 id：只能由这一个人作为末轮参与者。
memset(previous, -1, sizeof previous);
previous[1] = 0; // 虚拟第 0 轮，允许任意人从 1 开始。
for (int r = 1; r <= rounds; r++) {
fill(current, current + valueMax + 1, -1);
for (int id = 1; id <= n; id++) {
const int *a = words + start[id];
for (int left = 0; left < len[id]; left++) {
// 我先排除上一轮也由当前这个人接龙的情况。
int state = previous[a[left]];
if (state == -1 || state == id) continue;
for (int right = left + 1;
right < len[id] && right - left < k; right++) {
mergeState(a[right], id);
}
}
}
for (int x = 1; x <= valueMax; x++) {
reachable[r][x] = (current[x] != -1);
}
copy(current, current + valueMax + 1, previous);
}
for (auto query : queries) {
if (!firstAnswer) cout << '\n';
cout << int(reachable[query.first][query.second]);
firstAnswer = false;
}
}
return 0;
}
代码-满分
时间 \(O(R(S+V)+n+q)\)，空间按轮数与数字范围存可达表，另存词库和询问。固定数组放全局，避免大二维表占用栈。
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 2e5 + 10;
const int M = 1e5 + 10;
int words[N], start[M], len[M];
int previous[N], current[N];
unsigned char reachable[105][N];
void mergeState(int value, int id) {
if (current[value] == -1) current[value] = id;
else if (current[value] != id) current[value] = 0;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
bool firstAnswer = true;
int T;
cin >> T;
while (T--) {
int n, k, q, valueMax = 1;
cin >> n >> k >> q;
int total = 0;
memset(reachable, 0, sizeof reachable);
for (int id = 1; id <= n; id++) {
int length;
cin >> length;
start[id] = total;
len[id] = length;
for (int j = 0; j < length; j++) {
cin >> words[total];
valueMax = max(valueMax, words[total]);
total++;
}
}
vector<PII> queries(q);
int rounds = 0;
for (auto &query : queries) {
cin >> query.first >> query.second;
rounds = max(rounds, query.first);
valueMax = max(valueMax, query.second);
}
// -1：不可达；0：至少两个不同的人可作为末轮参与者；
// 正数 id：只能由这一个人作为末轮参与者。
memset(previous, -1, sizeof previous);
previous[1] = 0; // 虚拟第 0 轮，允许任意人从 1 开始。
for (int r = 1; r <= rounds; r++) {
fill(current, current + valueMax + 1, -1);
for (int id = 1; id <= n; id++) {
const int *a = words + start[id];
int last = -1;
for (int j = 0; j < len[id]; j++) {
// 先当终点，再更新起点，片段才不会只有一个数字。
if (last != -1 && j - last < k) mergeState(a[j], id);
int state = previous[a[j]];
if (state != -1 && state != id) last = j;
}
}
for (int x = 1; x <= valueMax; x++) {
reachable[r][x] = (current[x] != -1);
}
copy(current, current + valueMax + 1, previous);
}
for (auto query : queries) {
if (!firstAnswer) cout << '\n';
cout << int(reachable[query.first][query.second]);
firstAnswer = false;
}
}
return 0;
}
2025T1-P14357拼数¶
提示1-先决定哪些数字要用
我先试 1a01b。0 是否应该丢掉？多留一位会让正整数更大，把非零数字放在前面即可避免前导零。题目保证至少一个非零数字。
提示2-特殊条件能省掉什么
性质 A 只有数字，省去过滤字母，但 \(10^6\) 个数字仍不适合平方排序。性质 B 的字符串虽长，数字却至多 1000 个，所以先过滤再排序是有效部分分。简化的是参与排序的数量，不是输入长度；仍要读完字符串。
提示3-排序对象比字符串小
\(|s|\le10^6\)，但性质 B 保证数字数 D≤1000。筛选后用插入排序，可以覆盖 D≤1000 的测试点；不要把整个字符串长度误当作要排序的数字数。
提示4-只有十种数字
位数确定后，我交换两个相邻数字，发现大的在前更好。再看只有 0—9 十种，统计次数后从 9 到 0 输出即可。A 中无字母，也由同一过滤过程处理；答案用字符串输出，不能转成整数。
代码-72分
适用于数字数量 D≤1000，覆盖测试点 1—14、16—17、21—22（共 18 点，每点 4 分）。时间 \(O(|s|+D^2)\)，大规模数字输入不保证通过。
#include <bits/stdc++.h>
using namespace std;
int main() {
string s, digits;
cin >> s;
for (char c : s) {
if ('0' <= c && c <= '9') digits += c;
}
for (int i = 1; i < int(digits.size()); i++) {
char digit = digits[i];
int j = i;
// 我让大的数字向前移动，使高位尽量大。
while (j > 0 && digits[j - 1] < digit) {
digits[j] = digits[j - 1];
j--;
}
digits[j] = digit;
}
cout << digits;
return 0;
}
代码-满分
时间 \(O(|s|)\)，读取字符串占 \(O(|s|)\) 空间，计数数组为 \(O(1)\)。
2025T2-P14358座位¶
提示1-先画出座位方向
我先画 n=3、m=2：第一列向下，第二列向上。这里按列蛇形，输出也是列号在前、行号在后。
提示2-特殊条件能省掉什么
测试点 2—3 只有一行，列号就是名次；测试点 4—5 只有一列，行号就是名次。A 中小 R 的成绩为 1，必为最后一名；B 中为 nm，必为第一名。它们能帮我检查蛇形方向，现有名次公式已同样简单，不另列重复版本。
提示3-只需要知道自己的名次
\(n,m\le10\)，成绩互不相同，最多 100 人。模拟和排序都够用；A、B 给出的固定成绩顺序可直接找名次，但一般情况只需统计比小 R 高的人数，不必排出所有人的顺序。
提示4-把名次拆成列与列内位置
用从 0 开始的 rank：column=rank/n，offset=rank%n。偶数编号列从上向下，行号为 offset+1；奇数列从下向上，行号为 n−offset。检查第 n 名、第 n+1 名和最后一名，同一公式处理单行、单列。
代码-满分
时间 \(O(nm)\)，额外空间 \(O(1)\)。不再重复列只处理一行的同算法版本。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m, mine;
cin >> n >> m >> mine;
int rank = 0;
for (int i = 1; i < n * m; i++) {
int score;
cin >> score;
if (score > mine) rank++;
}
// 我用从 0 开始的名次，让整除和取模统一处理换列。
int column = rank / n;
int offset = rank % n;
int row = (column % 2 == 0 ? offset + 1 : n - offset);
cout << column + 1 << ' ' << row;
return 0;
}
2025T3-P14359异或和¶
提示1-先枚举小范围的区间
我先用 dp[i] 表示前 i 个数最多能选多少个区间。最后一段若为 [j,i]，只能接 dp[j−1]；否则可以继承 dp[i−1]。
提示2-特殊条件能省掉什么
性质 A 的测试点 1、3 共 10 分，全是 1 且 k=0，最短合法区间是两个 1，答案为 n/2。性质 B 的测试点 2、4、5、13 共 20 分：只含 0/1，k=0 时每个 0 单独取、每段连续 1 两两配对；k=1 时每个 1 单独取。为了跨过 0 凑一对 1，最多新增一段，却会失去至少一个可单独取的 0，不会更优；k=1 时每个合法区间都至少含一个 1，单独取每个 1 已达到上限。性质 C 则把前缀值域缩到 256。
提示3-数据要求减少枚举
前 12 个测试点 n≤1000，共 60 分，\(O(n^2)\) 可行；一般 n≤\(5\times10^5\)。性质 A 全 1、B 只含 0/1、C 值至多 255，都适合手算前缀；所有数据 a[i],k<\(2^{20}\)，前缀异或也在这个范围。
提示4-先找到一个结束最早的区间
区间异或是两个前缀的异或。当前前缀为 x，查历史是否出现 x^k。第一个合法结束点就选：用它替换最优方案的第一段，结束不会更晚，也不妨碍后续，因此不会少选区间。
提示5-选完要换一批起点
我用时间戳数组记录当前可用的前缀，选完区间就换代号，再插入当前前缀，作为下一段的边界。先查询后插入，避免 k=0 时误选空区间。检查全 0、无解、重复前缀。
代码-30分
仅适用于全部元素及 k 都在 0/1 中，覆盖测试点 1—5、13，共 30 分（A 与 B 的并集）。时间 \(O(n)\)，空间 \(O(1)\)。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
int answer = 0, ones = 0;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (k == 1) {
answer += x;
} else if (x == 0) {
// 我把 0 单独取出，再将连续的 1 两两配对。
answer += ones / 2 + 1;
ones = 0;
} else {
ones++;
}
}
if (k == 0) answer += ones / 2;
cout << answer;
return 0;
}
代码-60分
适用于 n≤1000，覆盖测试点 1—12。时间 \(O(n^2)\)，空间 \(O(n)\)。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<int> a(n + 1), dp(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) {
dp[i] = dp[i - 1];
int value = 0;
for (int j = i; j >= 1; j--) {
value ^= a[j];
// 选 [j,i] 后，只能接上前 j-1 个位置的答案。
if (value == k) dp[i] = max(dp[i], dp[j - 1] + 1);
}
}
cout << dp[n];
return 0;
}
代码-满分
时间 \(O(n+2^{20})\)，空间 \(O(2^{20})\)。每次清除用改代号代替，避免反复清空整张表。
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<int> stamp(1 << 20);
int generation = 1, prefix = 0, answer = 0;
stamp[0] = generation;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
prefix ^= x;
if (stamp[prefix ^ k] == generation) {
answer++;
// 我换一个代号，让上一段的起点全部失效。
generation++;
}
stamp[prefix] = generation;
}
cout << answer;
return 0;
}
2025T4-P14360多边形¶
提示1-先检查少量木棍
我先枚举子集，判断根数至少 3、总长度严格大于两倍最长长度。1、2、3 的等号不能组成三角形；相同长度的不同下标仍是不同选择。
提示2-特殊条件能省掉什么
测试点 1—3 的 n=3，只需检查唯一的三根组合。测试点 15—20 的所有长度为 1，共 24 分，几何条件变成“至少选三根”，直接用全部子集数减去选 0、1、2 根的数量。测试点 11—14 长度至多 100，满分背包的容量就能缩小；已有 24 分公式代码保留。
提示3-两个小范围各有用处
前十点 n≤20，共 40 分，可枚举子集。测试点 15—20 全是 1，共 24 分，可用 \(2^n-1-n-\binom n2\)。一般 n≤5000、长度 A≤5000，指数枚举不行，但小长度允许背包。
提示4-按最大所选下标分类
我先排序，把每个非空子集归给最大所选下标 i，长度相等也不会重复归类。设这根长 x，其余所选长度和为 s，合法条件就变为 s>x。总方案 \(2^i\)（i 从 0 开始），减去 s≤x 的坏方案。
提示5-背包只保存小的和
dp[s] 统计此前木棍的子集和为 s 的方案数，dp[0]=1，只保存 s≤A，因为正长度不可能把更大的和降回来。先算当前贡献，再倒序加木棍；选 1 根、2 根都会自动算入坏方案。取模并检查相等长度、全 1、严格等号。
代码-24分
仅适用于所有长度为 1，覆盖测试点 15—20。时间 \(O(n)\)，额外空间 \(O(1)\)；一般长度不能套用此式。
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 998244353;
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int length;
cin >> length;
}
long long power = 1;
for (int i = 0; i < n; i++) power = power * 2 % MOD;
// 只有全 1 时，才可以只扣掉选零根、一根、两根的方案。
long long answer = (power - 1 - n - 1LL * n * (n - 1) / 2) % MOD;
if (answer < 0) answer += MOD;
cout << answer;
return 0;
}
代码-40分
适用于 n≤20，覆盖测试点 1—10。时间 \(O(n2^n)\)，空间 \(O(n)\)；n>20 的占位输出不保证正确。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int &x : a) cin >> x;
// 只适用于 n<=20；大数据请使用背包解法。
if (n > 20) {
cout << 0;
return 0;
}
int answer = 0;
for (int mask = 0; mask < (1 << n); mask++) {
int count = 0, sum = 0, longest = 0;
for (int i = 0; i < n; i++) {
if ((mask >> i) & 1) {
count++;
sum += a[i];
longest = max(longest, a[i]);
}
}
// 等号不能组成多边形，我检查严格大于。
if (count >= 3 && sum > 2 * longest) answer++;
}
cout << answer;
return 0;
}
代码-满分
时间 \(O(nA+n\log n)\)，空间 \(O(n+A)\)。答案对 998244353 取模，MOD 放在全局。
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int &x : a) cin >> x;
sort(a.begin(), a.end());
int A = a.back();
vector<int> dp(A + 1);
dp[0] = 1;
int power = 1, answer = 0;
for (int x : a) {
int bad = 0;
for (int s = 0; s <= x; s++) {
bad += dp[s];
if (bad >= MOD) bad -= MOD;
}
int good = power - bad;
if (good < 0) good += MOD;
answer += good;
if (answer >= MOD) answer -= MOD;
// 我先计算当前最大木棍的贡献，再倒序把它加入背包。
for (int s = A; s >= x; s--) {
dp[s] += dp[s - x];
if (dp[s] >= MOD) dp[s] -= MOD;
}
power = int(2LL * power % MOD);
}
cout << answer;
return 0;
}