CSP2024游寄

· · 生活·游记

其实是第一轮之后开坑的

Day 9.21-1

初赛前几天天天只睡三四个小时，然后放学因为没背英语课文被留了。

回来吃完饭 8.000000001:00 瞬间睡觉，结果身体觉得我不该睡这么久，然后……

Day 9.21

上午：最简单的一集。

娱乐比赛，我连J组题目都没做几套（只做了锣鼓的SCP-J模拟，S组都没做）

虽然暑假打印了 5 套 J 组卷子和两套 S 组但根本没做。

感觉CQ线要 80\text{pts} 了。

预估 90\text{pts}，毕竟以我的经验来看不管哪里都会挂点分。

民间答案：100\text{pts}，不会 AK 了吧？？？？？

上午把 RP 用完了下午没过咋办……

下午：啥？

这下真把 RP 用完了。

鉴定为赌王争霸赛。

阅读程序只能看懂第一个在干什么，做完前面选择和第一个阅读已经一个小时多了，后面凭本事乱蒙，结果发现完形填空是一个简单二分+次短路。

但是我没写过次短路！！！

然后就无了。回来估了好几遍分，在 [64,67] 浮动（lg 和小图灵的答案不一样）。

估计过初赛有点难，不过也算是积累一个经验：阴间位运算封装由于不涉及位移和进位，所以可以直接当成 bool 暴力枚举 4 种情况看结果即可。

我场上用了 20 分钟才明白 logic 的原理，但实际上考试中去深究具体原理“为什么会这样？”是不必要的，有时“知其然不知其所以然”是可以的。

当然这是在考试中为应试产生的特殊情况，平时练习可以去思考原理当然是最好的：

另一点就是有些事情并不需要过度准备（准备 != 过度准备），不要还没走第一步就想着第 10,20 步。

最后，好好睡觉（Sleep well!）

Day 好像是 9.27

姓名 准考证号 总成绩

【】 CQ-J【】100

姓名 准考证号 总成绩

【】 CQ-S【】64

搞笑。

CSP-J/S 2024第一轮J组得分为89分（全国排名前10\%）及以上的选手、S组得分为56分（全国排名前25\%）及以上的选手，均须确保晋级第二轮。

赢！

安心滚去复习复赛了，尸体感觉暖暖的

Day 难说

虽然过了初赛但还是好奇 CQ 线，发现往年 CQ 憋气大赛都名列前茅。。

1、 CSP-J 2024第一轮成绩在83.5分及其以上认证选手，可晋级J组第二轮。

2、 CSP-S 2024第一轮成绩在47分及其以上认证选手，可晋级S组第二轮。

居然不是顶满？

重庆本年度第二轮考点设定4个认证点，共提供700以上机位。

4个认证点？？？不是三个吗？？？

Day 10.13

又在搞锣鼓 SCP 模拟。

J：100+100+(0)72+(0)45=317

上午九点半才醒，十点开题，花 1 个小时看题面做 T1，，令人忍俊不禁

T2<<<T1 式子推错了，，以后一定先打暴力找规律

搞完 T2 已经 11:30 了，实在不想做了就润了，下午好好做。

S：100+0+(0)25+0=125

开始看了一个半小时题面才开始码。

T1 顺利想到正解，15 分钟写完，调了 45 分钟，bug包括但不限于：字符串未从 1 开始读入（这里说一下如何从 1 开始读入：scanf("%s",s+1);），链式查询某个数是否存在记录错误，数位分离未倒序处理，局部变量未赋初值（这使得第一个样例就错误，但在每次判定后printf("")就能正确）……

隐隐约约感觉 T2>T3，所以滚去拿 T3 的部分分了。

预估T3 $55$，结果B性质模块未特判（赛后发现即使特判依然WA）,$-30$，在 $n \le 5$ 时特判输出了 `3 1 3`，$-5$。 在使用checker时一直觉得checker有问题（为什么我输出有解它一直说没有解？） 18:20遗憾离场，交了代码滚去上课，路上想到 $n \le 5$ 时特判的bug，远程联系母亲改代码，母亲成功改对但没有找到浏览器和比赛界面，吾命休矣。 但是我在提交时忘记删除freopen，喜获 $0$ 分！ ~~所以我在比赛结束前想到了bug，所以还是能多拿5分，合计25~~ T2 观察到第六样例全为 Shuiniao，只写了`puts("Shuiniao")*t`，预估12，实际0。 T4 后面才看到可以极其简易地拿到 $28$ 分，然而也没时间码了。 合计 $100+0+(0)25+0=125$。 总结： - 不要看太长时间题面，15到30分钟足以，初步把每道题目理解。 - 每道题目都有可以拿的部分分，不要在一个题目上吊死。 - 留够时间码和拍，J T1/T2 一般纯模拟/数学，不会先暴力抓一半。 - 先整体看题面，然后逐个击破（或者抓点部分分），不保证难度递增，必要时可切下一题。 ## 此处省略 $10^9+7$ 场模拟赛。 # Day 10.26 六点半就被叫醒了，但是我诈（通假字，通“昨”）天在玩 $florr$ ，被母亲提醒了 $3$ 次~~不要玩地板了~~去复习。 ###### ~~至于为什么我也玩地板了？我们班上（此处指 whk 班级）所有人都在玩，所以我也入坑了。~~ 然后半夜打懒标线段树模版。 醒来直接在出租车 (ju1) 上睡觉，由于交通便利 $7$ 点就到 CQYZ 了。（~~一般情况下我都是坐轻轨~~） 顺利找到考点所在楼，一来就看见胡~~牢大~~，然而不能上去，把学校旗子给了我就上去了。 然后就罚站了一个小时。最搞笑的是因为我没有 YZ 校服，加上我手里的袋子（并且是透明的），~~于是所有人都知道了我是对面派来的卧底。~~ ## 上午：红红橙啊？ 鉴定为娱乐比赛 $2.0$ 。应该是近几年搞 OI 的人越来越多，所以 $CCF$ 逐渐在降低难度（包括 S 组，参考春测/S/NOIP 2023 T1，并且今年也是一样的）。 感觉这次 J 一股校内模拟赛味，~~两个语法基础+一个找规律+一个写不出正解的DP，并且感觉每道题都是原，并且赛后发现真是原，并且我没做过~~。 T1 居然不是纯数学推柿子橙题？？？为什么？？？不敢用 `std::set`，怕挂分，老老实实写了二维数组+枚举。 T2 依然语法基础，实在想不明白锣鼓为什么会标橙。就因为官方放在 T2？ 不过二维 `char` 数组 + $k$ 的取模 + DX/DY 这种模拟复杂度叠加起来可能能摸到橙题的边。 T3 先打了 $n \le 50$ 的暴力，然后瞬间找到规律，直接切掉。 前三题 + 看题面 $50$ 分钟就做完了，然后全部在搞 T4。 T4 想到图论，发现建边就会直接爆，果断 DP。 中途稍微假了一次，把题目看成了“接龙必须要上一个人的结束和这一个人的开始**数值和下标都相同**”。 我的赛时做法：$f_{i,j}$ 表示第 $i$ 轮是否可以达到数值 $j$。 注意要维护三种状态：不能达到即为$0$，有且仅有一种人达到为那种人的下标，有多种方案即为总人数 $+1$。 转移：每一轮枚举所有元素（下文记为 $m_1$），如果存在某个它前面的 $k-1$ 个元素（下文记为 $m_2$）使得 $f_{i-1,m_2} \ne 0$ 且 $f_{i-1,m_2} \ne m_i$，则至少有一种非这个人本身的转移，则更新 $f_{i,m_1}$。 这个做法是 $O(Tlk)$ 的，其中 $k$ 会自动和 $l$ 取 $\min$。有 $60$ 分稳过，如果 $CCF$ 机器够强有可能可以过 $k \le 5$ 的特殊性质，从而多拿 $10$ 分。 赛后看了下题解，稍微研究了一下才发现我的 $k-1$ 枚举有很多是重复的，如果再加个 $cnt$ 维护对后面转移起效的个数就是正解了，~~然后我就能 AK 了~~。 但是赛时不敢去优化也没想到优化。 不过 $100+100+100+60(+10?)=360$ 我已经很满意了（ 赛前只准备 A 前两题+后两题骗到加起来 $100$ $= 300$ 的。 总结： - T1/T2 这种类型的题目都是签到题，但是要保证准确性，**绝对不要出错**。后来发现由于输入全部有效，`std::set` 反而更加稳妥。 - T3 这种类型的找规律/数学思维先打好暴力，可能就能发现规律得到正解，同时方便对拍。 - T4 这种难度还是尽可能多拿分，同时注意仔细读题面。由于这次时间极其充裕，所以也要敢于优化，敢于正解。 - 另一点是这道题目还是花了我较长时间的，如果前三题换成 23 年难度，光是 T3 模拟在我早就看过题面（并且写过一次不完整代码）的情况下，依然使用了 $40$ 分钟打完代码，那么前三题+读题合计就会花掉我约一个半小时的时间，T4 可能就没时间写了，所以还是要好好提升码力，赛时尽可能兼顾编码效率、运行效率和代码可读性。 Update：我忘记 T2 有没有清空地图了！！！ 我的输入是从 1 开始的，所以绝对不会访问到0或n+1，所以偷懒没有写越界特判，但是我的地图没有清空，导致有可能访问到之前的地图，从而访问到其他地方！！！ Update2：字符数组读入时会清空上一次的，所以不会挂分！ Update3：不会清空未读入的行！！！！所以还会挂分！！！ Update4：大样例都过了所以CCF在用∠造数据，还是有机会的（ ## 下午：橙绿啊啥？ 赛前参考了往年 S 组（包括 NOIP）题目，发现一个趋势：从 23 年开始，连续三次（参考春测/S/NOIP 2023 T1）都在 T1 有意识地出签到题，但在此之前 T1 往往绿题起步，于是我认定今年必定依然保持 T1 橙题的传统，事实证明我的观点是对的。但是 $100$ 连去年 $6$ 钩都没有，只能拿 2=，于是我赛前的打算是 $100+30+20+20=170$，对标去年 $7$ 钩线。 但是在 CQ 依然没有 1=，于是赛前祈祷 T2 为绿，果真灵验。 正片： T1 结论很简单，但是不敢确认正确性，策略从最大对最小 $\rightarrow$ 双指针让第一个比它大的对阵 $\rightarrow$ 桶排序。 最终选择桶排做法，代码简单，即使假了就回溯，也不会花费太多时间，结果一遍过大样例，$100$ 拿到，瞬间精神抖擞开 T2。 这里说一下桶排的合理性：原题可化为：“给定一个序列，将其划分为若干子集，使得每个元素只出现在一个子集，且所有子集内部无数值重复的元素，求子集最小个数。” 子集内部会自动排序，然后从低往高依次击杀，由于内部元素不重复，每个子集只留下一个人，答案即为子集最小个数。 所以是桶排，每次取出存在这个值的一个元素作为一个子集，个数即为每种元素的个数最大值。 T2 开始发现只会做 $O(2^m)$ 做法，观察样例发现被看到超速的摄像头总是连续的，于是就变成了摄像头模型。 但是枚举每个摄像头会变成 $O(nm)$，只能捡 $60$，判个性质 A 可以 $70$。发现答案单调性，直接二分，复杂度$O(n log m)$。如果会超速，再记录线段，排序复杂度$O(m log m)$，稳过。 ### 但是我摄像头模型有点忘了！！！ 我刚开始学 OI 的时候学的最不好的就是贪心，发现官方比赛历年从未考过这种模型，便不打算专门复习。 ### 但是我现场想起（~~猜对~~）了模型！！！ 虽然不会严格证明。 代码直接写了 $100$ 行，光是 `main` 前面就有 $50$ 行。不得不说确实也算个大模拟（虽然绝大部分都在二分、特判和算第二问）。 非常顺利的过了大样例，发现居然跑了 $1s$ ？？？ 被卡常了？？？$\log$ 做法不该这样啊？？？ 发现是多测，并且是 $2s$ 时限。但是有半数数据是 $10^5$，相当于还是卡满。 不过想起来上午胡老师说 CCF 机器够硬，所以就去 T3 了。 到这个时候已经接近 $2$ 小时了，虽然 T2 是大模拟，但是我只写了1.6k，$30$ 分钟就打完了。 T3 不断在想 DP ，想到 $f_{i,j}$ 维护第 $i$ 位前面与 第 $j$ 位相同，想了个搞笑转移，大概 $O(n^2)$，发现样例都不过，又想了几种 DP，想了 $1$ 小时硬是没想出来。打个 $20$ 分暴力去 T4 了。 T4 读题都读了几遍，发现暴力都打不出来，看特殊性质结果发现任何性质都不能使用指数级复杂度，吾命休矣！！！ 打了个 `puts("1")` 就跑了。 接受了自己只有 $220$ 的事实，原本还幻想着 $100+100+[35,50]+[12,28]=[247,278]$，这样就稳定 1= 了。 然后就滚去检查 `freopen` 和前两题了。这个时候有一会想去卡卡 T2 的常，加个快读快写什么的，毕竟考前也打了遍模板。但是怕打出锅来，反倒 $100 \rightarrow 0$，~~怕不是要被全四机房人笑死~~，想想还是算了。 总结： $100+100+20+[0,CCF不是傻子，所以还是0]=220$ 。 $6$ 钩应该稳了，不知道 $7$ 钩 /1= 有没有。 - T1 纯思维大胆假设，小心求证。 - T2 勿抱有侥幸心理，该复习就复习。 - T3 还是要好好练习，DP 在 OI 的中后期都有很重要的地位 - T4 虽然我觉得我们现在应该不用 A 这道题，但是还是多刷题练练怎么打暴力吧（ ## Day 11.4 为了防止有人以极其简单的方式开合，我可以很负责的告诉大家，我的 J 组大概挂了几十亿分，但是 S 组分比我预期的好一点。如果想要知道实际成绩的，可以私信我。