CSP-2022 J/S 游寄
Fido_Puppy
·
·
个人记录
CSP-2022 J1/S1
在自己学校考试，早上在宿舍睡到 $6:50$，出门有点心急，忘记换鞋了，穿着拖鞋就去机房了。
在机房水了几道题，$8:30$ 就跟着 $\color{red}\text{Licykoc}$ 下楼了，远远就看见 $\color{orange}\text{Zachary\_Cloud}$ 和 $\color{green}\text{yoghurt\_yht}$ 在食堂门口站着。遇到了好多同学，聊的很欢。 
大约 $8:45$，我发现手表落在机房了，感觉跑一趟还行，就回宿舍去换了鞋，回机房拿了手表，下来刚好 $9:00$，要去考场了。
换完鞋大概长这样
在考场门口等了大概 $10\ \text{min}$，$9:10$ 进的考场。
上午考 $J$ 组，感觉好像阅读程序比去年难了一点，但是程序填空简单的我有点意外? 
$J$ 组估分 $90^+$，自我感觉良好。
中午带两个同学参观了我的宿舍，顺便拿了两包零食。
下午 $2:30$ 开考，$2:00$ 可以到考场门口等了。
我竟然和 $\color{red}\text{QwQcOrZ}$  一个考场，跟大佬在一起瞬间感觉 `rp++`。
但是座位并不是很好，桌子一个脚矮了一截，需要用腿撑着桌子，椅子也有点摇。~~（话说下午好像其他同学都头晕，听说是台湾地震了，为什么我没有感觉到？）~~
祝台湾同胞全体平安！
发现 `CSP-S1` 的试卷有点皮，怎么还有宇宙射线？
发现一个锅 `for (int j = 0; j < n; j *= 2)` 求时间复杂度，本来想找一个 $\Theta(\infty)$ 的选项，发现没有，就先选了 $\Theta(n \log n)$，后来有老师来修了。
阅读程序感觉还行，可是完善程序怎么感觉 $T_1$ 比 $T_2$ 难？
$T_1$ 造了一组样例拍了一下，发现按照我填的方法可以过，但是还是逃不过扣 $6$ 分的命运。 
考完后遇到了我们初中的老师，他问了我们的学习情况，然后说 `CSP-S1` 如果有 $80$ 分那就可以稳进了。
回到机房，发现有洛谷估分，$S$ 组估分 $77.5$ 分，有点悬。
看了一些讨论，发现 $S$ 组 $T_{10}$ 竟然就是
$${8 \choose 2}$$
什么情况，记得考场上我算了一个 $7 \times 5 \times 3 = 105$，发现有点偏大，以为要除以什么东西去重，发现四个选项全是偶数就崩了，随便选了一个 $C$。
是我语文不好吗，为什么我 $T_{10}$ 没看懂题目意思？ 
初赛可以看一下 [$\text{Licykoc}$](https://www.luogu.com.cn/user/175456) 的 [励志故事](https://licykoc.blog.luogu.org/csp-2022-js-you-ji#)，$J$ 组估分 $96.5$ 分，$S$ 组估分 $95.5$ 分，$\text{Orz}$%%%。
$9$ 月 $27$ 日查分，但是似乎 $\text{NOI}$ 官网炸了。
$12:00$ 出分了，$15:36$ 查出分了，$J$ 组 $96.5$ 分，$S$ 组 $80.5$ 分，进复赛了。
$\color{red}\text{djwj223}$ 准考证号填涂时左对齐了，抱灵了，$\color{red}\text{houzhiyuan}$  也抱灵了。 
似乎 $\color{red}\text{djwj223}$ 和 $\color{red}\text{houzhiyuan}$  所在的 $1306$ 考场的所有人都是 $0$ 分，现在已经在申诉了。
恭喜 $\color{red}\text{Hovery}$ 卡线进复赛！ 
## CSP-2022 J2/S2
凌晨 $5:30$ 爬起来，$6:00$ 的时候出发去杭州师范大学。
在 $7:30$ 到了那里，面基了 $\color{red}\text{Licykoc}$ 和 $\color{red}\text{Hovery}$。
上午考的是 $J$ 组，按照去年的标准应该是 $1h\ AK$ 的。
进考场之后，发现刚开始不让动键盘（所以我还以为可以提前写缺省源呢）。
$8:30$ 开考，写完缺省源发现已经过了 $10 \min$，赶紧去开题。
看了一下 $T3$ 似乎不是很好做的样子，先用 $30 \min$ 把 $T1, T2, T4$ 写了。
然鹅 $T3$ 调了 $1h\ 20\min$（完了 $2h$ 才 $AK$）。
出来交流了一下，应该是人均 $AK$ 了。（所以我做的好像是最慢的？）
下午 $2:30$ 考 $S$ 组。（去年被骗说暴力打满就一等了，于是我拿到了 $80$ 分的高分？）
先开 $T1$，刚开始题目看错了，以为经过的每一个点都是算点权的，刚开始还在想为什么我连第一档分都不会了。 
先把任意两点之间的最短路求出来，然后判断两点之间是否可以 $k$ 条边之内到达，接着就可以暴力 $\Theta(n^4)$ 了。
突然发现可以只枚举外面的两个点，中间的两个点预处理出来，然后就变成了 $\Theta(n^2)$。
接着 $T2$ 被一眼秒了，分类讨论即可。 
然后开 $T3$，发现题目有一点小长，准备 $T3$ 和 $T4$ 部分分凑出 $100^+$。 
看了一会儿 $T3$，想了一下发现好像只要每个点的出度为 $1$ 就行了，第一个限制没什么用，于是直接动态维护所有出度的乘积，模了一个大质数，$60$ 分就到手了。（后来发现似乎要模两个质数？）
然后开 $T4$，一下子就想到了动态 $\text{DP}$，但是发现似乎普通 $\text{DP}$ 都打不出来？
放弃预计 $200^+$ 行的正解，开始写 $k = 1$ 和 $n \leq 2000$ 的部分分，先把路径拍成一个序列，然后开始 $\text{DP}$，发现第二个样例死活过不去，手模了一下，还以为是样例错了，后来才发现原来不一定只在简单路径上跳。
开始思考不在简单路径上跳的情况，发现只有 $k = 3$ 的时候才可能出现，并且最多只会往非简单路径的方向跳一格，第二个样例过了，但我感觉我的程序跑一下 $5 \times 10^4$ 的大样例应该能跑出来？
等了大概 $1 \min$，拍了一下，发现错了。~~（绷不住了~~
同时在等待的时候我还写了一个对拍程序，结果死循环了，窗口还关不掉了。
在最后的 $20 \min$，发现可以设另一个 $\text{DP}$ 数组，终于在还剩 $10 \min$ 的时候过掉了 $5 \times 10 ^ 4$ 的大样例。
考完出来**以为**自己是 $312$ 分了。
回到家后洛谷已经有民间数据了，但是 $T1$ $\color{red}\text{Wrong Answer}$ 了。
发现自己写了个脑抽的 $\text{bfs}$ 求最短路，但是写挂了。
有一点泪目，本来稳的 $312$，现在 $T1$ 变成 $0 \sim 100$ 中均匀随机了。 
自己估分：$50 + 100 + 60 + 52 = 262
洛谷：70 + 100 + 55 + 52 = 277
\text{Infoj}$：$70 + 100 + 60 + 52 = 282
小图灵：100 + 100 + 55 + 52 = 307
总结：比赛的时候没有发挥出最好的水平，T1, T3 挂分了，T4 本来如果暴力 \text{DP} 调得快一些，我可以把程序改成 \Theta(q \times \text{简单路径的长度})，在随机数据下期望 \Theta(q \log n) 就能拿 76 了。
最低情况直接拉成 $257$ 分，输麻了。
官网出分了，$100 + 100 + 100 + 100 = 400$，似乎 $T1$ 多给了 $5$ 分，$\color{red}\text{Licykoc}$ $T1$ 没开 `long long` 只挂了 $10$ 分，总分 $302$ 分。 
总的来说还是太简单了！！！