2024 CSP CQ

· · 个人记录

前言

停课了，该写游记了。

10.14

停课第一天，上午打了模拟赛，T1 是 STL 大杂烩，直接掏出优先队列。T2是人类智慧题，先跳了，T3 是仙人掌，根本没遇到过仙人掌，想了下 dijkstra 或 spfa 的乱搞，没想出来，又跳了。T4 一开始把子序列看成了子串，白打 30min，重新读题注意到所求的为严格上升子序列，遂直接无视限制，左右同时加入，由于取了左边必然不会取右边，反之亦然，所以最大值轻轻松松，方案数取了下巧，将 a_1 复制两遍后答案除以 2 就可以避免分类讨论。爬回去打了点部分分，遗憾离场。

下午出成绩，nm除 2 没写逆元，痛失 15pts，差点场切紫题，我是 fvv。预计 100+10+20+100=230，实际100+0+40+85=225。

补题，发现 T2 是连续段 DP，T3 是仙人掌 DP，T4 是线段树/树状数组优化 DP，被 DP 场搞心态了，瞪了 1h 仙人掌的圆方树做法，吃饭前极限打完。

吃完饭打了会羽毛球，@AlicX 自称羽毛球天才，实则只会欺负@songszh。

晚上来看删边最短路，感觉自己变成唐诗了，连 O(n^2) dijkstra 都写不来 /kk。

10.15

上午 VP div.2，C题双指针调了15分钟，虽然最后25min开 E 时一眼秒了，但是打代码 20min + 调题 10min 导致超时5分钟才过qwq。可怜昨天的 @AlicX，最后时刻没有抄过 E，强烈谴责@CQ_Bob 提供错误代码欺骗 @szhqwq 与 @AlicX，强烈谴责@szh_qwq 抄上 CM。

下午定时打 2200 的CF，结果教练专挑紫的放，1h才想出 T1，一个巧妙的线段树题，不等式转换后，维护值与二分上限一致，都可以直接查询。结果取值范围有负，tag=-1 直接怒调 1h。T2读错题，幸好有@AlicX 的提醒，不然就原地寄寄了。然后发现是水。T3 是个阅读理解题。T4 是弱智 hash。T5是人类智慧构造题。

补了一晚上题。

10.16

上午模拟赛，T1是弱智枚举gcd，秒了。T2 是线段树+栈，也秒了，反复改了几处细节，过了hack。T3是神秘题，发现关键性质但是没能发现式子里面的 a_i-a_{i-1} 可以转换成差分，区间加变单点改，然后套用贪心，唐完了。T4本来一看出根号分治，但由于坚信根号分治超纲，所以没有多想 c<\sqrt N 的情况。预计 100+100+20+20=240，实际 100+100+20+0=220，rk3遗憾离场。

下午补了下 T3，唐诗@As_Snow 一直在那p图。

晚上接着补题，调了好久，多亏了 @AlicX，休息时去打羽毛球被 @highkj 和 @AlicX 利用地形优势击败了/kk。@As_Snow 玩AI换脸，/bx 女装大佬 @CQ_Bob 和 @szhqwq

@CQ_Bob

10.17

早上打去年NOIP T4，除了最后的 subtask 其余全会了，愣是没想懂怎么树状数组转线段树。调了一早上没调出来，直接不做了。我换做括号序列，弱智式子写得手类，结果一直 0 分，最后发现 i 写成了 j。草。

下午定时做题，T1 是弱智扫描线，一开始没看到排列。T2 是弱智翻译，马的题面全读错，性质一个不翻译，纯**。T3 是傻儿贪心，调了 2h。T4 是 dp，看都没看，虽说吃完饭回来做出来了，但是被 @highkj 用 spfa 过穿了。@AlicX 使用了唐诗线段树。

晚上也没干啥，就补了补题。qwq。

10.18

今天打了 NOI Plus模拟赛（蓝紫紫黑？），唯一可做的蓝是个打模拟，打个 83 跑路，T2 是串串，一眼不可做，T3 是送分，n^2 拿 70，T4 是概率，虽然知道是 DP，但是不会期望。

预计 83+25+70+0=178。 实际 83+15+10+0=108。

发现 T3 最后答案没取模。T2 看错时限没写离线。

@Acoipp 拿下 380 强炸了 /bx /bx

@szhqwq 19 分有实力tql。

@highkj 10 分有实力tql。

10.19

去八中打线下模拟赛。

T1是弱智题，开T2，一眼DP，推式子1h，打了 O(n^2)，没过大样例，先看T3，感觉是一堆 trick 揉一起，只能跳，T4完全不会，虽然一眼出了状态，但是一步都推不动。爬回来死磕 T2，发现式子假了，重新推了个 O(n^22^n) 的 DP，去掉搜索优化成 n^4，最后 7 分钟调过大样例，2 分钟前缀和优化成 O(n^3)，发现可以再来个前缀和优化成 O(n^2)，但是没打完，直接寄寄了。

预计 100+40+0+0=140。 实际 100+48+0+0=148。

回来发现整栋楼都断电了，只能去打羽毛球。

回到科技楼，看了题解，T2 只差 bitset 优化了，@As_snow 直接切 T2 了，T3 是 23kb 树剖+ST表查询，再换根 DP，今天真是吃到屎了。T4 是轮廓线 DP，会不了一点qwq。

10.20

5:00 来机房打 div.2，ACM效率高，多亏了 @highkj 光速秒 D，直接拿下rk33，加大分，直接4场1751。

10.21

做切比雪夫的题，整了一个上午，下午也没干啥，就看了看图论，晚上更是什么没干，就过了个矩阵快速幂优化dp。

10.22

上午模拟赛，T1 是傻逼最短路，秒了。T2是线性基性质题，也秒了。T3 是经典的模数搞事情题，刚看题都还能注意到，做着做着就忘了，最后区间 DP 式子没乘 2，打了个弱智 O(qn^3) 跑路了，T4 纯不可做，但是没想到建虚拟点我就真唐，O(n^2) 都没跑出来qwq。

预计 100+100+25+20=245。实际 100+100+50+20=270。

10.23

打模拟赛，数论场，T1 找规律，但是不会欧拉定理被卡常，T2 更是找规律，popcount 的奇偶性是什么抽象啊，T3 是牛马容斥题，一步都没推对，T4 也要容斥，不打容斥就没分qwq。全场只有 @As_Snow 看出 T2 规律/bx。

预计 100+60+0+0=160。实际 60+60+0+0=120。

打得最屎的一场。

赛前的集体 generals。

10.24

感觉什么都不会，但又什么都练不动。

晚上出去外培的学长和@CQ_BOB @Watersun 回来了，教练给我们讲了抽象联考的 T3，数论模拟赛打不了一点。被 @StayAlone 嘲讽赛前做平衡树板子题qwq。

10.25

上午打信心赛，打成打击信心赛了，T1 5分钟秒了，但是没清空晚，打了暴力拍了一个小样例，手模后才过，T2 是牛马结论题，最后一分钟推出了 DP 式子，赛后转换了下发现和结论等效，死透了。T3是典中典，但是没见过，不会拆位算贡献，不会期望。T4 人类智慧，可以发现前面的修改操作会被附带的除 2 变成 0，暴力枚举 log 就行了。

预计 100+30+0=20=150。 实际 100+30+0+20=150。

希望明天 rp++。

10.26

早上起来默写板子。手感极佳，10min过平衡树板子。看了看2021年S组T3，贪心题，拿着大样例调了1h，还好过了。

下午到科技楼门口集合，疯狂询问欧拉定理，但是也没用上。

上考场了，左边的左边是 @WaterSun，右边的右边是 @As_Snow。上来开 T1，最小看成最大，浪费10min，发现无脑贪心，感觉可以输出众数，但是不敢，打了个丑陋 upper_bound。开T2，高中物理+贪心，不难发现超速的时间是连续的一段，也就是连续一段路程，也就是会经过连续一段测速仪，二分查找即可，问题转换为一堆区间，选尽量少的点使得每个区间至少覆盖一个点，之前教练讲过这个贪心，但还是自己证了下，一遍过大样例，手感极佳。开 T3，发现样例与样例解释不一致，但是影响不大，随手定义了一下状态，发现只有与 i 值相同的位置有贡献，或者直接从前面传递， O(n^2) 很显然了，立马又发现只有离 i 最近的，与其值相同的 j 有意义，因为若再往前取，连续的一段贡献显然不优于两端拆开。前缀和优化一下直接就 O(n) 了，大样例随便调调就过了。此时才过 2.5h，T4 抽象读入，看题花了 10min，感觉特殊性质 A 比较水，纯暴力较水，花了一个小时拼了下，拿了 28pts 就检查去了。

回家颓了不知道多久，想起来应该测一测，打了个 T1，并没有挂。

预计 100+100+100+28=328。

10.27

早上起来害怕 T3 挂掉，键盘都看不清，但还是打了 T3，过了，悬着的心总算放下了，T2 给了那么多大样例，应该不会有事，晚上聚餐，打 arc，结果是抽象场，只能 unrated 了。

10.28

在 luogu，云斗，梦熊都是 328pts，感觉不会有大意外。

11.4

查分了，从 1:00 推迟到了 4:00 又推迟到了 5:30。