一、比赛基本情况
- 比赛日期：2026-08-11
- 比赛时长：4h
- 比赛得分：2pts
二、比赛整体回顾
T1 ~ T2 很快就完成了，还是比较简单。
T3 是搜索题目，一开始就想正解去了，没写暴力；导致考试时没拿到部分分；如果没有一次性想到正解一定要先暴力保分，后面还可以用作对拍。
T4 是关于逆序对的题目，想出了题目和逆序对之间的关系但实现的时候没有注意细节，以后写题目时要想清楚了再写。
T5 是关于模拟的题目，考试时想到了枚举出现了几个字符，然后判断，但因为一些未定义行为导致没通过样例。
T6 因为前面去死磕了，所以每留出太多时间来看这道题，下次一定要分配好时间。
三、比赛理想时间安排
- T1 ~ T2 在 30 min 内完成
- T3 花上十分钟理清代码逻辑，大概在 30min 完成本题
- T4 很容易想到逆序对，大概花 30min 理清思路，大概 15min 写代码
- T5 也很容易想到枚举，细节较多，大约花 15min 写好伪代码再写代码，大约用时 40min
- T6 稍微想一想能知道要记录两维状态，细节也比较多，大概 60min
四、题目复盘
Following Directions S
初始思路
对每个点进行搜索，找到没有修改的答案，然后修改就是改动一个位置，但这样是不对的，最后一个需要改动前面的。所以思路就变成往前面跳，复杂度最多是 \(O(n)\)，理论上不写错可以过了这一题。
错误原因
由于每个点有两种情况，从上面来、从左边来。要分别考虑而不是单独考虑一种情况，所以导致只有 6pts。
赛后题解
每次向上跳，理论上时间复杂度是 \(O(n^2)\) 的，但是随机数据跑的飞快。
递归的常数是很大的，尽量减少递归次数。
本题总结
本题暴露出调试能力的缺陷调试时不能使用瞪眼法来盯着黑窗口，要动手在草稿纸上画一画。
补题代码
#include <bits/stdc++.h>using namespace std;#define ll long long
#define ull unsigned long long
#define db double
#define all(x) (x).begin(), (x).end()
#define inf (1 << 30)
#define lnf (1LL << 60)
typedef pair<int, int> PII;
constexpr int N = 1500 + 7;
constexpr int P = 998244353;int n, q, a[N][N], vis[N][N], bel[N * N], tot;
ll cost[N][N], ans;
char s[N][N];
bool b[N][N];int dfs(int x, int y) {if (x > n) return a[x][y];if (y > n) return a[x][y];vis[x][y] = tot;if (s[x][y] == 'R') return dfs(x, y + 1);else return dfs(x + 1, y);
}void modify(int x, int y, int k) {if (!x || !y) return;if (b[x][y]) return;b[x][y] = true;cost[x][y] = k;if (s[x][y - 1] == 'R') modify(x, y - 1, k);if (x == 1 || s[x - 1][y] == 'D') {modify(x - 1, y, k);}
}void update(int x, int y, int sgn) {if (!x || !y) return;ans += cost[x][y] * sgn;if (s[x][y - 1] == 'R') update(x, y - 1, sgn);if (x == 1 || s[x - 1][y] == 'D') update(x - 1, y, sgn);
}int main() {scanf("%d", &n);for (int i = 1; i <= n; i++) {scanf("%s", s[i] + 1);scanf("%d", &a[i][n + 1]);}for (int i = 1; i <= n; i++) scanf("%d", &a[n + 1][i]);for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {if (!vis[i][j]) {++tot;bel[tot] = dfs(i, j);}}}for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {cost[i][j] = bel[vis[i][j]];ans += cost[i][j];}cost[i][n + 1] = a[i][n + 1];}for (int i = 1; i <= n; i++) {cost[n + 1][i] = a[n + 1][i];}printf("%lld\n", ans);scanf("%d", &q);while (q--) {int x, y;scanf("%d%d", &x, &y);if (s[x][y] == 'R') {s[x][y] = 'D';update(x, y, -1);modify(x, y, cost[x + 1][y]);update(x, y, 1);} else {assert(s[x][y] == 'D');s[x][y] = 'R';update(x, y, -1);modify(x, y, cost[x][y + 1]);update(x, y, 1);}printf("%lld\n", ans);}return 0;
}
Sorting Color Balls
初始思路
由于题目所给过程就是冒泡排序的过程，很容易想到逆序对，相同颜色的逆序对个数肯定是互补干扰的，所以可以用总的逆序对减去相同颜色的逆序对总和。
错误原因
实现上一些细节出现了问题。
赛后题解
就是用总体的减去相同的，实现要把颜色分开做归并排序。
补题代码
#include <bits/stdc++.h>using namespace std;#define ll long long
#define ull unsigned long long
#define db double
#define all(x) (x).begin(), (x).end()
#define inf (1 << 30)
#define lnf (1LL << 60)
typedef pair<int, int> PII;
constexpr int N = 3e5 + 7;
constexpr int P = 998244353;int n;
int a[N], c[N], d[N];
vector<int> b[N];ll divide(int l, int r, int lx) {if (l == r) return 0;int mid = (l + r) / 2;ll res = divide(l, mid, lx) + divide(mid + 1, r, lx);int i = l, j = mid + 1, k = l;while (i <= mid && j <= r) {if (b[lx][i] <= b[lx][j]) d[k++] = b[lx][i++], res += j - mid - 1; else d[k++] = b[lx][j++];}while (i <= mid) d[k++] = b[lx][i++], res += j - mid - 1;while (j <= r) d[k++] = b[lx][j++];for (int p = l; p <= r; p++) b[lx][p] = d[p];return res;
}int main() {scanf("%d", &n);for (int i = 1; i <= n; i++) scanf("%d", &a[i]);for (int i = 1; i <= n; i++) scanf("%d", &c[i]), b[0].push_back(c[i]); for (int i = 1; i <= n; i++) {b[a[i]].push_back(c[i]);}ll res = divide(0, n - 1, 0);for (int i = 1; i <= n; i++) {int l = 0, r = (int)b[i].size() - 1;if (l > r) continue;res -= divide1(l, r, i);}printf("%lld\n", res);return 0;
}
本题总结
本题有一个技巧，就是冒泡排序的交换次数就是逆序对的个数。
Equal Frequencies
初始思路
由于 \(k\) 大于 \(26\) 时，字符集会不够用，所以可以枚举选了多少个字符；
错误原因
由于 UB，导致输入输入了一坨，输出是个不知道什么东西，好像是因为数组越界了、
赛后题解
枚举选了多少个字符，显然一定是 \(n\) 的因数，则个数一定是 \(\dfrac nk\)，找到最小化的 \(k\) 之后构造数列，如果可行直接删掉一个，如果不行，就找到剩余的。
补题代码
#include <bits/stdc++.h>using namespace std;
#define ll long long
#define ull unsigned long long
#define db double
#define all(x) (x).begin(), (x).end()
#define inf (1 << 30)
#define lnf (1LL << 60)
typedef pair<int, int> PII;
constexpr int N = 1e5 + 7;
constexpr int P = 998244353;int n;
char s[N];void solve() {scanf("%d", &n);scanf("%s", s + 1);array<int, 26> cnt{};array<array<int, 2>, 26> cset{};for (int i = 1; i <= n; i++) ++cnt[s[i] - 'a'];for (int i = 0; i < 26; i++) cset[i] = {cnt[i], i};sort(all(cset), greater<array<int, 2>>());int minval = inf, minid = -1;for (int k = 1; k <= 26; k++) {if (n % k != 0) continue;int now = n / k;ll res = 0;for (int i = 0; i < k; i++) res += abs(now - cset[i][0]);for (int i = k; i < 26; i++) {assert(i < (int)cset.size());res += cset[i][0];}res /= 2;if (res < minval) minval = res, minid = k;}printf("%d\n", minval);for (int i = 0; i < 26; i++) cnt[i] = 0;for (int i = 0; i < minid; i++) cnt[cset[i][1]] = n / minid;for (int i = 1; i <= n; i++) {int found = -1;for (int j = 0; j < minid; j++) if (s[i] == (cset[j][1] + 'a')) {found = cset[j][1];break;} if (found < 0) {s[i] = '\0';} else if (!cnt[found]) {s[i] = '\0';} else {--cnt[found];}}for (int i = 1; i <= n; i++) {if (s[i] != '\0') continue;for (int j = 0; j < minid; j++) {if (cnt[cset[j][1]]) {--cnt[cset[j][1]];s[i] = cset[j][1] + 'a';break;}}}for (int i = 1; i <= n; i++) printf("%c", s[i]);puts("");
}int main() {int test;scanf("%d", &test);for (; test--; ) solve();return 0;
}本题总结
本题的核心在于几个点
- 枚举长度，找到可能的最小值；（最小的操作次数）
- 判断是否保留
- 构造数列
Two Currencies
初始思路
NULL
错误原因
NULL
赛后题解
由于当 \(s>50\times50\) 时，就不需要更多银币了，所以其实只要考虑到 \(2500\)，并不是 \(250\)。
所以可以跑分层图上跑最短路。
具体来说建图的时候要建两种图，一种是边与边的，一种是点的。
补题代码
#include <bits/stdc++.h>using namespace std;
#define ll long long
#define ull unsigned long long
#define db double
#define all(x) (x).begin(), (x).end()
#define inf (1 << 30)
#define lnf (1LL << 60)
typedef pair<int, int> PII;
typedef array<ll, 3> arr;
constexpr int N = 50 + 7, V = 2600 + 7;
constexpr int P = 998244353;int n, m, s;
vector<arr> adj[N][V];
ll dis[N][V];
bool vis[N][V];void dijkstra(int sx, int sy) {priority_queue<arr, vector<arr>, greater<arr>> q;memset(dis, 0x3f, sizeof(dis));memset(vis, false, sizeof(vis));dis[sx][sy] = 0;q.push({dis[sx][sy], sx, sy});while (!q.empty()) {auto [d, u, cost] = q.top(); q.pop();if (vis[u][cost]) continue;vis[u][cost] = true;for (auto [v, pay, t] : adj[u][cost]) {if (dis[u][cost] + t < dis[v][pay]) {+dis[v][pay] = dis[u][cost] + t;q.push({dis[v][pay], v, pay});}} }
}int main() {scanf("%d%d%d", &n, &m, &s); s = min(s, 2450);for (int i = 1; i <= m; i++) {int u, v, a, b;scanf("%d%d%d%d", &u, &v, &a, &b);for (int j = a; j <= 2450; j++) {adj[u][j].push_back({v, j - a, b});adj[v][j].push_back({u, j - a, b});}}for (int i = 1; i <= n; i++) {int c, d;scanf("%d%d", &c, &d);for (int j = c; j <= 2450; j++) {adj[i][j - c].push_back({i, j, d});}}dijkstra(1, s);for (int i = 2; i <= n; i++) {ll ans = lnf;for (int j = 0; j <= 2450; j++) ans = min(ans, dis[i][j]);printf("%lld\n", ans);}return 0;
}本题总结
本题的核心在于几个点
- 想到建分层图
总结
这次大部分题目都是实现问题。
下次考试要注意几个点：
- 合理分配时间
- 每道题目如果没有把握一次想出，先打好暴力
- 写代码之前先想好要写什么