CSP-S 2025 游记
normalpcer · · 生活·游记
坐标 JL，退役 OIer。在 whk 之余，突发奇想，决定为可能是我最后一场的 CSP-S 留下些文字。
故地重游，初赛和复赛居然都在去年的考场。别有一番趣味。
初赛
92.5 分。
感觉题目做着还算顺利。印象比较深的是一处让在 false 和 0 中做选择。在这里真的都可以吧。考虑到定义的时候类型是 int，于是选择了后者。
我不喜欢这道题目。
复赛
Day -1
大练习挂分了。没关系，就当是给 CSP 运气守恒了。
翻一翻自己之前写过的代码吧，结果发现提交了七八页的洛谷愚人节比赛的代码。
之前写的代码注释里面有“涉及到”，这个是病句。
Day 1
考前突然听说，这次 CSP 再次升级了评测机，把杜先生玩原神的机子拿出来评测了，比 LOJ 还快。评测机都升了，能不能上 C++23/GCC15 啊。
同学去年省选还在考场上打 Pollard-Rho，今年光顾着看 ntt，忘了复习了。
不过，更严峻的问题还是，差点没找到考场的入口。不过最后还是准时进入了考场。
简单检查一下电脑，建完文件夹。解压密码是人杰地灵。
T1
大概看了一下题目。每个部门的成员数量，至多是总人数的一半，所以可以注意到，一定不会有人沦落到选择第三志愿。
嗯，那么看起来是一个贪心。需要把几个人调配到第二志愿，希望满意度最大，那么应该优先满足第一志愿优势更大的人。只需要按照一二志愿的满意度差值排序，然后逐个分配，如果人数超限就调到第二志愿。仔细想了想，这个贪心策略应当是正确的。
写一下代码。代码还是好写的，大概 20 分钟顺利通过大样例。
:::info[club.cpp]
#include <bits/stdc++.h>
#define FILE_NAME "club"
using i32 = std::int32_t; using u32 = std::uint32_t;
using i64 = std::int64_t; using u64 = std::uint64_t;
/*
多测说是。
直接贪心，随便搞。
100
*/
namespace Solution {
namespace {
char constexpr endl = '\n';
auto solve() -> void {
i32 n; std::cin >> n;
std::vector<std::array<i32, 3>> a(n);
for (auto &x : a) {
for (auto &y : x) std::cin >> y;
}
std::vector<std::pair<i32, std::array<std::array<i32, 2>, 3>>> sorted;
sorted.reserve(n);
for (auto &x : a) {
std::array<std::array<i32, 2>, 3> tmp{};
for (i32 i = 0; i < 3; ++i) {
tmp[i] = {x[i], i};
}
std::sort(tmp.begin(), tmp.end(), std::greater<>{});
sorted.emplace_back(tmp[0][0] - tmp[1][0], tmp);
}
std::sort(sorted.begin(), sorted.end(), std::greater<>{});
std::array<i32, 3> cnts{};
i64 ans = 0;
for (auto [_, favor] : sorted) {
if (cnts[favor[0][1]] >= n / 2) {
++cnts[favor[1][1]];
ans += favor[1][0];
} else {
++cnts[favor[0][1]];
ans += favor[0][0];
}
}
std::cout << ans << endl;
}
}
}
auto main() -> int {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::freopen(FILE_NAME ".in", "r", stdin);
std::freopen(FILE_NAME ".out", "w", stdout);
i32 t; std::cin >> t;
while (t --> 0)
Solution::solve();
return 0;
}:::
得分：
T2
读错题了。
一开始，并没有注意到“城市”和“乡镇”是两个概念，以为是从已经有的节点中选择几个改造，并且改造之后可以连接新的边。同时当时也没有想到，正解的复杂度就是带
想了一个假做法，甚至已经快写完了。然后突然想到这个做法不太对，拿笔画了一下，发现确实想假了。
有些慌张。决定先去看看 T3（见后文），然后又回来打了一个比较暴力的做法。
状压枚举所有要城市化的乡镇，然后把对应的边合并到原图上跑最小生成树。很好想很暴力的做法，但是有不少分了。然后突然想到可以给原图的边预先排序，然后再合并有序数组，可以稍微快一些。
（我当时并没有意识到，其实原图上只有最小生成树的边是有用的）
这里本来以为可以获得
然后又顺手拼了一个性质分，这个时候城市化不需要代价，只需要都连到原图上跑最小生成树。能多拿到
:::info[road.cpp]
// #define _GLIBCXX_DEBUG 1
// #define _GLIBCXX_SANITIZE_VECTOR 1
#include <bits/stdc++.h>
#define FILE_NAME "road"
using i32 = std::int32_t; using u32 = std::uint32_t;
using i64 = std::int64_t; using u64 = std::uint64_t;
/*
就是，最小生成树，但是，有若干条边，需要先点亮一个特殊节点，才可以连接。
K 很小。但是指数枚举还是远远不够。
怎么感觉还是可以贪心。
考虑点亮一个特殊节点可以获得多少收益。
首先，点亮他的价格是一个固定的支出。
接下来，计算从这个点到所有节点的最短路。
如果这个最短路，比不上这条直连道路，那样这条路就是稳赚不亏的。
如果总收益大于支出，就点亮它。
所以特殊节点的数量很少，因为从每个点开始都要跑一下最短路。
这就差不多了，但是时间复杂度，还是有一点危险。一秒？KQMlog(N)
我不知道啊。但就算过不去，分也不少，感觉也不是很难写。先实现一下吧。
坏了，好像有点想假了。
坏了，读错题了。城市和乡镇是独立计数的。也就是乡镇和乡镇不会进一步连边了。这好像稍微简单了一些。
先打一个暴力吧。枚举改造的城镇。
好消息是，除了MK都是满的数据以外，都能顺利通过。可以获得64分。
还能再凑一个性质分。如果所有的城镇改造都不花钱，可以直接最小生成树。这值8分。
64+8=72
*/
namespace Solution {
namespace {
char constexpr endl = '\n';
class DSU {
public:
std::vector<i32> pa, size;
DSU(i32 n): pa(n + 1), size(n + 1, 1) {
for (i32 i = 1; i <= n; ++i) pa[i] = i;
}
auto find(i32 u) -> i32 {
if (pa[u] == u) return u;
else return pa[u] = find(pa[u]);
}
auto add(i32 u, i32 v) -> void {
if (size[pa[u]] < size[pa[v]]) std::swap(u, v);
pa[pa[v]] = pa[u];
size[u] += size[pa[v]];
}
};
auto popcount(u32 x) -> i32 {
return __builtin_popcount(x);
}
auto solve() -> void {
i32 n, m, k; std::cin >> n >> m >> k;
std::vector<std::array<i32, 3>> edges(m);
for (auto &[len, x, y] : edges) {
std::cin >> x >> y >> len;
}
std::sort(edges.begin(), edges.end());
std::vector<i32> c(k + 1);
std::vector<std::vector<i32>> add_cost(k + 1, std::vector<i32>(n + 1));
bool all_free = true;
for (i32 p = 1; p <= k; ++p) {
std::cin >> c[p];
if (c[p] != 0) all_free = false;
for (i32 i = 1; i <= n; ++i) {
std::cin >> add_cost[p][i];
}
}
auto krusk = [&](std::vector<std::array<i32, 3>> const &final_edges, i32 n) -> i64 {
DSU dsu{n + k};
i64 cur_ans = 0;
for (auto [len, u, v] : final_edges) {
if (dsu.size[dsu.find(1)] == n) break;
if (dsu.find(u) == dsu.find(v)) continue;
dsu.add(u, v);
cur_ans += len;
}
return cur_ans;
};
i64 ans = 0x3f3f3f3f3f3f3f3fLL;
for (u32 st = 0; st != (1 << k); ++st) {
if (all_free && st != (1 << k) - 1) continue;
std::vector<std::array<i32, 3>> new_edges;
auto sel = popcount(st);
i64 ex_cost = 0;
new_edges.reserve(sel * n);
for (i32 i = 1; i <= k; ++i) {
if ((1 << (i - 1)) & st) {
ex_cost += c[i];
for (i32 j = 1; j <= n; ++j) {
new_edges.push_back({add_cost[i][j], n + i, j});
}
}
}
std::sort(new_edges.begin(), new_edges.end());
std::vector<std::array<i32, 3>> final_edges(m + sel * n);
std::merge(edges.begin(), edges.end(), new_edges.begin(), new_edges.end(), final_edges.begin());
auto cur_ans = krusk(final_edges, n + sel);
ans = std::min(ans, cur_ans + ex_cost);
}
std::cout << ans << endl;
}
}
}
auto main() -> int {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::freopen(FILE_NAME ".in", "r", stdin);
std::freopen(FILE_NAME ".out", "w", stdout);
Solution::solve();
return 0;
}:::
得分：
T3
在 T2 想假的时候，读了一下 T3 和数据范围。注意到这个 B 性质似乎很有趣，因为在这个条件下，“特殊”的字符串完全可以通过左右字母 a 的数量来描述。也就是说，我们把一个字符串，转换成了整数的运算。
然后发现，进行字符串替换的过程，可以通过字母 b 的位置变化来描述。这样在一次查询的时候，我们只需要在库中寻找一个替换方案，使得这样替换的位置变化为希望的值。然后又发现，如果这个替换方案过长，那么也是无法进行替换的。
记字符串的左侧有 la 个、右侧有 ra 个字母 a。对于每一次查询 s -> t，相当于要在库中寻找有多少个替换方案 x -> y 满足以下三个限制：
x.la - y.la = s.la - t.la
x.la <= s.la
x.ra <= s.ra（这里源代码注释写得有点问题）
所以它本质上是一个二维偏序问题。用树状数组即可解决。B 性质的
T2 写完之后，实现了 T3 的这部分代码，经过一些调试，也顺利地通过了大样例。
后来写完 T4 暴力回来，我又想到，普通的字符串是否有方法描述一个变化量？我想到了哈希。但是我并没有意识到，直接给哈希值作差是不可取的。同时这个部分，我也分析错了复杂度，以为它只能用来解决暴力和性质 A。所以考场上以为这样可以多得
:::info[replace.cpp]
#include <bits/stdc++.h>
#define FILE_NAME "replace"
using i32 = std::int32_t; using u32 = std::uint32_t;
using i64 = std::int64_t; using u64 = std::uint64_t;
/*
看起来这个题的 B 性质也很好写。
待会来拼一拼。
预处理一下，字母B左右的，A的数量
然后是一个二维偏序，计数：
x.la <= la
x.ra <= ra
x.ra - x.la = ra - la
唉写一下暴力。
好像哈希一下就可以了？
我在做什么！这个匹配似乎完全可以logN以内的复杂度解决。
所以A性质的分也是可以得到的。
我的天呐。好智慧。暴力和A性质分拿到。不过需要求逆元，改用双mod哈希。
25+10+25=55
*/
namespace Solution {
namespace {
char constexpr endl = '\n';
class BIT {
struct Node {
i32 val = 0, time = 0;
};
i32 now = 0;
std::vector<Node> c;
auto static constexpr lowbit(i32 x) -> i32 { return x & -x; }
public:
BIT(i32 n) : c(n + 1) {}
auto add_at(i32 x, i32 val) -> void {
++x;
while (x < (i32)c.size()) {
if (c[x].time != now) c[x] = {0, now};
c[x].val += val;
x += lowbit(x);
}
}
auto sum_pre(i32 x) -> i32 {
++x;
i32 sum = 0;
while (x != 0) {
if (c[x].time != now) c[x] = {0, now};
sum += c[x].val;
x -= lowbit(x);
}
return sum;
}
auto clear() -> void { ++now; }
};
auto constexpr qpow(i64 a, i64 b, u32 mod) -> u32 {
i64 res = 1;
for (; b != 0; b >>= 1, a = a * a % mod) {
if (b & 1) res = res * a % mod;
}
return res;
}
i32 constexpr p0 = 998'244'353, p1 = 1'000'000'007, base = 131;
using hashed = std::array<i32, 2>;
auto operator- (hashed a, hashed b) -> hashed {
return {(a[0] - b[0] + p0) % p0, (a[1] - b[1] + p1) % p1};
}
auto solve_force(i32 n, i32 q) -> void {
auto hash = [&](std::string const &s) -> hashed {
u64 res0 = 0, res1 = 0, tmp0 = 1, tmp1 = 1;
for (auto ch : s) {
res0 += ch * tmp0, res0 %= p0;
res1 += ch * tmp1, res1 %= p1;
tmp0 *= base, tmp0 %= p0;
tmp1 *= base, tmp1 %= p1;
}
return {(i32)res0, (i32)res1};
};
std::vector<std::pair<hashed, i32>> a(n);
for (i32 i = 0; i < n; ++i) {
std::string s1, s2;
std::cin >> s1 >> s2;
a[i] = std::make_pair(hash(s2) - hash(s1), (i32)s1.size());
}
std::sort(a.begin(), a.end());
for (i32 i = 0; i < q; ++i) {
std::string s1, s2;
std::cin >> s1 >> s2;
auto q_len = (i32)s1.size();
i64 ans = 0;
auto t1 = hash(s1), t2 = hash(s2);
hashed tmp{1, 1};
for (i32 j = 0; j < q_len; ++j) {
i32 max_len = q_len - j;
u32 h0 = i64((t2[0] - t1[0] + p0) % p0) * qpow(tmp[0], p0 - 2, p0) % p0;
u32 h1 = i64((t2[1] - t1[1] + p1) % p1) * qpow(tmp[1], p1 - 2, p1) % p1;
auto to_find = hashed{h0, h1};
auto it0 = std::lower_bound(a.begin(), a.end(), std::make_pair(to_find, 0));
auto it1 = std::upper_bound(a.begin(), a.end(), std::make_pair(to_find, max_len));
ans += it1 - it0;
tmp[0] = i64(tmp[0]) * base % p0;
tmp[1] = i64(tmp[1]) * base % p1;
}
std::cout << ans << endl;
}
}
auto solve() -> void {
i32 n, q;
std::cin >> n >> q;
if (n <= 100 || q <= 1) return solve_force(n, q);
struct Item {
i32 la, ra, diff = 0;
auto operator< (Item const &y) const -> bool {
auto const &x = *this;
if (x.diff != y.diff) return x.diff < y.diff;
if (x.la != y.la) return x.la < y.la;
return x.ra < y.ra;
}
};
std::vector<Item> a(n);
std::vector<std::pair<Item, i32>> qs(q);
{
auto findb = [&](std::string const &s) -> i32 {
auto pos = s.find('b');
if (pos == s.npos) return (i32)s.size();
else return pos;
};
auto cmp2str = [&](std::string const &s1, std::string const &s2) -> Item {
auto f1 = findb(s1);
auto f2 = findb(s2);
auto diff = f2 - f1;
return {f1, (i32)s1.size() - f1 - 1, diff};
};
for (auto &x : a) {
std::string s1, s2;
std::cin >> s1 >> s2;
x = cmp2str(s1, s2);
}
for (i32 i = 0; i < q; ++i) {
std::string s1, s2;
std::cin >> s1 >> s2;
qs[i] = {cmp2str(s1, s2), i};
}
}
std::sort(qs.begin(), qs.end());
std::sort(a.begin(), a.end());
i32 constexpr max_ra = 1e7;
BIT bit{max_ra};
i32 prev_diff = -0x3f3f3f3f;
i32 j = 0;
std::vector<i32> ans(q);
for (i32 i = 0; i < q; ++i) {
auto [la, ra, diff] = qs[i].first;
auto index = qs[i].second;
if (diff != prev_diff) {
bit.clear();
while (j != n && a[j].diff < diff) ++j;
prev_diff = diff;
}
while (j != n && a[j].diff == diff && a[j].la <= la) {
bit.add_at(a[j].ra, 1);
++j;
}
ans[index] = bit.sum_pre(ra);
}
for (i32 i = 0; i < q; ++i) {
std::cout << ans[i] << endl;
}
}
}
}
auto main() -> int {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::freopen(FILE_NAME ".in", "r", stdin);
std::freopen(FILE_NAME ".out", "w", stdout);
Solution::solve();
return 0;
}:::
得分：
T4
打完了 T3 的 B 性质，打了一个 next_permutaion 的阶乘暴力。
:::info[employ.cpp]
#include <bits/stdc++.h>
#define FILE_NAME "employ"
using i32 = std::int32_t; using u32 = std::uint32_t;
using i64 = std::int64_t; using u64 = std::uint64_t;
/*
8
*/
namespace Solution {
namespace {
char constexpr endl = '\n';
auto solve() -> void {
i32 n, m;
std::cin >> n >> m;
std::vector<char> s(n);
std::vector<i32> c(n);
for (auto &x : s) std::cin >> x;
for (auto &x : c) std::cin >> x;
std::vector<i32> order(n);
for (i32 i = 0; i < n; ++i) order[i] = i;
i32 tot = 0;
do {
i32 denied = 0;
i32 cnt = 0;
for (i32 i = 0; i < n; ++i) {
auto p = order[i];
if (denied >= c[p] || s[i] == '0') ++denied;
else ++cnt;
}
if (cnt >= m) {
++tot;
}
} while (std::next_permutation(order.begin(), order.end()));
std::cout << tot << endl;
}
}
}
auto main() -> int {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::freopen(FILE_NAME ".in", "r", stdin);
std::freopen(FILE_NAME ".out", "w", stdout);
Solution::solve();
return 0;
}:::
得分：
赛后
考场上最后五分钟，调完了 T3 的 A 性质。当时测试的时候，是从大样例里面随便摘了几组询问，发现通过了。然后没时间，也没有心情来进一步验证它的正确性。
最后能够做的，也就是算一算自己的分数，然后想要在注释里写一些抒情的文字，但最终也没有落笔。最后检查了一下 freopen，比赛结束。
下了考场，我的估分居然已经在机房中很高了。正当自己踌躇满志的时候，偶然间得知，T3 的
Day ...
赛后的若干天，也没有过度思考这件事情，只是拜托同学把我考场上的 T3 想法进一步实现一下（不过很快就被 hack 掉了）。作为一名 whker，我需要把自己的精力投入到下一周的大练习，和再过几天的期中考试中。
幸运的是，最终的测试点并没有
尽管在考场上有各种失误和遗憾，也没有打出什么有太多“技术含量”的分数，但是最终的成绩还是差强人意的。
期中考试
没考过我前桌。
追忆
我和 OI 的缘分，说长也长，说短也短。
说长，可能是小学三四年级的时候。那时第一次在屏幕上敲出 Hello, World!，第一次学会为两个整数求和，屏幕上的字符，让我第一次切实体会到了，自己正在“创造”。只是此后许多年，它就一直被搁置在记忆的角落。
真正的相逢，在 2024 年 9 月。初三的我，来到 JDFZ 的机房，才第一次接触到真正的 OI。抽象的算法和思维，与一行行的代码相结合，造就了一个精彩绝伦的答案。我很喜欢这种感觉。
不久后我参加了 CSP-S 2024，当时在 T2 上写了很长时间，因为排序的一个符号搞错，已经没有时间调试，最后从
我也继续不断地学习着，时间也在其中不停地流逝。我也经历了 NOIP 和省选联考两场比赛的磨砺。
然而，不知从何时起，那份最初的好奇与兴奋，渐渐沉淀下来。我开始以一个更冷静的视角，重新审视自己与 OI 的关系。
总有一些山峰，并非单凭热爱即可登顶。总有一些鸿沟，划清了自己思维的边界和极限。
2025 年 5 月，我离开了机房，投入到中考的复习中。没有激烈的告别，此后，我便与你渐行渐远。
追忆，总在不经意间，将我裹进泛黄的纸页里。一点点堆叠出的代码，调试时发现错误的懊恼，直到最后成功 AC 的喜悦……我读出了，那个沉思的自己，那个欢呼的自己。
曾经的日子无法重来，我只不过是一个过客。但在记忆的星空中见证过的璀璨，足以照亮我未来的路途。
后会有期。