专栏文章

CSP-J/S2025第二轮游记

lliuyi0905
生活·游记参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min8h5od
此快照首次捕获于
2025/12/01 22:17
3 个月前
此快照最后确认于
2025/12/01 22:17
3 个月前
查看原文
全机房只有我 J 组没 AK 是我的问题吗🤣
S 组挂了 4040 分，218218，好在还是上了一等线，终于有蓝勾了。还记得去年 CSP-S 斩获 150150 的高分，被所有人嘲讽。

Day -41

初赛。
啥都忘了，上次复习初赛还在上次。随便刷了几套卷子，发现真的啥都忘了。但也懒得管太多，毕竟能过就行，可要是真没过就老实了😑
为什么感觉 J 组的比 S 组的还难不少？最后以 J 组 90.5 和 S 组 92.5 的成绩拿下初赛。

Day -1

上午，考前最后一场模拟赛了，信心赛。A 是简单模拟，B 是小学数学，C 是结论，D 是小贪心。我当然也拿到了 200- 的好成绩，算是给 CSP 攒 rp 了。
下午打了 CCH 杯 ICPC 邀请赛，前三小时以仅仅一发罚时的优势稳在榜一，后来有许多巨佬超过了我们。死磕最后一道数学题，但拼尽全力无法战胜。最后以四道题拿下榜四，获得两包鸡腿👏
下课后就又和同学们在雅礼踢球了，结果被没素质的高中生们把场抢走了😒 只好跑去打排球，可时隔两个月没打，啥都忘了，但也只能慢慢找回手感。过了一会发现有场了，又去踢球了。打了好几个死角，我真是太有实力了😁

Day 0

听说又是赛前动员，结果是过来搞了两个小时卫生。本来 10:3010:30 的大会，硬生生拖到了 11:5011:50。动员大会具体讲了什么都没太听进去，好像就是讲了一些基础知识和注意事项。
下午放假，回家复习了一会模板，什么树链剖分、平衡树、主席树的都看了看，可没复习字符串，却只是想着要是考了串串就 **** CCF 没想到真的考了啊 然后进 florr 把卡全合了，没想到 5=1 super iris，RP -= inf 😭 大悲
晚上很早就睡觉了（其实并非），给明天留足精力。总是在想着要是明天没考好怎么办，是不是几个月所有努力全都白费了。

Day 1

早上很早就起来了，复习了一下就坐上了校车，发现考场就是上次的地方，离学校并不很远，不一会就到了。到那里先是研究了一下机子，发现有 Google 的小恐龙、Edge 的网上冲浪和纸牌，还有 CodeBlocks 的贪吃蛇和俄罗斯方块，好多游戏😝 反正是 J 组，老师也不看成绩，随便打打就是了。
8:208:20，调了一下 Dev-C++ 的设置，建好文件，静静等待试题的下发。8:408:40，终于把密码发了下来，看了眼题目，果真很简单，直接开写了好吧。
T1 简单模拟，将 ss 中的数字从大到小排序后输出，两分钟切掉。感觉只有红，但考虑到要排序（排序模板是橙题），估计有橙。
拼数 / numberCPP
#include <bits/stdc++.h>
using namespace std;
string s;
vector<char> a;
int main() {
  freopen("number.in", "r", stdin);
  freopen("number.out", "w", stdout);
  cin.tie(0)->sync_with_stdio(0);
  cin >> s;
  for (char c : s)
    c >= '0' && c <= '9' && (a.push_back(c), 1); 
  sort(a.begin(), a.end(), greater<char>());
  for (char c : a) cout << c;
  return 0;
}
T2 也是简单模拟，可是犯了些唐氏错误，导致 5 分钟才写出来。直接记录下小睿融排序后的位置，按照题目给定顺序模拟（其实可以直接算，可懒得写了）。甚至不太明白为什么 1≤n,m≤101 \le n, m \le 10，也是个 CCF……
他为什么是输出列和行啊，怎么不是行和列？
座位 / seatCPP
#include <bits/stdc++.h>
using namespace std;
int n, m, a[105];
int main() {
  freopen("seat.in", "r", stdin);
  freopen("seat.out", "w", stdout);
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m;
  for (int i = 1; i <= n * m; i++) cin >> a[i];
  int x = a[1], t;
  sort(a + 1, a + n * m + 1, greater<int>());
  for (int i = 1; i <= n * m; i++) a[i] == x && (t = i);
  int i = 1, j = 1;
  for (int k = 1; t > 1; t--) {
    (!(i + k) || i + k > n) ? (j++, k = -k) : (i += k);
  }
  cout << j << " " << i;
  return 0;
}
感觉 T3 上了点难度了，可认真读完题才发现还是一道 zrr 题目。因为区间都不相交且要选出尽可能多的，所以应该是直接模拟。可感觉不太保险，只好写了 dp（我有点脑抽）：
fif_i 表示前 ii 个数中能选出的最大区间数量，gi,jg_{i, j} 表示到了第 ii 个数且前缀亦或和为 jj 能选出的最大区间数量。状态转移方程就是这样：
{fi=max⁡(fi−1,gxi⊕k+1)gxi=max⁡(gxi,fi)\begin{cases}f_i = \max(f_{i - 1}, g_{x_i \oplus k} + 1)\\g_{x_i} = \max(g_{x_i}, f_i)\end{cases}
异或和 / xorCPP
#include <bits/stdc++.h>
using namespace std;
const int N = (1 << 20);
int n, k, a[N], f[N], g[N];
int main() {
  freopen("xor.in", "r", stdin);
  freopen("xor.out", "w", stdout);
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> k;
  fill(g, g + N, -1), g[0] = 0;
  for (int i = 1; i <= n; i++) {
    cin >> a[i], a[i] ^= a[i - 1];
    f[i] = max(f[i - 1], g[a[i] ^ k] + 1), g[a[i]] = max(g[a[i]], f[i]);
  }
  cout << f[n];
  return 0;
}
才过十多分钟，就过三道题了？这次也太水了吧。可 T4 就没那么简单了，并没有想到怎么做，就先花 55 分钟写了一个 8080 分暴力就直接睡觉去了（bushi
后来睡醒了，发现只有半个多小时了，饶有兴趣的玩起了俄罗斯方块，你别说还真挺好玩的。还玩了会小恐龙，还是太菜了啊，最多也就到三千多就死了。顺带看了眼旁边的小朋友，他居然过了两道题！可我再一看发现他子文件夹全都叫题目名称 + .cpp，哈哈哈又有一个爆零人了，善良的我并没有提醒他😈
考完后发现 wssb，他们全都 AK 了，就我 380380？原来 T4 是弱智题，方案大于 max⁡ai\max a_i 的全都不用关心具体多长，当成 50015001 算就可以了😫
多边形 / polygonCPP
#include <bits/stdc++.h>
using namespace std;
const int N = 5005, M = 998244353;
int n, m = 5001, a[N], f[N], s;
int main() {
  freopen("polygon.in", "r", stdin);
  freopen("polygon.out", "w", stdout);
  cin.tie(0)->sync_with_stdio(0);
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i];
  sort(a + 1, a + n + 1), f[0] = 1;
  for (int i = 1; i <= n; i++) {
    for (int j = m; j > a[i]; j--) s = (s + f[j]) % M;
    for (int j = m; j >= m - a[i]; j--) f[m] = (f[m] + f[j]) % M;
    for (int j = m - 1; j >= a[i]; j--) f[j] = (f[j] + f[j - a[i]]) % M;
  }
  cout << s;
  return 0;
}
我怎么没有写出来😭😭😭😭😭😭😭😭😭 都怪 zrr 😡
中午回家了，吃完饭，又继续复习了一会算法，还看了一些以前的笔记。一整个中午不一会就过去了，出去买了包巧克力和口香糖。
到校门口发现好多同学都在那，初一到高一的都有，几个教练也在那里。tkw 的考号是 HN-S01234，有趣极了。互相祝福了一下 rp++，就都进去了。
终于等到了 2:302:30，开题了！不会吧，怎么 T1 就这么难？不过思考片刻，想到一个简单的贪心做法，不过测完样例后发现假了。今天不会就要交代在 T1 了吧？那我怎么还有脸去机房啊。仔细思考了半小时，想到一个有点复杂的反悔贪心。因为最大人数为 n2\frac{n}{2}，所以会有许多性质，不需要讨论那么多情况。
  1. 对于一个人，先将他放入满意度最大的社团中，若人未满，那么 very good👍。
  2. 若那个社团人满了，则考虑需不需要踢人。设一个人的贡献为最大元素减去其他两元素的最大值，即 a1−max⁡(a2,a3)a_1 - \max(a_2, a_3)。注意到，若新来的人的贡献比原来的人中贡献最小的人的贡献高，那么将新人放入，将旧人踢出。
  3. 只不过模拟起来细节有点多，容易趋势😨
历经半小时终于调出恶心的代码，大样例都过了，能不能 AC 都看造化了
社团招新 / clubCPP
#include <bits/stdc++.h>
using namespace std;
using Pii = pair<int, int>;
using Arr = array<int, 3>;
const int N = 1e5 + 5;
int t, n, a[N][3], c[3];
Pii x[3];
int main() {
  freopen("club.in", "r", stdin);
  freopen("club.out", "w", stdout);
  cin.tie(0)->sync_with_stdio(0);
  for (cin >> t; t; t--) {
    cin >> n;
    for (int i = 1; i <= n; i++)
      cin >> a[i][0] >> a[i][1] >> a[i][2];
    priority_queue<Arr, vector<Arr>, greater<Arr>> q[3];
    int s = c[0] = c[1] = c[2] = 0;
    for (int i = 1; i <= n; i++) {
      for (int j = 0; j < 3; j++) x[j] = {a[i][j], j};
      sort(x, x + 3, greater<Pii>());
      int p = x[0].second, w = x[0].first - max(x[1].first, x[2].first);
      if (c[p] < n / 2) {
        q[p].push({w, i, x[0].first}), c[p]++;
      } else if (w > q[p].top()[0]) {
        Pii v[3];
        for (int j = 0; j < 3; j++) v[j] = {a[q[p].top()[1]][j], j};
        sort(v, v + 3, greater<Pii>());
        c[v[1].second]++;
        q[v[1].second].push({0, q[p].top()[1], v[1].first});
        q[p].pop(), q[p].push({w, i, x[0].first});
      } else {
        c[x[1].second]++;
        q[x[1].second].push({0, i, x[1].first});
      }
    }
    for (int i = 0; i < 3; i++)
      for (; q[i].size(); q[i].pop()) s += q[i].top()[2];
    cout << s << "\n";
  }
  return 0;
}
看到 T2，感觉是一道很简单的题。很快发现是看错题了，浪费半个小时🙄 我也是个人物。后来才彻底理解题目，知道暴力应该是 O(2k(m+nk)log⁡(m+nk))\mathcal{O}(2^k (m + nk) \log (m + nk)) 的暴力 MST。
突然发现是不是可以最开始跑一个 MST 预处理，后面直接 O(2knklog⁡nk)\mathcal{O}(2^k nk \log nk)，不过我很快的否定的这种思路（焯，这就是正解……）感觉要用什么状压或者一些奇奇怪怪的东西，可想破脑袋也不知道怎么做。只好放弃😫，看了看部分分，发现并不是很充足，不太会。
T3。怎么是串串？！CCF 你！@#￥%……&*（）早知道复习一下了，生无可恋……还是只能硬着头皮去做，完全不会，只想到了一个 O(nL2)\mathcal{O}(n L^2) 的暴力哈希做法，感觉有 3030 分，先写出来再说🤔
过了一会发现特殊性质 B 也可以做，写出来后大样例过了，估计有 5050 分，但我为什么总感觉会挂。
谐音替换 / replaceCPP
#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
const int N = 2e5 + 5, D = 5e6, M = D + 5, B = 13331;
int n, q;
ull pw[M], H1[M], H2[M];
unordered_map<ull, int> z;
vector<pair<int, int>> p[M * 2];
string s[N][2], t[N][2];
int main() {
  freopen("replace.in", "r", stdin);
  freopen("replace.out", "w", stdout);
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> q;
  bool f = 1;
  for (int i = 1; i <= n; i++) {
    cin >> s[i][0] >> s[i][1];
    int v = 0;
    for (char c : s[i][0]) c == 'b' ? v++ : f &= c == 'a';
    f &= v == 1, v = 0;
    for (char c : s[i][1]) c == 'b' ? v++ : f &= c == 'a'; 
    f &= v == 1;
  }
  for (int i = 1; i <= q; i++) {
    cin >> t[i][0] >> t[i][1];
    int v = 0;
    for (char c : t[i][0]) c == 'b' ? v++ : f &= c == 'a';
    f &= v == 1, v = 0;
    for (char c : t[i][1]) c == 'b' ? v++ : f &= c == 'a';
    f &= v == 1;
  }
  if (f) {
    for (int i = 1; i <= n; i++) {
      int p1, p2;
      for (int j = 0; j < s[i][0].size(); j++) s[i][0][j] == 'b' && (p1 = j);
      for (int j = 0; j < s[i][1].size(); j++) s[i][1][j] == 'b' && (p2 = j);
      p[p1 - p2 + D].push_back({p1, s[i][0].size() - p2});
    }
    for (int i = 1; i <= q; i++) {
      int p1, p2;
      for (int j = 0; j < t[i][0].size(); j++) t[i][0][j] == 'b' && (p1 = j);
      for (int j = 0; j < t[i][1].size(); j++) t[i][1][j] == 'b' && (p2 = j);
      int v = 0;
      for (pair<int, int> k : p[p1 - p2 + D])
        v += k.first <= p1 && k.second <= t[i][0].size() - p2;
      cout << v << "\n";
    }
  } else {
    for (int i = pw[0] = 1; i <= D; i++) pw[i] = pw[i - 1] * B;
    for (int i = 1; i <= n; i++) {
      ull h1 = 0, h2 = 0;
      for (char c : s[i][0]) h1 = h1 * B + c;
      for (char c : s[i][1]) h2 = h2 * B + c;
      z[(h1 * pw[s[i][0].size()] + '#') * B + h2]++;
//      cout << (h1 * pw[s[i][0].size()] + '#') * B + h2 << "\n";
    }
    for (int i = 1; i <= q; i++) {
      int m = t[i][0].size();
      t[i][0] = " " + t[i][0], t[i][1] = " " + t[i][1];
      for (int j = 1; j <= m; j++) H1[j] = H1[j - 1] * B + t[i][0][j];
      for (int j = 1; j <= m; j++) H2[j] = H2[j - 1] * B + t[i][1][j];
      int v = 0;
      for (int l = 1; l <= m; l++) {
        ull h1 = 0, h2 = 0;
        for (int r = l; r <= m; r++) {
          h1 = h1 * B + t[i][0][r];
          h2 = h2 * B + t[i][1][r];
//          cout << l << " " << r << " " << (h1 * pw[r - l + 1] + '#') * 13331 + h2 << " " << z[(h1 * pw[r - l + 1] + '#') * B + h2] << "\n";
          H1[l - 1] * pw[m - l + 1] + h2 * pw[m - r] + H1[m] - H1[r] * pw[m - r] == H2[m] && (v += z[(h1 * pw[r - l + 1] + '#') * B + h2]);
        }
      }
      cout << v << "\n";
    }
  } 
  return 0;
}
回来看 T2。考前听 cch 说 CCF 的机子现在 1s 可以跑 10910^9，这倒是提醒了我。也不知道脑子哪里出了问题，突然发现可以离散化+桶排？什么新奇的排序方式😰 不过还是得尝试一下的吧，毕竟时间复杂度 O(2km)O(2^k m)，卡线 10910^9！
兴奋的我十分钟就写出来了，发现原本要跑 529s 的大样例（别问我是怎么知道的），现在只需要跑 0.8s 了！太好了，也算是过了两道题了。不过总还是有点紧张，毕竟不是很确定到底能不能过。
道路修复CPP
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 1e4 + 5, M = 1e6 + 5, K = 15, F = M + N * K;
LL n, m, k, l, t, c[K], a[K][N], f[N + K], r = 1e18, vl[F];
unordered_map<int, int> h;
vector<pair<int, int>> q[F];
array<LL, 3> e[M], g[F];
int R(int x) {
  return f[x] == x ? x : f[x] = R(f[x]);
}
LL S(int C) {
  LL s = 0, z = 0;
  for (int i = 0; i < k; i++) {
    if (!((C >> i) & 1)) continue;
    s += c[i], z++;
    for (int j = 1; j <= n; j++)
      q[a[i][j]].push_back({n + i + 1, j});
  }
  iota(f + 1, f + n + k + 1, 1);
  for (int r = 1, j = 1; r <= t; r++)
    for (auto i : q[r]) {
      int u = R(i.first), v = R(i.second);
      u != v && (f[u] = v, j++, s += vl[r]);
      if (j == n + z) {
        for (int x = 0; x < k; x++)
          for (int y = 1; y <= n && ((C >> x) & 1); y++) q[a[x][y]].pop_back();
        return s;
      }
    }
}
int main() {
  freopen("road.in", "r", stdin);
  freopen("road.out", "w", stdout);
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m >> k;
  for (int i = 1; i <= m; i++) {
    cin >> e[i][1] >> e[i][2] >> e[i][0], vl[++t] = e[i][0];
  }
  for (int i = 0; i < k; i++) {
    cin >> c[i];
    for (int j = 1; j <= n; j++) cin >> a[i][j], vl[++t] = a[i][j];
  }
  sort(vl + 1, vl + t + 1);
  t = unique(vl + 1, vl + t + 1) - vl - 1;
  for (int i = 1; i <= m; i++) {
    e[i][0] = lower_bound(vl + 1, vl + t + 1, e[i][0]) - vl;
    q[e[i][0]].push_back({e[i][1], e[i][2]});
  }
  for (int i = 0; i < k; i++)
    for (int j = 1; j <= n; j++)
      a[i][j] = lower_bound(vl + 1, vl + t + 1, a[i][j]) - vl;
  for (int v = 0; v < (1 << k); v++) r = min(r, S(v));
  cout << r;
  return 0;
}
还是又去想想 T3，可还是未能突破。上了个厕所回来，突然发现只剩 2020 分钟了，T4 匆忙打了个 88 分的大暴力，其他许多性质都没想（本来是有 2424 分的啊）最后 1010 分钟，检查了一下文件和 freoepn，坐等比赛结束。
没想到这么快就过去了。
估分：100+100+50+8=258100 + 100 + 50 + 8 = 258。
考完后问了下其他人，好像人均 200+，考的好像都还不错。但过这次题目确实比去年的难了不少，笑点解析：NOIP2024 蓝绿紫紫，CSP-S2025 绿蓝紫紫。这次 1= 应该是稳了的，只要不犯一些奇奇怪怪的错误。
细节：
J 组密码：上善若水（上午很水）
S 组密码：人杰地灵（人均爆零）

Day 5

成绩出了，100+80+30+8=218100 + 80 + 30 + 8 = 218。
其实看到成绩的第一眼还是挺高兴的，毕竟 T1 还好过了，T2 被卡理所当然，T3 也没觉得能有 5050。问了下其他人的，这个成绩好像并不算非常差，也不算非常好，能不能打 NOIP 也就随缘了。
👏热烈庆祝 lzh 同学 T3 喜提 CE（你怎么知道算上模拟赛后这是他第四次 CE 了）👏
😞沉痛悼念 zrr 同学因为太可爱了，一道题都没做出来，只得到了 7171 分😞

后记

有趣的事。打 NOIP 的分数线是 218218，而我考了多少呢🤔😂
和 hke、xbc、wyn、lrh、cyx、hhc 巨佬们一起去集训了，他们都那么强，就我那么菜，总感觉有点不合群……还好一考完期中就停课了，不然在学校出了成绩怕是要被老尸们骂死的（
这次我们初二貌似还没有考过初一，为什么初一他们考的那么高啊😲😲😲😲
补了一下 S 组 T2，把 mm 条边跑 MST 筛出 n−1n - 1 条边，用原来的方式交了一下：
饿啊！为什么还卡常😡😡😡 也是直接把 push_back 改成 emplace_back 好吧，终于 AC。实在是有点想骂出题人……要是考场写出来 9696 分我会~！@#￥%……&*（）

结

NOIP，加油！

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...