CSP2024 游记
szhqwq
·
·
生活·游记
CSP2024 游记。
都初三了。
求赞 pwp。
2024.9.21
看到巨神 harmis_yz 报了 J，以为大家都要报，然后就交了 50，结果是只有我们两个报了。。
9:30 的初赛准备 8:30 出门，结果，堵车堵到半路都 9:00 了我还没到 /wx，然后下车狂奔 15 min，因为不敢横穿马路所以绕了一圈/wx/wx/wx。
今年 xxs 还是很多的。核心力量。 今天 J1 略弱，如愿葬送 T1 int 范围砍下 96.5，比隔壁 harmis_yz 少 0.5 /kel。
S1 略难，CCF 你是会选 A 的。单选和阅读程序感觉还行，完善程序 9 个 A 我 6 个，赤石。估分 70 pts 左右，反正能过就行。
2024.9.22
稳定发挥 10:30 下了晚自习。
2024.9.23 ~ 2024.10.11
加训。
2024.10.12
停课了。无伤速通了月考及周考。感觉自己还是菜的一批。
2024.10.13
勾石体测，不知道测什么测这么久，导致没打 scp-s。
晚上 arc 下分场。
2024.10.14
停课 Day 1。
上午模拟赛。
T1 签到。
T2 一个连续段大炮，只会 10 pts 的特殊性质，毁了 pwp。
T3 仙人掌上跑一个诡异的最长路，40 pts。
T4 是很弱智的，只需要往两边都放上 i，然后向两边都做最长上升子序列就能做完，没有想到第一步转化，菜的一批。
Symbolize 赛时秒了 T4，但是取模不乘逆元，直接除以 2，挂到了 85 pts。
中午做线段树。
补题并加训。
2024.10.15 ~ 2024.10.18
间接板刷 CF *2200 与模拟赛，忘记记录了/kk
2024.10.19
早上去隔壁 BZ 打联赛，感受深刻。
坐我旁边的大多是高中的，感觉都强的离谱，对面的老哥码速应该 600+ 了，据说背后坐的是金银牌/jk/jk。
Symbolize：今天也是打上 NOI plus 了。
T1 签到，按照 i \bmod k 放下来排序就做完了，赛时 10min+ 切了，刚切完感觉一切良好。
T2 是一个出的很有意思的 dp，可惜不会，没交暴力，甚至 \mathcal{O(n^2)} 都没写，最后是一个 bitset 优化到 \mathcal{O(\frac{n^2}{w})}，只有 As_Snow 场切了/bx/bx/bx。遗憾离场。
T3 据说是菠萝题，题面套了一车图论的东西在上面，根本看不出算法，最基础的暴力 \mathcal{O(n^3)} 只有 5 pts，给了 4 个特殊性质但是一开始脑瘫一个都不会/kel/kel，最后感觉稍有状态把菊花图做了，15 pts 遗憾离场。solution 是树剖 + ST 表 + 换根 dp。逆天的是出题人 std 23 KB，写的一坨勾石，去掉缺省源 600+ 行，不敢相信是怎么出出来的，赛时无人过 T3。
T4 轮廓线 dp，拼了一个暴力。
据说 BZ 初三无人上 200 pts（?），/bx As_Snow 切 T2。
upd： BZ 最高分 240，被吊打了。
中午回机房，整栋楼断电，不知道在干啥 pwp。
T3 特殊性质挂了，赤石 140 pts。/ll/ll
2024.10.20
赤石。
上午睡到下午才起来吃饭。
下午来机房冲 div.1，T1 T2 都是唐，但是葬送 4 发罚时，少了 200 分/ll/ll/ll。成功掉分 19 pts。
2024.10.21
做了几个图论 trick，找空闲时间记上来。。
-
当需要维护有关图的连通性的问题时，如果在原图上难以维护或者时空不允许，考虑在其补图上发现性质进行一些操作。
-
AT_arc150_c：只需要去找是否有 1 \sim n 失配的路径，所以每次就贪心地选取匹配个数最少路径往后走，使用 dij 轻松实现。
-
CF1842D：遇到这种诡异限制，看是否满足对于 (u,v,w)，dist_{u} + w \ge dist_{j}，考虑转化到图上做，对于此题，假如每一列是若干条竖着的线段，其代表的是这个元素出现的若干时段。发现贪心地把它们同时往上尽可能地移动，即上端对齐，可以尽可能的让限制满足。
-
常数边权最短路。
-
奶龙 trick：从 1 和 n 分别做一遍最短路，考虑枚举边或者点中转。
-
超级科技：01 bfs。
2024.10.22
模拟赛 111。
T1 是签到，最短路典 trick。
T2 是签到，权值线段树处理异或典 trick。
T3 是牛马题，遂写暴力。
T4 是牛马题，遂写暴力。
被吊打/kk/kk/kk。
最后 1h 发现 T2 写的 100\% 错解，拼了个 50 pts，应该写线性基才对，或者写一个神奇的暴力，但是这个暴力想到了也不敢写，不会证时间复杂度。这还是去年做过的题，被创惨了。最后 T2 全 RE，【】【】【】。
真被吊打了/kel/kel。考虑让我在模拟赛中全挂的分全部加到 CSPS2024 中来。考虑让我在模拟赛中全挂的分全部加到 CSPS2024 中来。考虑让我在模拟赛中全挂的分全部加到 CSPS2024 中来。考虑让我在模拟赛中全挂的分全部加到 CSPS2024 中来。考虑让我在模拟赛中全挂的分全部加到 CSPS2024 中来。
通过询问教练在周五获得一场信心赛。/wx
这里记一个有关模数的 trick：当题目给定模数具有一定特殊性，考虑其答案是否会在一定范围之外变为 0，遂暴力。
这个 trick 被 highkj 巨神薄纱了 2 次了。
明天准备全天做 dp，因为太菜，准备先做绿题。
有批话哥跟我面基了/wx。
有点抽象。。
2024.10.23
速速 dp！！
- [CF1826D](https://codeforces.com/problemset/problem/1826/D)
容易发现 $l,r$ 一定是我们要取的两个点，直接 $f_{i,0/1/2}$ 表示前 $i$ 个点其中取到了 $i1/i2/i3$ 的最大贡献即可。转化式子为 $(b_l + l) + b_i + (b_r - r)$。
- [P5343](https://www.luogu.com.cn/problem/P5343)
矩阵优化，首先显然有 $f_i = \sum\limits_{k \in rqst} f_{i - k}$，然后发现 $k \in [1,100]$，就能构造一个 $100 \times 100$ 的矩阵进行加速。
- [P6433](https://www.luogu.com.cn/problem/P6433)
板子背包拼一个贪心做完了。
- [P1896](https://www.luogu.com.cn/problem/P1896)
这题在洛谷上没交过。
##
下午全真模拟，无法 dp。
T1 是推式子题，第一遍我贡献少加了导致推错。。第二遍才过了大样例。然后答案式子是需要使用欧拉定理来求解的。
T2 是结论题，每次把 $1 \sim n$ 中 `popcount` 为奇数的数放到集合里就行了。
T3 是很神奇的组合数，最后式子大概长这样：$\sum\limits_{a,b,c,d}\binom{n}{b}\binom{m}{d}\sum\limits_{i=0}^{\min(b,d)}(-1)^i\binom{b}{i}\binom{d}{i}i!\dfrac{(c+2d-2t)!}{2^{b+d-t}}
T4 差分后维护二维前缀和，对于修改维护 n 个并查集，询问使用权值线段树维护加数删数区间和就做完了。
继续 dp。111
发现 dp 顺序不好确定，考虑排序然后贪心地去 dp，我们可以按 b_i 从大到小排序，正确性可以通过车人教的邻项比较法来证明。然后就是 f_{i,j} 表示前 i 棵树选 j 棵的最大贡献了。
- [CF1801C](https://codeforces.com/problemset/problem/1801/C)
树状数组维护这些序列能否相连组成更长的最长上升子序列，然后做完了。
### 2024.10.24
上午在机房睡了几个小时。醒后准备做做序列分治。
- [SP32079](https://www.luogu.com.cn/problem/SP32079)
分治时维护 $[l,mid]$ 的后缀 $gcd$ 出现个数以及 $(mid,r]$ 的前缀 $gcd$ 出现个数，然后枚举前后缀，乘法原理计算答案。由于 $gcd$ 的优秀性质，时间复杂度应为 $\mathcal{O(n \log n)}$。
- [CF817D](https://codeforces.com/problemset/problem/817/D)，[SP10622](https://www.luogu.com.cn/problem/SP10622)，[AT_agc005_b](https://atcoder.jp/contests/agc005/tasks/agc005_b)
三倍经验。考虑最大值最小值分开分治双指针求解即可。
- [CF549F](https://www.luogu.com.cn/problem/CF549F)
CF *2800，但完全不值。考虑双指针，即枚举 $[l,mid]$，指针维护 $(mid,r]$，以及枚举 $(mid,r]$ ，指针维护 $[l,mid]$，维护一个前缀和，每次再维护前/后缀最大值，式子能够写为 $(s_i - s_j - mx) \bmod k = 0$，这个东西可以直接拿一个桶来维护。
- [AT_abc282_h](https://atcoder.jp/contests/abc282/tasks/abc282_h)
你发现单调栈很好写，于是单调栈乱过了。
- [CF1156E](https://www.luogu.com.cn/problem/CF1156E)
赤石，这题先是读错了题然后写了个错的，只能过样例，然后改了之后发现还是只能过样例 /kel/kel/kel。发现你清空桶的时候写的是 `cnt[p[pos]] = 0` 相当于只把你的指针最后停留点清空了，然后改成 `p[i]` 就过了。虚空调试 30 min /cf/cf/cf/cf/cf/cf/cf/cf。
- [P4755](https://www.luogu.com.cn/problem/P4755)
单调栈加主席树维护。
- [AT_abc248_h](https://atcoder.jp/contests/abc248/tasks/abc248_h)
听 AlicX 与 highkj 说此题不是一般的复杂，考虑到时间原因，放到 CSP 后来做 111。
##
你发现给 Edge 安个 iTab 插件并把背景设为砂狼白子能够有效提高做题水准与效率。111111
##
现在是简单题不会，难题更不会，后天 CSP，我该怎么办 pwp。
继续 dp。
- [P1758](https://www.luogu.com.cn/problem/P1758)
这题之前没做，毁了。考虑将 $a_i^2$ 的形式拆为取两轮，两轮取出的序列相同的方案数。时间复杂度 $\mathcal{O(n^3)}$。
不做了，复习板子。
### 2024.10.25
上午信心赛，成功打没信心，T2 的结论能被猜出来也不想说了。。
下午一直敲板子，预计明日缺省源 $86$ 行。
明天上午要和 CQ_Bob 征战 J 组 pwp。下午拿下 S 组。111
CSP2024 RP++CSP2024 RP++CSP2024 RP++CSP2024 RP++CSP2024 RP++CSP2024 RP++CSP2024 RP++CSP2024 RP++CSP2024 RP++CSP2024 RP++CSP2024 RP++CSP2024 RP++CSP2024 RP++CSP2024 RP++CSP2024 RP++CSP2024 RP++CSP2024 RP++CSP2024 RP++CSP2024 RP++CSP2024 RP++CSP2024 RP++CSP2024 RP++CSP2024 RP++CSP2024 RP++CSP2024 RP++CSP2024 RP++CSP2024 RP++CSP2024 RP++CSP2024 RP++CSP2024 RP++CSP2024 RP++CSP2024 RP++CSP2024 RP++CSP2024 RP++CSP2024 RP++CSP2024 RP++CSP2024 RP++CSP2024 RP++CSP2024 RP++CSP2024 RP++CSP2024 RP++CSP2024 RP++CSP2024 RP++CSP2024 RP++CSP2024 RP++CSP2024 RP++CSP2024 RP++CSP2024 RP++CSP2024 RP++CSP2024 RP++CSP2024 RP++CSP2024 RP++CSP2024 RP++CSP2024 RP++CSP2024 RP++
### 2024.10.26
最毁的一集。我这一生也是毁在了这里。
上午打着玩玩，20 min 杀到了 T4，然后寄了。一生之耻，毁于此。
下午 S 组。
进场后发现电脑的 vscode 不可用，不能运行，把我气坏了，不得不使用抽象 dev。码完缺省源后开题111。
T1 一眼贪心，然后使用 `multiset` 乱搞，一遍过了大样例。
T2 分讨一下，把产生贡献的测速仪区间计算出来，然后就是最小点覆盖，双指针乱过了。第一遍没过大样例，发现是有个 `upper_bound` 写成了 `lower_bound`，改了之后就过了。这时候大概是 15:10。
T3 是 dp，感觉有个神奇性质以前好像做过，但是没敢写，先写了 $\mathcal{O(n^3)}$，然后改成了 $\mathcal{O(n^2)}$，应该有 $50$ pts，~~希望有 $60$ pts~~。盯了 2.5 h 没有盯出来。
T4 好抽象，感觉难爆了，读懂题后感觉部分分不太好拿，于是回来继续做 T3，最后爆炸了。
这是你第 $3$ 次 CSP，爆炸了。
出来问了一圈，全都会 T3，洛谷上看了一圈，也都会 T3，感觉 T3 很简单，但是就是不会，果然，菜是原罪。果然，题做少了就是不会。果然，学了 2.5 年 OI 跟没学一样，活该被骂退役。甚至连写 T4 部分分的勇气都没有，你拿什么和别人打。
估分只有 $100 + 100 + 50 + 0 = 250$，应该没有 1=，应该没有 7 级。
等着看分数下来会不会挂分吧。。
Loser.