CSP-S 2019 游记
公无渡河，公竟渡河！
堕河而死，其奈公何！
新的 OI 赛事又要开始了.
Day 0
早一天 (Day -1) 就回家了, 看了考场还算满意, 或许是自己的要求不够高? 熟悉的 win7 x86 & 2 GB RAM 令人想起之前的老台式… 不过 win7 内存占用很少, 考场系统除了红蜘蛛以外还算干净, 因此 2 GB 用起来还算流畅.
软件配置和去年类似, 有 Vim 和 Dev-cpp 我就满足了. Dev-cpp 虽然不好用, 但是作为现场唯一提供的 C++ IDE 还是要尊重一下的 (雾, 毕竟 windows 的 cmd 用起来有种说不出的别扭, 有朝一日在考场用上 Linux, 再用命令行编译吧.
手写注册表改了改键盘映射, 罪恶的 Caps 和 Esc 回到了科学的位置, 临时背的注册表好像有点锅, 不想修了. 本想在试机的时候刷个板子熟悉一下键盘, 后来因为有家长在等就作罢了.
HA 省机房槽点还是挺多的, 键盘主键盘区的 Enter 生怕不被误触而做的出奇的大, Backspace 为鼓励不写错而惊人的小… 其次就是空调足以把人热 sha, 通风也不是很好, 整体的空气有一种封闭的感觉.
到家后开始刷知乎, 我也不知道为什么就刷了很久, 晚上意识到自己太颓, 随便找了到自己鸽掉的 NOIP 真题写了一道, 思路不假, 只是可惜实现时还是参考题解, 希望在明天自己的代码思路能更明了一些吧.
回想了最近复习的流程, 还有些不常打的模板没有写, 因为不常打所以不熟, 然后就不想打 = =. 一意识到自己还有没打好的板子, 有种晕眩的紧张感. (还是不要太紧张好了.) 复习的过程还是有漏洞, 对于以往难写一点的 NOIP 题目, 应该在这周再写写, 同学从 qbxt 带来的模拟题, 也是要写写的. 但是这些事情都没有做, 只好携我两袖清风, 踏上考场了.
这周在学校的几个晚上不能用电脑, 无聊翻翻紫书权作复习. LRJ 的书果然是 OI 真理啊
但是有一点需要注意: 理解一个题解和自己独立推导出所有细节还是不一样的, 所以在看完一个难题题解之后最好把它做两遍: 一遍是刚看完题解以后 “趁热打铁”, 一遍是等忘掉题解后自己从头推导一遍.
——— 刘汝佳 <算法竞赛入门经典 (第 2 版)>
附, windows 下修改注册表使得 Esc 和 Caps 互换的注册表文件, 还是喜欢 Linux 一行命令解决的简单方式:
1 | Windows Registry Editor Version 5.00 |
Day 1
七点五十多的时候发现大家都到了, 其实我到得还算早, 只是恰饭浪费了时间… 会合后照例谈笑风生, 开始各路毒奶:
“请问有省四这种奖吗?”
“我现在开坑 CSP-S 2019 Day 1 题解, CCF 会不会把我禁赛三年啊?”
“我 Day 1 是不可能 200 分以上的, 我要是考到 200 分以上就女装.”
“我拿一等我就女装.”
“您是不是 AK Day 1, 明天就不用来了?”
……
啊, 这群人考好点就有戏看了~
咳咳咳.
Ren2Zhen0Si1Kao9?
进场后, 空气比昨天要好很多了, 配置考场环境也没有出什么大问题.
拿到题后, 强迫自己看完三题题意, 本想直接写 T1 的, 怕不是 CF 写多了, 后来还是等半小时后再动键盘.
T1
看到给出 “格雷码” 的完整构造方案以为这题和 神奇的幻方 同源, 看完数据范围后才发现直接模拟会挂…
考虑了一下, 写出了一个构造方案, 感觉可行就直接写代码了, (但是应去手算一下样例的, 这样就可以避免接下来会出现的错误了)
结果没过第二个样例, 确认代码没什么问题之后就又去读了一遍题, 果然是题目细节有疏漏, 修修补补算是过了三个给定的样例.
考试时 WA T1 就直接重读题意的想法来自昨天刷知乎得到的经验, 这里想引用一句话
一般这种题写挂就是没读懂题意, 回去重读题意就好了.
你看我刷逼乎还是有点用的(大雾)最大的遗憾就是没有写暴力拍 T1
T2
看到题目后就有 $O(n^4)$ 的带暴力想法, 本着
NOIPCSP-S 暴力打满的精神就先写暴力, 写出来前两个样例直接过了, 开始考虑怎么优化. 想了一会有 $O(n^3)$ 的 DP. 当时我兴致勃勃的去打这个 $O(n^3)$ 的 DP, 因为我算错复杂度以为这是 $O(n^2)$ 能拿到 $50 pts$.好在写出来之后及时发现时间复杂度是假的, 更好的事情是, 再优化到 $O(n^2)$ 也不算难. 改完没能过样例, 心态有点爆炸, 调整一会心态之后部分重构了, 算是过了第二组大样例.
临近考试结束, 拿着 $O(n^3)$ 的暴力拍了一下, 即便用脚随的数据很假也算是过了几十组. 脑子一热拿这破机子去跑了 恶 臭 不 堪 的第三组样例, 本机上 RE, 检查了一下认为是本地爆栈的问题就不打算管了, 毕竟我也不会手动开栈这种 “禁赛三年” 的操作… (雾, 你的手动 O2 是怎么学会的)
感觉这题放在 Day 1 T2 应该不会是难题, 可能是我有关键点没有把握, 没能想出来正解是我的无能. 如果因为 T2 退役也是不会令人懊恼的事了. 竞赛的事情啊, 还是以个人实力为基础吧.
T3
很像是贪心的样子, 不过有贪心策略就能在 $O(n)$ 的时间得到答案, 所以我一直在想枚举一点, 贪心一点的算法.
只是…没有什么好策略.
刚开始拿到题目之后, 肤浅地认为这题的分应该好拿, 解决特殊性质和小数据就可以得到不错的分数, 而链和菊花的情况也会好想一点. 后来的事, 就是我想多了.
$O(T\cdot n!)$ 的带暴力好哇! 虽然写的时候心不在焉, 导致自己调了好久…
离开考场之后见到 star, 听完情况之后一脸失望.jpg.
下午看了看民间数据, 好多人表示 “T1 大样例都过了, 可是交上去却没拿满.”, 有点心慌, 看来对拍一定要写, CSP-S 还是稳一点好. T2 有 $O(n)$ 的 DP 做法, 没想到的原因除去我太菜, 还有时间复杂度死找 log… 最近写比赛总是被数据范围误导, Day 2 要抛开 && 灵活一点了.
Day 2
昨天周围的人大多没有考得很好（指达到贵乎 $210 pts$ 水平），今天表情都挺阴沉的，可能都在想翻盘的事吧
@zhuajin1SHIJIAN7
T1
只要我 T1 能写出来，在 HA 我可以绝杀！NOIp 提高组 Day 2 T1 你能秒我，我当场就把这个电脑屏幕，给吃、下、去！
好的，T1 愉快的写炸了
开考前毒奶“今天不会有数数题吧？”，算是奶到了？开始认为是组合计数、容斥原理之类的东西，加加减减乘乘除除就可以了，以及模拟赛计数题就没有写对几题的经验，开考之后把 T1 先搁置了，愉快地去看 T2 以及 T3 了
T2，T3 暴力写完之后一直在想 T1 的正解，无果，于是就有了上面那段自嘲的段子。结果到 11:30 的时候 T1 暴力搜索还没有打出来，心态近乎崩溃，有一种挣扎无望的感觉，最后提交代码的时候也只好交了过不了第二个样例的假暴力。
实际上暴力可以拿到 $40 pts$，没有打的确可惜啊
T2
一眼看过去有斜率优化 DP 的味道，推了推式子感觉能做，写的时候发现假了，要求新数据的规模能够递增这个限制没有考虑到想到 T1 没有 A 掉的把握心有点凉 = =，所以愉快地打起了 $O(n^3)$ 的暴力 DP，没能优化到 $O(n^2)$ 或是 $O(n^2\log n)$，于是 $36 pts$ 滚粗
考虑 T2 的时候有监考老师过来：“对于 type=0 的所有测试点，保证最后输出的答案 $\leq 4×10^{18}$”。赛后出题人称使用高精是为了防止取模会直接 pass 掉 DP 做法，不过贪心策略也没能想出来，告辞
T3
动态求重心 X
暴力求重心 X
大暴力求重心 √重心板子执意没有复习，论据：“重心这东西也就点分治用过啊，CSP-S 不会考点分治吧？”诚然，没有考点分治，但是这一点都不影响 CSP-S 考重心 = =
原来的期望做法为 $O(n)$ 枚举边，$O(n)$ 求重心，总计 $O(n^2)$ 可拿到 $40 pts$，不过忘记了 $O(n)$ 求重心的做法，考场脑补了一会也只给出了 $O(n^2)$ 的做法，于是总计 $O(n^3)$ $25 pts$ 结 束 战 斗
今年的 CSP-S 结束了，明天就要回班里补文化课了。估了一下分数, 可能算是省二左右的分数吧. 如果就此退役, 也没有什么不好. 或许是之前的想法太过于极端了, 偏执地认为不学 OI 就没有什么想要继续去做的事情了, 但是如果真的发生了, 还是会偏向默默接受的态度吧.
期望得分: $100 + 50 + 10 + 0 + 36 + 25 = 221 pts$
后记
CCF 的官方成绩出来了, 比期望得分要高一些, 看教练那里的排名, 借着 HA 省是弱省的优势也能够拿到省一了.
Day2 T3 的 $O(n^3)$ 暴力似乎拿到了 $O(n^2)$ 的分数? 感谢 CCF 少爷机 ( 其实复杂度就是 $O(n ^ 2)$.
今年的遗憾就是没能 CSP-S 没能上 $300 pts$ 了, Day 2 发挥的尤为不好, 坐在考场上没有蓄势待发, 激情四射的感觉, 从内心似乎有些颓势吧, 思维也不是相当的活跃. 之前总是有一种错觉, 偏执地认为自己是 “大赛型” 选手, 平常写不出来的题, 到考场上或许就能写出来了; 平时容易错的东西, 到考场上也许就可以不出锅了. 其实不是这样.
原来自己之前只是机械的找题, 写题, 学算法, 没有注重于自己独立思索的能力. 以后要多加注意了.
省选, 再会了.