死亡回放
【8:30 - 8:45】看 T1，很简单的样子。15 min秒了。
【8:46 - 9:17】看 T2，看起来很板呢。推了下规律，发现这个子序列的生成过程像一个栈，但并不知道如何用栈实现 qwq。其实是可以用单调栈实现的，上这节课的时候是录播课，没搞懂……于是蒟蒻换了种思路写，两个样例都过了。
【9:18 - 10:02】看 T3，应该是数学题。当时手推了一下性质，凭着自己的直觉乱搞了一下，推出了公式！！！在赛后老师讲了题，我才知道那个东西叫“整除分块”。
【10:03 - 11:15】看 T4，是个 dp，好难啊。写啊写啊写啊，写了一个记忆化 + dp。调试完有一个样例没过。于是加了一个特判。
【11:15 - 12:00】检查题目，结果把自己的 T2 解法 hack 了。。。也不想改了，觉得用该能过一点样例。开摆……
估分：
实际：
考试总结
犯了几个错
- 怎么能早早摆烂呢？。
发现自己的解法被 hack 了，应该去重新修改啊！不会单调栈暴力写也能拿 30 pts。
- 为什么那么相信自己的写法？。
如果实在不会（如 T4），完全没有把握可以写一些人类智慧骗分，不需要敲自己认为是正解但成功几率不大的代码。像 hhy 大佬，T4敲了个贪心 + 暴力的人类智慧，能拿 80！
考试题解
T1 存钱
够水的。容易发现将最小的两个加起来是最优的，且能得到一个零，且这个零可以在 [2,n]。那么后面每次操作都可以用这个零，因此全局都是最优的。最后排序，时间复杂度 O(n \log n)
Code
a[0] = 0x3f3f3f3f;
int i = 0, p1 = 0, p2 = 0;
while (t--) {
i++;
if (a[i] < a[p1]) {p2 = p1; p1 = i;}
else if (a[i] < a[p2]) {p2 = i;}
}
a[p1] += a[p2], a[p2] = 0;
sort(a + 1, a + n + 1);
for (int i = 1; i <= n / 2; i++) {
ans += a[i];
}
T2 邦布照相
蒟蒻不会单调栈啊。。。想出是栈结构，但是不会实现。于是蒟蒻换了种思路：
遍历每个元素，尝试选择每个型号的第一次出现，并在剩余次数较多时跳过。
Code
for (int i = 1; i <= n; i++) {
cin >> a[i];
cnt[a[i]]++;
}
for (int i = 1; i <= n; i++) {
if (vis[a[i]]) continue;
if (a[i] > k) continue;
else if (a[i] != 1 && cnt[a[i]] > 1) {cnt[a[i]]--; continue;}
else {
cout << a[i] << ' ';
vis[a[i]] = 1;
}
}
然而，这种方法没有考虑字典序的最小化，导致无法在后续元素中找到更优的排列。
考虑这组 hack：
input
20 9
4 5 2 1 6 7 2 1 3 4 5 9 8 1 6 2 7 9 1 8
output
1 2 3 4 5 6 7 9 8
它输出了：
1 3 4 5 6 2 7 9 8
问什么错了？原因有以下几点：
- 贪心策略不当，代码仅根据当前元素是否首次出现以及剩余次数决定是否选择，未比较元素大小。例如，较大的元素被提前选中后，即使后面有更小的元素也无法替换，导致字典序偏大。
- 无法回溯调整，一旦元素被选中，就无法在后续步骤中调整顺序，而正确的字典序可能需要将前面的较大元素替换为后面的较小元素。
我们应该采用贪心策略，维护一个栈，每次遇到新元素时，尽可能将较小的元素放到前面：
用栈结构保存当前已选的元素，保持字典序尽可能小。当新元素比栈顶小且栈顶元素在后面还会出现时，弹出栈顶元素。记录每个元素的剩余可用次数，确保后续有足够元素组成答案。
考虑单调栈实现，时间复杂度 O(n)。
Code
for (int i = 0; i < n; ++i) {
cin >> a[i];
cnt[a[i]]++;
}
for (int i = 0; i < n; ++i) {
int x = a[i];
if (x > k || inStack[x]) {
cnt[x]--;
continue;
}
while (!st.empty() && x < st.top() &&
cnt[st.top()] > 0 && k - st.size() + 1 <= n - i) {
inStack[st.top()] = false;
st.pop();
}
if (st.size() < k) {
st.push(x);
inStack[x] = true;
}
cnt[x]--;
}
vector<int> res;
while (!st.empty()) {
res.push_back(st.top());
st.pop();
}
reverse(res.begin(), res.end());
for (int v : res) cout << v << ' ';
return 0;
}
T3 CQOI余数之和
把题意转化为公式：
给出正整数 n 和 k，计算
其中 k\bmod i 表示 k 除以 i 的余数。
设答案为 ans，于是 ans = \sum_{i=1}^n k \bmod i。
时间复杂度 O(\sqrt k)。
Code
if (n == 1) cout << 0, exit(0);
else if (n == 2 && k & 1) cout << 1, exit(0);
else if (n == 2 && !(k & 1)) cout << 0, exit(0); // 这几行不要也没关系
int ans = 0, i = 0, j = 0;
int m = n;
while (1) {
if (i == 0) i++;
else i = j + 1;
if (i > n) break;
j = ((k / i == 0) ? n : min(n, k / (k / i)));
ans -= (k / i) * (j - i + 1) * (i + j) / 2;
}
cout << ans + n * k;
越来越觉得自己像数学家了 OAO。当然论数学，肯定不如 @我命由我不由天
T4 集邮比赛 3
JOI 君在环形湖周围收集邮戳，每个邮戳台有位置和撤销时间，需在时间允许下收集最多邮戳。关键在于如何选择移动路径，使得收集的邮戳数量最大，同时保证到达每个邮戳台的时间不超过其撤销时间。
赛时写了小记搜，试图通过逐次移动相邻邮戳台并记录已收集的邮戳来求解，但是 Wa & Re
int dfs(int i, int cnt) {
if (cnt == T) return (t[i] <= cnt && !vis[i]);
if (cnt > T) return 0;
if (dp[i][cnt]) return dp[i][cnt];
int sum = 0;
if (t[i] <= cnt && !vis[i]) sum = 1;
vis[i] = 1;
if (i == 1) {
sum += max(dfs(i + 1, cnt + (x[i + 1] - x[i])), dfs(n, cnt + (x[1] + l - x[n])));
} else if (i == n) {
sum += max(dfs(i - 1, cnt + (x[i] - x[i - 1])), dfs(1, cnt + (x[1] + l - x[n])));
} else {
sum += max(dfs(i + 1, cnt + (x[i + 1] - x[i])), dfs(i - 1, cnt + (x[i] - x[i - 1])));
}
vis[i] = 0;
return dp[i][cnt] = sum;
}
仔细一看，问题还挺多的：
状态缺失了，记忆化状态仅记录当前位置和时间，未考虑已收集的具体邮戳，导致不同收集路径的状态被错误合并。
移动受限，只能移动到相邻邮戳台，无法跨过中间台选择更优路径，可能增加不必要的时间消耗。
未正确处理环形路径的最短距离，导致时间计算错误。
我们换种定义状态的方式，用 dp_{i,j,d,m}，表示已收集左侧 i 个和右侧 j 个邮戳，当前位置在左或右端 d=0/1，已收集 m 个时的最小时间。通过状态转移，每次选择扩展左或右的下一邮戳台，计算最短时间并更新状态。
状态转移：
- 从左侧 i 扩展至 i+1：计算顺时针移动时间，判断是否能在撤销时间内收集。
- 从右侧 j 扩展至 j-1：计算逆时针移动时间，同理更新状态。
最后采用贪心策略，每次选择时间最短的路径扩展，确保在有限时间内收集尽可能多的邮戳。
Code
dp[0][n + 1][0][0] = dp[0][n + 1][1][0] = 0; // 初始状态
for (int i = 0; i < n; i++)
for (int j = n + 1; j >= i + 2; j--)
for (int m = 0; m <= n; m++) {
if (dp[i][j][0][m] == inf && dp[i][j][1][m] == inf) continue;
// 扩展左侧i+1
ll cost0 = dp[i][j][0][m] + (x[i + 1] - x[i]); // 顺时针移动
ll d1 = x[i + 1] - x[j];
ll cost1 = dp[i][j][1][m] + min(abs(d1), l - abs(d1)); // 最短路径
ll tmp = min(cost0, cost1);
int nm = m + (tmp <= t[i + 1]);
if (nm <= n) dp[i + 1][j][0][nm] = min(dp[i + 1][j][0][nm], tmp);
// 扩展右侧j-1
ll d2 = x[j - 1] - x[i];
ll cost2 = dp[i][j][0][m] + min(abs(d2), l - abs(d2));
ll cost3 = dp[i][j][1][m] + (x[j] - x[j - 1]);
tmp = min(cost2, cost3);
nm = m + (tmp <= t[j - 1]);
if (nm <= n) dp[i][j - 1][1][nm] = min(dp[i][j - 1][1][nm], tmp);
}
}
放上蔡老师为我们讲解的笔记：
/* dp[l][r][k][m]
l往右走的到达的地点 l+1
r往左走到达的地点
k当前处于左边还是右边
m代表当前收集到的站点数量
最开始 dp[0][n+1][0][0] = 0; dp[0][n+1][1][0] = 0;
状态转移：
站在右边dp[0][n+1][0][0]
往右边走(x[i+1]) dp[i][j][0][m] -> dp[i+1][j][0][m] { dp[i][j][0][m] + x[i+1]-x[i] }
往左走(x[j-1]) dp[i][j][0][m] -> dp[i][j-1][1][m] {dp[i][j][0][m] + l - x[j-1] + x[i]}
//变成站在右边
站在左边dp[0][n+1][1][0]
往左边走(x[j-1]) dp[i][j][1][m] -> dp[i][j-1][1][m] {dp[i][j][1][m] + x[j] - x[j-1]}
往右边走(x[i+1]) dp[i][j][1][m] -> dp[i+1][j][0][m] {dp[i][j][1][m] + l - x[i+1] + x[j]}