前言
暑假和开学后一直在考模拟赛,前前后后考了有四十多场,这应该比我以前三年考过的模拟赛数量加起来还多了,所以这个赛季还是希望能考好一点的 (虽然模拟赛考的很烂)。
印象最清晰的是一场 S 组模拟赛把 CDQ 分治加斜率优化 dp 放在了 T1。很多大数据结构 T4 也是之前没有见过的码量(比如有一次的 23K 700 行的正解代码),很新奇当然也很痛苦,不过改完了还是能有进步的,一些基础的 trick 也慢慢会运用了。那么验收成果就是这个赛季的成绩了。
2024.9.21
初赛日。
早上去考 J 组,本来以为要求不得个人报名可以让水军少很多,但是实际看下来并没有少多少,周围的小孩还是挺多的。
考场在人家教室里,但是早上我的座位就在垃圾桶旁边,而且课桌太小放不下腿,比较差评。J 组比较简单,大概一个多小时就写完了。
欸你这个 int
的范围是多少啊?
下午 S 组,还是在同一个考场,前面坐的就是 @OIer_Automation。前面几道题做的都挺顺的,但是不知道为什么阅读程序第二题唐了半天,愣是一个小时才看出来一个允许有前导零而另一个不允许。
急急急,只剩半个小时了,还有三道大题。我直接乱蒙了一下第三个完善程序,开始做后面的完善程序。二分的题比较简单,次短路暑假刚考过,而且出的还是 Dyc 的写法。不过还是因为太唐错了几个。
这样考 S 组不行啊,复赛这样就完蛋了。
2024.9.23
丸辣,CCF 又泄题了,怎么还和 SN 有关啊?吃瓜吃到自己家了。
没事我肯定没泄题。
2024.9.27
初赛出分了,J 组 \(93\),S 组 \(70.5\)。这考的有点烂啊,S 组还没去年高,基本算全机房垫底了,属于是开了一个不好的头。
希望复赛别炸了。
2024.10 上旬
\(10\) 月份学校还是有很多事情的,先是第一次月考,然后又开运动会。运动会完了正好开始备战 CSP,波波给我们把作业停了一周,然后又停了一周课。考前最后一场模拟赛说是信心赛,确实是一周来考过最简单的了。
考前最后一天强调了下注意事项,\(8:30\) 就放学了,让回家准备准备。
2024.10.26
为什么这个考场这么远啊?贴近秦岭感受大自然啊?
早上还是先考 J 组,进考场发现机子屏幕极小且极难看,键盘也只能说差强人意。打了代码模板后写了个 dij 试了下机子就开始玩了。
\(8:29\) 发了 PDF 密码,然后就开始看题了。T1 直接一个 vis
数组就解决了,T2 随便模拟一下就解决了。T3 一开始想了个 \(O(10n)\) 的 dp,但是发现这样的话要开高精度,复杂度承受不了。简单打了表就发现一定是后面先放 \(8\),前面最多留两位特判一下即可。
此时仅仅过去了一个小时,优势在我!开始看 T4。
发现 \(r\le 100\) 后我迅速想到应该在轮数上进行 dp,所以设了个 \(f(i,j,k)\) 表示第 \(i\) 轮接到第 \(j\) 个人且结尾为 \(k\) 的方案数。
发现这样做复杂度会爆炸,然后考虑到每一次转移并不关心上一轮是具体哪个人作为结尾,只需保证结尾的字符以及结尾的人不是自己即可。所以就可以省去记录人的这一状态,不过对应的要为每一个人记录 \(g(i,j)\) 表示第 \(i\) 轮以 \(j\) 位置作为结尾的方案数,以此去判断上一轮所有的以 \(k\) 为结尾的状态是不是都是从自己转移得来,如果是就不能再转移了。最后在当前的人上进行一个差分就可以弄出当前的状态。
想到这些并写出代码大概花费了我 \(1\) 个小时,但是崩溃的来了——这个复杂度 \(O(\max r_i\times \sum l_i)\) 的程序大样例跑了 \(5s\)!
我第一反应就是常数太大。想到 CSP 考前一周的模拟赛有一道题专门就是卡常,并且考前一天我还在卡一道题,我以为优化常数应该不算难。我把自己看的所有卡常技巧全部扔了上去,又花了 \(1\) 个小时优化各种细节,这个大样例却始终只能跑到 \(1.95s\)。问题是大样例不满啊!
此时我还是比较绝望的,自己从来没有 AK 过一场比赛,难道要因为常数爆炸吗?但是考试结束,我也没有办法,只能祈祷 CCF 评测姬快一点。估分大概就是 \(100+100+100+[60,100]=[360,400]\)。
考完试发现今年的组织好唐啊,要填一个什么表,还要监考老师挨个给学生打压缩包,看着学生提交。捣鼓了十几分钟才让走。我们考场还是走的最早的,@Zctf1088 的第一考场半个多小时才让走。
中午在车上吃饭,休息了一会。完全没有睡着,因为一想到下午的 S 组就紧张,遂起来再看了看板子。
S 组在同一考场。开考后迅速秒掉了 T1。T2 怎么是物理题?我当年学物竞的时候就是从这开始讲的。第一问二分就可以简单秒掉,第二问可以转化为区间上线段的最小点覆盖。想到了考试两周前刚做的杂题中的 某位歌姬的故事,部分分中的 dp 状态可以直接拿来用,线段树优化也是比较显然的(当然我考后才知道完全不必这么麻烦,实际上这个麻烦的做法也给我造成了一定影响)。
一个小时调出了 T2 的代码,结果大样例又被卡常了,不过这次稍微加了快读就跑的飞快,甚至跑进了 \(1s\) 内。
这个时候已经过了两个小时,我开始做 T3。很快想到了 \(O(n^2)\) 的 \(50\) pts 做法,然后想到了这一类区间分割问题实际上是模拟赛中考过的经典题 CSP-S 模拟赛 13 T4 送快递,开始以此去推 dp。但是我错误的将状态设为了以 \(i\) 结尾而非开头的最优答案,这导致我始终推不出正确的式子。半个小时后决定放弃,先去写 T4 暴力。
T4 有比较简单的 \(20\) pts,但是我却唐了一个小时才把这一部分分打出来。这个时候只剩不到半个小时,我也无心再去想 T3,只好开始检查文件。
考后估分是 \(100+100+50+20=270\)。听 Dyc 讲了它 T3 的做法,然后自己想了想设 \(f(i)\) 表示以 \(i\) 作为一段开头的最优解怎么做。最后很快推出来了式子,只需要开一个桶维护值域上的最值即可。
忽然觉得十分难受,明明是模拟赛考过的题却没有做出来,自己改题也认真了,为什么会这样呢?
考后纠结这个题纠结了一段时间,总是想着自己如果再多想一点做出来了如何如何。但是考过的已经是过去的不可改变的了,也只能作罢。
2024.11.04
期中考考试第一天,正好也是 CCF 出分。J 组的 T4 卡过去了,\(400\) pts,S 组也没有挂分。
整体对自己的发挥还算满意,基本水平都发挥出来了,J 组的 T4 还超常发挥了一下。只有 S 组的 T3 有些失误,不过也还算是在可接受范围内。毕竟谁能没有遗憾呢?
赛季的第一场比赛结束了,后面还有 \(11\) 月的 NOIP。不管成绩如何,这只是一个起点,前方还有更长的路要走呢。
p.s:停课一周回去考了期中,考了个年级第二。
标签:结尾,T4,CSP,2024,小时,100,游记,模拟 From: https://www.cnblogs.com/UKE-Automation/p/18537712