CSP-S 2023 游记-526互联

初赛部分

Day 1

真的有必要写吗？如有。

感觉还是要延续之前 CSP 游记的排版。

考前复习了半个小时初赛，优势在我。

好像迟到了一点点，监考员没有给我发试卷，但是给我发了两张知情同意书。睡觉。

出来对答案，错了几个，一个忘了有二分上下界，还有一个是 linux 下编译。

有人 NOI 考完之后忘了 g++ 怎么编译，猜猜他是谁呢？

92 分，还没有去年高，OI 生涯 AK 不了初赛力（悲

复赛部分

Day -2

上午模拟赛，第一次感受到了 \(\mathcal O(n^4)\) 能过 \(n=400\)，时限 1.5s。

T3 挂分了，就当攒 rp 了。T4 关键结论就差一步，不过反正没时间写了。

来点题。

求满足 \(kx \bmod y \in [l,r]\) 的最小非负整数解 \(k\)。

Solution

当 \(l=r\) 时显然用 exgcd 就行了。

考虑转化问题：有一个 \(0 \sim y-1\) 的序列，你要从 \(0\) 出发，每次向右跳 \(x\) 步（模 \(y\) 意义下），求第一次跳到 \([l,r]\) 区间内的点是什么时候。

考虑第一次跨过 \(y\) 之前，到达的点都是 \(x\) 的倍数，那么如果 \([l,r]\) 内存在 \(x\) 的倍数，答案就是这个点。

否则这些 \(x\) 的倍数会将序列分成若干段，其中每一段形如 \([kx,(k+1)x)\)（最后一段可能不完整），且 \([l,r]\) 被包含在某一个段内。

手玩一下，发现每次跨过 \(y\) 之后会回到第一段，之后不停地 \(+x\)，即跳到下一段同样的位置。

于是设第一次跳到 \([l,r]\) 的点为 \(t\)，如果 \([l,r]\) 不在第一段，那么 \(t\) 的上一步一定是 \(t-x\)，相当于变成 \([l-x,r-x]\) 的子问题。

不断 \(-x\) 直到 \([l,r]\) 处于第一段，那么只需要求解现在的答案，就可以推出原来 \([l,r]\) 的答案。

发现现在只与第一段有关，而 \(0\) 一直往右跳跳到的下一个第一段的点就是 \(x-y \bmod x\)。于是此问题可以看成 \(0 \sim x-1\) 的序列，每次往右跳 \(x-y \bmod x\)，求第一次跳到 \([l,r]\) 区间内的点是什么时候。这是一个子问题，即 \((x,y,l,r) \rightarrow (x-y \bmod x,x,l \bmod x,r \bmod x)\)。

这还不足以保证复杂度正确。考虑取个反，那么递归到的子问题就是 \((y \bmod x,x,x - r \bmod x,x - l \bmod x)\)，时间复杂度 \(\mathcal O(\log{\max(x,y)})\)。

晚上发生了一些很不好的事情。大概就是一些学弟在开摆，某个学弟回家后告诉家长机房有人在摆，那位家长便告了老师。后来摆的都被罚了。

这两天一直下雨，导致玩不了飞盘。不好的预感。

Day -1

上午去打试机赛，T4 愣是没想到背包问题可以折半搜索。学背包废了。

由于昨晚的事情，教练把全机房的人都叫过来教育了一番。

“我们机房从来都没有考前可以腐败的传统！”

大家可以翻看我之前写的游记。哦没有 WC 游记啊，我记得那天晚上老师给我们点了麦当劳，放了电影，并允许我们自由腐败。

非常非常难受。我想应该有不少人理解我的心情。

总之教练还是明令禁止我们玩游戏以及打开无关网页，这样好像连 puzzle collection 都不行了呢。希望明天早上其他人考 J 组的时候可以偷偷摸一下。

下午和晚上完全开摆，唯一做的一道题是去年 T4，板子是一点都不想打。不过多亏了学弟们的支持，让我们在如此艰难的情况下得以放松了一会（有人能猜出来我们在干什么吗？）。

Day 1

昨晚没睡好觉，幸好不是上午考试。

想着去 acwing 玩一会，结果被教练发现了。~~不是这都不能玩吗？那我还能干什么？写题吗？~~

8:30 了，好像在谷群发现了一点乐子。这是能说的吗？

本人 QQ 号刚才被人盗用，本人并不知道 J 组题目，且并不知道 J 组考试中发生的任何特殊情况，一切不良后果均与本人无关。

还是想多了，教练一直都待在机房，完全没有可以摸的机会，只能跟昨晚一样了。以后一定要写一个相关的 QQ bot！

中午吃饭，小卖部没开，买不了巧克力，这是不好的。听了 J 组题目，好像很简单的样子，听说 zlt 不到 1h 就 AK 了！/bx/bx/bx

午睡前紧急翻看了一些没复习的东西，虽然不怎么会考就是了。希望今年也能考简单一些。

面基了 zsh，然后进了考场。位置在角落，唯一的缺点是键盘抽的位置好像太靠左了，有点难受。

14:27

经典提前 3 分钟开考，解压密码忘了。

你先别急，让我把 my_std 给打了。

14:33

自测 my_std 没啥问题，开始看题。

T1 看起来好简单的样子，反复看了几次题面确认没问题后开始码，做法大概是直接枚举，然后开个桶记录次数。

一遍过了所有样例，但是 CCF 没给大样例，有点慌，自己造了若干组数据。看起来不太可以拍的样子，就丢一边了。

14:45

T2 有点好玩！推出若干性质后开始确定做法（虽然说这些性质都没啥用就是了/qd）。

一开始想的是 cdq 分治，然后用 trie 维护，感觉空间 \(\mathcal O(n|\Sigma|)\) 不太行。后来想了个更好写的做法，直接对每个右端点求出最近的合法左端点就行了。虽然空间还是 \(\mathcal O(n|\Sigma|)\) 的，但是它写出来才 200B 啊！而且能过就行。

一遍过了所有样例，自己造了个极限数据，没爆空间，还很快，就丢一边了。

15:10

看到 T3，真切感受到 CCF 没题出了，上午 J 组的 T3 也是如此。

毕竟是（大）模拟题，题面需要更加仔细阅读。手玩样例感觉理解没问题，大致想好如何实现后开始写代码。

写到一半发现起始位置的规则那里好像理解错了，幸好题面最后有形式化定义，感恩！

由于时间充裕，于是就慢慢写，一遍过了所有样例。手造了若干组数据后感觉没问题，也不太可拍，就丢一边了。

16:10

终于要来了吗，T4！

读完题面后在草稿纸大概推了一下，肯定要二分，然后每个点有一个时间上限 \(l_i\)，唯一的要求是 \(l_{fa_i}<l_i\) 以及 \(l_i\) 互不相同。于是将 \(l_{fa_i}\) 对 \(l_i-1\) 取 \(\min\)，开个桶记录每个 \(l_i\) 出现次数后判断合不合法然后……做完了？

不是，T4 放这种东西？我都不敢相信。

懒得解二次方程，而且怕精度爆炸，于是直接二分解，时间复杂度 \(\mathcal O(n\log^2 V)\)，很能过的样子。

很快码完了，怀着激动的心情看着它一遍过了所有样例，手造极限数据后本地只要 0.8s，感觉过得去。

我，AK 了？