CSP2024游记

省流

废了，只有260

11.4：吗的只有252

10.18

本来考CSP-S之前压力没这么大，想着就算没考好只要能去NOIP努努力还有机会，然后这天晚上教练告诉我们CSP-S没一等就去不了NOIP qwq。这压力一下就上来了，我不要赛季刚开始就结束了啊啊啊，明天还有一场多校联合的NIOIP模拟赛，NK和YZ有一部分学生要来我们这边考，其中有我的好儿子 @Alicx gm还放了个挡板模拟真实考试，虽然我看到的第一反应是方便颓废。gm喊我们早点睡，但我为了“放松”和儿子来了把CS，本来打完才11点，挺早的，但是后来又不知道什么原因睡得很晚，感觉第二天要萎了

10.19

好好好，果然萎了，困得不行。。。。

8.00，gm发题，我先大致浏览了一遍，感觉部分分很多啊!T1想了个5min直接会了，wow，直接过大阳历了，感觉还行。遂开T4写暴力，写了一堆奇怪的DP，然后萎萎萎，最后改成dfs开心地过了大阳历。T3听说是最难得，那暴力分一定很多吧！然后读了一下题，发现我只会 O(n^3) ，再看子任务，居然有 5pts 出题人真的太良心了喵，赶紧写写写。最后花了30min也是成功把prim写成dijkstra了，嘻嘻嘻，改过阳历后就不管了，最后喜提 0pts 现在都不知道哪里错了捏。最后开了部分分最多的T2，感觉是DP，看到了 c_i=i 的特殊性质，发现这不就是将这个序列分段，然后每一段从这一段里面选个颜色吗，然后把这个特殊性质写了自以为没问题，再看暴力分，想到了 dp_{ij} 表示最后一段颜色是j的方案数，最后写萎了哈哈哈

下午来机房测一下分，发现喜提 100+4+0+40=144 被写了T2暴力的同学暴打了捏，gm又发了一套题，说是wx觉得质量很高，gm说拿给我们当“信心赛”，打了114514min才把T1T2过掉，因为T2的撒比题面真是太撒比了，然后开T3T4，发现都不会做哈哈哈，最后T3T4一共得了 15pts 喵喵喵，期间还有神本学弟2hAK。。。还好有伟大的绑点仙人，让tzy只有120，xyt100，lwz200，因为我打得都是最撒比的暴力所以没有挂分喵

晚上又按照gm的要求来打abc，一天三场比赛，场场皆失，总结是前5道撒比题，f一眼dp但是调1919810年也调不对，感觉成废物了喵喵喵

10.20

昨天打了三场比赛累成狗了，早睡晚起好身体啊！晚上是化学周考，考前有2h复习，结果我一直在睡觉。。。。。化学也是不出意外的炸了，献祭化学周考求CSP上300 qwq

10.21

今天补了周六的题，感觉自己是唐诗。

下午T3：

因为k特别小，考虑对于每个 a_i 求它满足恰好出现 j 次，区间 [l,r] 的 l,r 的取值范围，然后写个扫描线，考虑状压，记录线段树上每个节点差 sta 状态的数量，统计的时候就加上 tr[1].v[0]

T4

最唐诗的一集，一个顶点个数为 N 的凸多边形，再加 N-3 条互不相交的边，最后这个多边形肯定会被分成很多个三角形，然后我没想到。。。每个环一定是被若干个三角形组成的，于是就对于相邻的三角形连边，问题转化为连通块的数量，找三元环的方式就按照lzm的博客那样找，最后建出来的图一定是棵树，树形dp来求即可， dp_x=\prod{}(dp[y]+1)\{y\in son_x\}

上午T2：

正难则反，考虑最后的序列在何种情况下合法，假如最后序列为 \{1,1,2,2,3,4\}，则合并相邻的两项变成 \{1,2,3,4\} 于是这个最后的序列想要合法那么合并后的序列就必须是原序列的子序列，证明是 easy 的，那么考虑 dp_{i,j} 表示长度为 i ,结尾颜色为 j 的子序列个数

• 其中子序列必须满足相邻两项的颜色不同

  那么 dp_{i,j}=\sum^{c!=j}dp_{i-1,c} ，这样会T，考虑一下优化，因为答案对 2 取模，所以考虑 bitset ,于是用一个bitset ans ,ans 的第 i 位表示目前每个长度为 i 的子序列有多少个，dp_c 则表示颜色以 c 结尾的，每次转移的时候，若当前位的 颜色为x 则先把颜色为 x 的答案从 ans 中去掉，再将 ans<<1 赋值给 dp_x ,并将 dp_{x,i} 设为1，最后再将 dp_{x} 加到 ans 里,最后求答案就是 \sum^n_{i=1} ans_i\times C^{i-1}_{n-1} 即隔板法将子序列扩展为长度为 n 的序列

晚上是打“速度训练”，T1T2是水题，T3是打磨你，时间不够了，留到明天来写

10.22

晚上来机房把昨天的打磨你过了！感觉CCF再出个打磨你也有做出来的可能了（但是还是不希望CCF出），然后发现T4是第一眼有点没思路的题，直到放学也没做出来，于是复习各种离线算法

10.23

逃了体育课来机房复习，突然发现一堆数据结构不会打，还好有几个st表都写不对的同学，让我放松一点，晚上来机房就一个小时，于是看了一下学长列的大纲，在网上看了一些常见trick

10.24

铁锹回归，看了一下板子，打摆

10.25

语文课来试机，成功不用写作文

10.26

睡到11点起床，复习了一会儿，吃了个饭去学校了，2点半开考，看T1，发现是水题，10min过了，开T2，写加调1h，感觉这把稳了啊！就把后两题暴力写了，然后想到这么重要的比赛我得稳一手，于是放弃瞪T3正解，开始写拍子，拍T2，发现过了，测T4，发现前3个大阳历都过了，再看T3，知道是dp但是瞪了114514年也不会dp，就只写了20pts的最低档分，然后就一直检查代码了。。。这提高组怎么出成普及组了，出来一问人均300+，感觉废了。。NOIP也去不了了，这个赛季就这样结束了

赛后估分：100+100+20+[40,48]=[260,268]

感觉这分前几年稳1=啊，结果今年。。。

11.4

在教室的吸我查分，发现100+100+20+32=252，直接似了，还有传奇道吧，T3luogu只有10pts，CCF给它放过了。。。ojs也是，过了本来要挂分的题，xyt直接爽了，T2挂了60pts，唉，听天由命吧

11.19

CCF发线，CQ250，全国最高，然后顶级擦线直接爽了