游记 - CSP 2023

hopeful_imitation · 2023-10-22 12:58:08 · 生活·游记

游记 - CSP 2023

J 组和 S 组双料选手。

初赛

J 94.5，S 82。基本没复习，只做了 0.76 套模拟题。被各同学薄纱。

复赛

Day [-14,-1]

开训。

开雀！

开某款 Gen 开头的游戏！

Day 0 Morning: Junior

2023.10.21.

看完题，本来打算先全部口胡完再写，结果愣卡在 T4。一开始就想到对每个点维护 \bmod k 的每个余数的最短路，然后又觉得好像不好转移，卡在 O((n+m)a) 的建图。觉得受不了，先把前三题写了。

前三题还是要动动脑子才能写：第一题发现每次减去三分之一向上取整是可以做的；第二题本来以为 DP，再想了想应该是从前往后简单贪心一下；第三题模拟，一开始没有发现要处理 sqrt(1)，还是有细节的。还有一些变量名写错这类细节问题……花了一点点时间。

快 10:00 了，突然开窍，发现最短路 +k 总是合法，然后就做完了。写了 O(mk\log mk)，想了想，如果实现精细可能可以 O(mk\log nk) 这种东西，但觉得不是很值，就不写了。然后上厕所，然后拍 T1。有点怕 T4 常数大，因为最短路算法好像不是普及组算法。

Day 0 Afternoon: Senior

看完 T1，蒙的，怎么比 Junior T1 还简单？反复确认几遍，好像暴力即可……

大概扫了一遍题，发现 T2 好像不是很浅显，T4 应该是树上问题，要动脑子，T3 不用。所以写完 T1 就搞 T3。

T3 写完大概已经赛了 2h 了。中间就是那个对齐的规则没有读对，修改了几回，上个厕所。看了眼 T4，好像是简单，把变化的函数写一下，感觉不难，就先放放，动动脑子想 T2。

想 T2，一开始只想到 O(n^3)，做类似括号序列的东西。然后手模了一种 O(n^2)，就是维护 n 个栈，逐个看栈顶相同就删，不同就加。当时还没有细细证明过就觉得这是对的了，也不知道怎么想的。上个厕所，想怎么进一步优化，就想到每个右端点的答案是往左走删空的左端点数目，然后就像字符串结构一样维护 fail 指针之类的东西，再把它优化到单次查询 O(1)，记录每个字母的最靠右的左端点。时间就是 O(n|\Sigma|)。感觉很灵光一现，然后理理细节，写掉了。此时赛程还有 1h，可以计算在本题有 0.5h 想题，0.5h 写代码。

T4 觉得长得比较二分，然后就做完了。这是我第三回上厕所，水喝多了属于是。写完还有 15min，然后怕 __int128_t 过不了编，写了：

#ifdef __int128_t
typedef __int128_t lll;
#else
typedef long long lll;
#endif

结果丢到 Linux 一测，给我爆 long long。整个人恍惚的，根本来不及手敲 __int128，最后删掉 _t 然后结束考试。

感觉 400 分场，T4 打成这样也没话说了。给大家表演一个 400 变 300。

Day 0 Evening

听说 S T2 有原？还是我听课有听到的原？？虽然猜到，但真的一点没印象啊。

估分，Junior 小图灵和 Luogu 是 400，云斗上面 T4 测了 25，爆 Segmentation Fault，有点神秘。

Senior 前三题在 Luogu 和云斗都能过，T4 直接交，云斗上面 5，Luogu 上面 30。

然后当我把上面那一段改成：

// #ifdef __int128_t
typedef __int128_t lll;
// #else
// typedef long long lll;
// #endif

云斗上变 35，Luogu 上变 90。一搜，#ifdef 只检查宏定义，不检查某个东西是不是真的被定义了。所以它一定会使用 long long……

另外，把第四行的 long long 改成 long double，在 Luogu 也能拿到 90，double 是 85。

给大家表演一个不会 C++。

但还是觉得云斗有点神秘。

小图灵 S 更神秘了：100+95+100+0，T2 WA 一个点。

一段训练之后有一种感觉，感觉自己的思维逐渐模糊迷蒙，不那么具体和有理，不知道好不好。可能会把一些比较无理的想法也说了，表达也喜欢感性表达，写题也感性理解。以及，晚上思考感觉比较无理，上午还犯困。

好像还是缺少一点快速代码的能力。感觉这两场的难处主要在于代码能力，思维最难可能是 S 组 T2。

Day 8 结论

J：100+100+100+100=400。

S：100+90+100+25=315。

J 还是稳，没留遗憾。所以云斗怎么把 T4 挂成 25？

然后给大家讲述如何从 315 调成 400：

第一步，T2 90 变 100：

for (int i(1); i <= N; ++i) {
  // ...
  if (~fal[i]) {
    // ...
    if (i); // correct: if (fal[i]);
  }
}

纯粹变量打错，看一下都知道不合理啊，i 从 1 开始，if (i) 恒成立啊。

实际结果：19、20 两组数据的输出比答案小 2。

第二步，T4 25 变 85：

#ifdef __int128
typedef __int128 lll;
#else
typedef long long lll;
#endif
// correct: typedef __int128 lll;

第三步，T4 85 变 100：

for (int i(1), u(0), v(0); i != N; ++i)
  scanf("%d%d", &u, &v), addedge(u, v), --u, --v;
// correct: scanf("%d%d", &u, &v), --u, --v, addedge(u, v);

解释：大部分情况下，我习惯从 0 开始计下标，下文以 0 为根 dfs，数每个点儿子个数。如果这么写，每个点都和 0 不联通，因此每个点的儿子个数都是 0。原来这样写，三组数据输出比答案小 1。

总结好处坏处：

严谨。这可以有效保证正确性。
思维活络。以尽可能解开难题。
粗心，写代码动脑子手脚不协调。也许可以做一些有意义的事情来避免，比如玩原神。
不知道 #ifdef 只检查宏，不是检查任何名称。不敢咬定 __int128 能过编。错一次就记住了。长期地，我开始学用 vim，在 Linux 环境下编程，图保险。
审题不够细致，尤其是本次的模拟题。这也会浪费时间。我认为这是性格，不过状态冷静理智的时候也可以避免。