初赛部分
Day 1
真的有必要写吗?如有。
感觉还是要延续之前 CSP 游记的排版。
考前复习了半个小时初赛,优势在我。
好像迟到了一点点,监考员没有给我发试卷,但是给我发了两张知情同意书。睡觉。
出来对答案,错了几个,一个忘了有二分上下界,还有一个是 linux 下编译。
有人 NOI 考完之后忘了 g++ 怎么编译,猜猜他是谁呢?
有人 NOI 考完之后忘了 g++ 怎么编译,猜猜他是谁呢?
有人 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 了?
- 16:30
别急,还要检查。
重新测了所有题的大样例,测了极限数据的时间与空间,在 Linux 下测了一下防 UB。
之后写了 T2 和 T4 的拍,造了各种数据,都没挂,这是好的。
再次检查若干遍文操和数组大小,之后就开始玩 tetris。很难想象每次监考员检查我的代码文件时都要看到我玩 tetris 是什么心情。
玩累了就趴在桌子上睡觉。键盘的敲打声此起彼伏,很助眠。左边的小哥还在努力调代码,很有毅力!不知道是不是在调 T3。
结束前还玩了玩小恐龙,觉得这东西对提升动态视力很有帮助。
出考场了,还是觉得不可思议。为什么这次打的能够如此顺利,所有代码都没有调试,一遍过样例,且并没有拍挂。
交流了一下,都觉得很简单,感觉今年 AK 人数会非常多(不考虑挂分)。希望不要挂分吧。
晚上打 ucup + CSP 自测。云斗,核桃和小图灵都没有挂,洛谷第四题 T 了两个点,不过我选择相信 CCF 的机子(参见今年省选 D2T1)。
标签:bmod,样例,Day,T4,2023,mathcal,游记,第一段,CSP From: https://www.cnblogs.com/AFewSuns/p/17779799.html