首页 > 其他分享 >CSP-S 2023 游记

CSP-S 2023 游记

时间:2023-10-22 15:36:25浏览次数:33  
标签:bmod 样例 Day T4 2023 mathcal 游记 第一段 CSP

初赛部分

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

相关文章

  • CSP2023游记
    初赛忘了,反正记得很早做完开摆了,然后最后错了一个阅读,原因是直接默认\(A\)远大于\(n\),然后忽略了复杂度中的\(n\logn\)了。/cf复赛Day-1给J组小盆友出了点模拟赛,晚上去讲了两次题,顺便zyq去拿奶茶,被徐嘉正质问为什么不敢点ez(准备蹭xjz一顿大餐。本来xjz说要......
  • # 学期2023-2024-1 20231401 《计算机基础与程序设计》第四周学习总结
    学期2023-2024-120231401《计算机基础与程序设计》第四周学习总结作业信息这个作业属于哪个课程2023-2024-1-计算机基础与程序设计这个作业要求在哪里2023-2024-1计算机基础与程序设计第四周作业这个作业的目标自学教材:计算机科学概论第4章,第5章,C语言程序设计第......
  • 2023-2024-1 20211319《计算机基础与程序设计》第四周学习总结
    2023-2024-120211319《计算机基础与程序设计》第周学习总结作业信息这个作业属于哪个课程<班级的链接>(如2023-2024-1-计算机基础与程序设计)这个作业要求在哪里https://www.cnblogs.com/rocedu/p/9577842.html#WEEK04这个作业的目标<写上具体方面>作业正文......
  • CSP-S2023 游记
    \[\text{比较抽象的一集}\]Day-INF初赛\(79\),过了Day-10~Day-1天天模拟赛挂分,无语住了Day0疯狂写板子,晚上写数学板子每一个一次过的,感觉要寄学习了如何使用Sublime,感觉吊打DevDay1早上打摆,看旁边的人玩了一上午CS1.6看了看普及组的题,感觉T4很难,预感要寄......
  • 2023-2024-1 20231320 《计算机基础与程序设计》第四周学习总结
    2023-2024-120231320《计算机基础与程序设计》第四周学习总结作业信息这个作业属于哪个课程<班级的链接>(2023-2024-1计算机基础与程序设计)这个作业要求在哪里<作业要求的链接>(2022-2023-1计算机基础与程序设计第四周作业)这个作业的目标<自学《计算机基础与......
  • # 2023-2024-1 20231322 《计算机基础与程序设计》第四周学习总结
    作业信息|2023-2024-1-计算机基础与程序设计|(https://edu.cnblogs.com/campus/besti/2023-2024-1-CFAP))||2023-2024-1计算机基础与程序设计第四周作业||这个作业的目标|总结第四周学习过程中的疑问及收获||作业正文|(https://www.cnblogs.com/cjl03/p/17780446.html)|教材学习......
  • 2023/10/21 学习笔记
    vrrp与DHCPvrrp报文协议advertisement(心跳线)--目的ip地址224.0.0.18,目的mac地址01-00-5e-00-00-122,协议号是112.状态机:(优先级0-255) 默认0-2550代表主要退出255代表有设备和虚拟ip冲突可手动配置1-254优先级相同会比较接口地址大的优先优先级默认为10......
  • P9754 [CSP-S 2023] 结构体 题解
    前言在考场上调了2h+还没调出来,并且T4也没来得及做。希望看到这段文字的你能避免这样的悲剧。正文题目要求动态创建类型,于是我用结构体代表一个struct(禁止套娃),要新建就new出来一个。(最后也没delete)structObj{typnamtnam;lllen,align;std::map<std:......
  • 游记——CSP-S2023 SD 第二轮游记
    游记——CSP-S2023SD第二轮游记Day0晚上从青岛出发,到了日照,路挺顺。试机,门口很堵,还好我进的早。考场是C404,转了几圈才找到(和几年前的小学组很近大学操场有小情侣,羡慕,呜呜呜。。。考场FTP没调好,说19:30考试19:45都没进屋。一堆普及组的来提高组试机(旁边的大佬1......
  • 【洛谷 9240】[蓝桥杯 2023 省 B] 冶炼金属
    #[蓝桥杯2023省B]冶炼金属##题目描述小蓝有一个神奇的炉子用于将普通金属O冶炼成为一种特殊金属X。这个炉子有一个称作转换率的属性$V$,$V$是一个正整数,这意味着消耗$V$个普通金属O恰好可以冶炼出一个特殊金属X,当普通金属O的数目不足$V$时,无法继续冶炼。现......