游记 【CSP2020-S】

## 前言 - 此时的囧仙中之人是 @离散屑波变换 。以下的游记都是这个屑写的。 - $2020$ 年的 $\rm CSP$ 初赛结束了，写篇游记纪念一下。 - 初赛得分 $92$ 分，似乎还行的样子。有点略低于期望值（ - 复赛估分 $260\sim 295$ ，炸了炸了，但愿 $\text{CCF}$ 少爷机能让我 $n \log n$ 过 $\verb!T2!$ 吧（悲） ## 初赛 $\verb!(CSP-S1)!$ ### 考试之前 $\verb!(Day-27)!$ 好像初赛只有一天的样子……似乎没啥必要分什么 $\text{Day1 Day2}$。 初赛前一天压根啥事没做，照常 $11$ 点睡觉。具体要说做了什么吧，就是向老师请了个假（）相当颓废的一天。 ### 当天 $\verb!(Day-26)!$ 初赛当天早上就在学校机房把你谷的模拟卷做了。没认真看，就写了 $30 \text{ min}$ 练下手感。然后只拿了 $80$ 分。主要是一些题目不怎么确定，也没怎么仔细去想，就这样交了；然后看了一下海亮的那套模拟卷。 $\frak{u1s1}$ ，那套卷子挺好看的，尤其是代码块那边，应该是用 $\LaTeX$ 做的。 ~~草，关注点好奇怪啊。~~ 海亮卷子的单选题好毒瘤啊，全是数论，还有一堆我看不懂的东西（） 因为考场就在学校机房（话说为什么笔试要在机房啊），所以到的挺快的。听说 $\rm CCF$ 的袋子贴的比较紧，我看监考老师也没花什么力气就解开了？因为机房的桌子毕竟还是放了电脑，所以能放试卷的空位并不大，写题体验有点糟糕（） ### 考试中 谈谈做题体验吧。 - 单项选择题体验挺好的，至少没有什么申必的计数问题（之前模拟卷计数问题错了好多……）。也没啥常识题，就考了个香农。挺常识的。意外的居然没考今年是哪一届 $\rm NOI/IOI/NOIp$ ，我这种压根没背的选手侥幸逃过一劫（ - 阅读程序题做题体验也还行，就是这个阅读程序最后一题……槽点太多了 - 居然 $0202$ 年了还有人手写迫真 $\rm map$ 和队列，实现地还巨丑陋。 $\rm map$ 复杂度直接起飞。 - 大致看了一下程序，似乎是个双向宽搜，还加了点迫真剪枝。但转念一想，这玩意怎么说也过不了题啊…… - 这双向宽搜和迫真手写，纯粹是增加码量的罢（半恼） - 找规律题不知道正解，随便插值搞了个函数就填上去了。 - 算复杂度，我以为那屑代码至少 $\mathcal O(n!)$ ，居然就选了“正确”。然而我万万没想到的是，那题甚至比阶乘还裂（），什么屑代码啊（半恼） - 完善程序体验挺好的。最后一题有点难度，但也还能接受。 ### 考试后 上你谷看了一下讨论区，怎么个个 $70-$ ，搞得好像初赛很难的样子…… ### 题目的想法 昨天晚上很晚了，写了半个小时就去睡觉了……今天补一补对题目的看法罢。 - 第一题进制转换，没啥难度，很水。 - 第二题用排除法都能做的样子，非常常识。 - 第三题是经典的图片存储，简单除一下就行了。 - 第四题只要知道栈的操作就行了吧……可能有点小坑的是最后问的栈底元素。不过这样似乎更送分了（ - 第五题的哈希碰撞也是常规题。 啊这，做到现在为止都是水题啊。 - 第六题可能对算法的了解考察的比较多。不过也可以用排除法。主要是霍夫曼编码可能不怎么常见。（不过我好像印象里翻译为哈夫曼编码。）幸好看过这个算法的实现，是贪心。 - 第七题扇贝复杂度题，只要会做图的搜索就能做吧。 - 第八题主要考察二分图的概念吧，也挺入门的。 - 第九题也是相当入门。*（不过阅读程序题你出双向宽搜可还行）* - 第十题是经典的小学奥数，也可以直接用 $\rm CRT$ (中国剩余定理)去解。似乎也能暴力枚举。 做到现在没啥难度啊……题目都没啥意思。 - 第十一题考察了等差数列。也属于小学数学题罢。 - 第十二题考察了后缀表达式的概念，按照定义走就行了。 - 第十三题稍微有点意思。不过我当时直接容斥就解掉了（），后来演算的时候枚举了一遍，工程量也不大。这一届的计数题难度不行啊…… - 第十四题不使用堆或其它优先队列进行优化的 $\rm Dij$ ，复杂度至少不会带 - 第十五题考了个迫真常识题，其实用排除法排除一下就行了。不过我之前听说过香农，所以事实上也可以直接选出来（） 这一届单选题难度不行啊，各种考察基础概念的，常识题也不怎么难。意外的没考察奇怪的年份。 - 第十六题看不出这写了个啥算法。不过选项似乎挺简单的。 - 个鬼啊，`,否则程序可能会发生运行错误` 这句话到底哪错了。其他题目倒是挺简单的。 - 第十七题应该是找 $k$ 大。知道这一点做起来就比较简单了。 - 然而并不是。你还要看这代码怎么实现的。前两题送分，后面各种各样算复杂度。不过似乎也能模拟出来。 - 赛后听说第三题有问题。不管了，反正选什么选项都对（） - 然后是我最想吐槽的第十八题了。 - 代码长的要死，废话一大堆，复杂度还高的飞起，不知道出题人在想啥，纯粹用长代码恶心人吗？ - 手写 $\rm map$ 复杂度飞起。 - 然后莫名其妙写一个双向宽搜，搞得好像这样优化能过题似的。 - 简单看了一下代码，大致看懂了意图： > 有两个字符串 $st_0,st_1$ ，每次可以把 $st_0$ 中第 $m$ 个字符移到开头或者结尾。问最少多少次可以让 $st_0$ 变成 $st_1$ 。 - 不过不出所料地，前两个小问送分。 - 第三题没多想，以为这么屑的算法复杂度最坏也就阶乘。但没想到它能比阶乘还烂。 - 第四题莫名其妙地丢分了，太草了。我居然没发现循环字符串并不能翻转它。 - 第五题不会。不过既然它给了这么多输入和输出，怕不是找规律题（）但是这么屑的算法真的能跑的出这个输入数据吗/fad - 第六题先是不会。但这提示的也太明显了，随便讨论讨论逆序对就出来了…… - 第十九题似乎在你谷有[原题](https://www.luogu.com.cn/problem/P2240)的样子。~~引恐禁三警告~~。很水。 - 第二十题相对有难度，这种背包优化没看过（） - 第一小问应该是 $\rm lowbit$ ，写过树状数组应该就知道了。可能如果写过 $\rm lowbit$ 函数的话比较送分吧。 - ~~插句题外话，$\rm \sout{c++11}$ 已经支持直接统计一的个数了。果然€€￡已经落伍了~~ - 第二小问根据他给的 $Max$ 定义，可以发现就是求前 $8$ 位和后 $8$ 位。 - 主要难的是后三问。第三问首先可以排除 $Max$ 选项；然后根据 `对于空子序列，规定其子序列分值为 0` 就能猜到初始化不可能为 $-\infty$ 了。 - 假想我自己用这种背包写这题，我会怎么写？当然是考虑第 $i$ 个数字作为末尾时的转移了。然后考虑怎么转移。 - 所以可以大胆猜想，这个程序也是这么写的。 - 显然，我们要考虑上一个数字是什么。根据 $Max$ 的定义，我们只要让 $z$ 枚举它的后 $8$ 位就行了。转移方程就比较简单了。 - 然后是要考虑下一个数字是什么。为什么我们要固定前 $8$ 位？这自然要和转移方程有关。我们定了下一个数字的前 $8$ 位，就能提前统计这部分的答案；然后这也和第四问关联在了一起。 ### 评价 简单题送分到位，难题有点难度。但我感觉分值设置不怎么合理。几条 $4.5$ 分的题一旦错了就有可能导致另外一题跟着错， $9$ 分就没了。我感觉这也是导致分值差距比较大的原因。 考察的知识面还算比较广（哈夫曼编码，二分图，双向宽搜），但深度不够，基本停留在基本定义和基础算法。 总体难度，简单题显然低于往期，难题分值有点大了。 ### 总结 屑。 ## 复赛 $\verb!(CSP-S2)!$ ### 考试之前 $\verb!(Day-3)!$ 这天被拉到机房去打模拟赛了（草，一个星期也才打了两场，这就是复赛集训吗， $\rm ilil$ ）。结果四条题目 $T4$ 爆零， $T3$ 写挂了只拿了 $25pt$ ，树状数组都能写挂，整个人都不好了。 第四题在 $\text{Windows}$ 上能正常编译，结果在 $\text{Linux}$ 上编译错误了（ $\verb!abs!$ 不支持无符号整型），感觉自己傻了。 ### 前夕 $\verb!(Day 0)!$ 草，这天晚上才发现我看错时间了。一直以为是星期日上午比赛，结果是星期六下午，这一个星期我到底在干啥啊…… 这天也没啥想法，在洛谷上随便看看。没有什么心情，有点虚，不知道该看什么。 ~~结果这天晚上还在刷 $\frak{B}$ 站~~ ### 考试当天 $\verb!(Day 1)!$ 上午从学校坐大巴去南京了（~~暴露地址~~）。午饭在酒店吃的，还挺好吃的。 餐桌上有用来点烟的火柴，结果有几个人几个人吃完了没事干，用火柴去烧西瓜皮？~~人类迷惑行为~~。显而易见的并没有烧的起来。不过或许考场的秩序册可以烧起来~~引恐禁三~~。 西瓜皮的牙签上有个粉红色的玩意，我以为是块糖，结果就是一块木头~~我到底在想啥~~。 然后有个同学掏出了电脑玩起了车万 $\text{Project}$ 的妖精大战争。瞬间智商 $-$ ⑨ 。 完了完了，大家都被降智了。 后来普及组题目出来了。但因为听的是口述，对题意不怎么清楚，但感觉今年的普及组也不怎么难的样子…… 吃完午饭，休息了一会儿就直接去考场了。 排队的时候我们就在猜今年可能有哪些题目（以及 $\verb!CCF!$ 会不会自己抄自己）。然后我谈到了一个前几天在政治课上的事情，政治老师依次找同学回答问题，明明是一列，突然拐弯了。当同学表示诧异的时候，我们政治老师问了一句**你们玩过贪吃蛇吗？**~~然后那个被点到的同学回了句“玩过”然后坐下了~~。草，这就是伏笔吗。 拍了一会儿队，就进考场了。**终于到了激动人心的时刻力！** --- 试机的时候简单写了一下快读，顺便写了一下对拍可能会用到的东西，~~结果事实证明我根本没时间对拍~~。键盘用起来没啥问题。然后就是发题目了。 $\text{JS}$ 的压缩包没有设置密码的习惯，不能猜密码，我谔谔。 - 看了一眼 $T1$ ，看了 $1\text{min}$ ，不顺眼，直接去开 $T2$ 了。 - 然后发现 $T2$ 是道扇贝题，花了 $10\text{min}$ 就写完了，过了大样例。 - 第三题题面比较简单，~~但是我不会写~~，花了 $45\text{min}$ 写了个 $n^2$ 的做法。然后发现空间也是 $n^2$ 的，这样会炸，悲。不管了不管了，先去开 $T4$ 了。 - 我以为第四题是一道博弈论。最强的蛇会吃最小的蛇，当且仅当它吃了最小的蛇之后自己以后不会被吃。顺着这样的思路，我花了 $30\text{min}$ 写了个暴力，~~然后调挂掉了~~。 - 尽管如此，我还是想去看看 $T1$ ，于是翻回去了。题面读了 $5 \text{min}$ ，看到年份的数据范围达到 $10^9$ ，询问数达到 $10^5$ ，感觉又要爆推公式了。 - 但是我太菜了不会推公式，转而想做一做天数小于 $2\times 10^6$ 的数据点。接着我发现，只需要 $2305447$ 天，就能直接从 $-4713$ 年到达 $1600$ 年。也就是说，这题一半的难点（公元元年的转换、被消除的 $10$ 天、巨麻烦的闰年判断）直接被砍没了…… $$\text{哎呦我操，这是好的。}$$ - $1600.1.1$ 之后的情况就非常单一了，公式应该也很好写 ~~可惜我还是推不出公式~~。这时，我发现： $$\text{从年份推天数比从天数推年份容易多了。}$$ - 然后考虑二分年份，计算它和 $1600$ 年之间的天数只差（因为我数学不好，为了防止奇奇怪怪的边界条件，我选择计算差值，这样就能统一削除误差了）。确定了年份，月份和日期可以直接枚举。 - 对着大样例调了一会儿，过了。这时候我非常高兴。这时候比赛已经将近 $2 \text{ hour}$ 过去了。 - 做完了第一题就回到了第四题。我发现，吃蛇的顺序是永远不变的，并且最多会吃 $n-1$ 次。考虑先求出全过程再说，于是我花了 $20\text{min}$ 模拟了一下吃蛇的过程。 - 根据往常惯例，我选择从后往前枚举全过程。经过一番激烈的思考，我发现最强的蛇会吃最弱的蛇，当且仅当从这一步到最后一步它不会被吃。否则游戏局面就会止步于此，我们就可以更新最后一步了。 - 想到了 $n^2$ 做法，还是比较兴奋的。花了 $30\text{ min}$ 写完了程序，发现只需要求当前序列的最大值和最小值就可以了。因此，我们只需要一种数据结构，支持以下操作： $$\text{求最大/最小值，插入、删除数据}$$ - 显然平衡树是能做到这些的。把暴力模拟改成了 $\text{set}$ ，过了第三个大样例。~~我一直以为最后一个样例是 $\sout{10^6}$ 的，直到最后几分钟才去测第四个大样例~~。 - 这个时候，比赛已经 $3.1\text{ hours}$ 过去了。 - 为了多弄点分，看了一下第三题的部分分。随便敲了一个 $\sum c_i=0$ 的情况（也就是没有操作 $3$ ），~~结果这个部分分洛谷自测挂了（悲）~~。 尽管心态有点崩，但还算坦然，收了程序签了字就出考场了。 中午还能在酒店吃饭，结果晚上只有汉堡了，悲。~~但是味道不错~~。在车上交流了一下，并没有问到第三题和第四题的做法。 当晚洛谷第一题的民间数据和江苏省的选手程序都出来了，交了一下，过掉了。挺高兴的，毕竟过了一条毒瘤题。 估分是 $100+100+30+75=305$ 。当然，这是最乐观的情况，谁也不知道大样例强度怎么样。 ### 结束后 $\verb!(Day 2)!$ 上午在学校自习（明天就要期中考试了，悲）。中午回家就发现洛谷的民间数据都造好了。测了一下， $260\text{pt}$ ，第二题用的 $\text{map}$ 被卡了（我怕不支持 $\verb!c++11!$ 所以不敢用 $\text{unordered\_map}$ ，尽管它可以通过洛谷的数据）。第三题只拿了 $20$ 分，骗分失败，悲。 ### 总结（谈谈看法） 第一题肯定是毒瘤题了。但如果仔细想想，只要不那么贪，哪怕你就是打表（模拟），也能拿不少分。 $1600$ 年以后不去贪心地追求公式 $\mathcal O(1)$ 算法，直接二分也很容易写。我觉得这题罪不至此。 第二题比第一题简单，就是题面有点烦……卡 $\text{map}$ 就挺谔谔了。但总体感觉还好。 第三题我不会做，不敢评价，爬了爬了。 第四题 $75pt$ 意外好拿，就是不知道正解怎么去利用这个单调性。我想到了“蚯蚓”那题（考前刚看的），结果还是不会写。 希望 $\text{CCF}$ 少爷机和出题人能手下留情吧（悲）