游记 【CSP2020-S】

囧仙 · 2020-10-13 23:49:51 · 个人记录

前言

• 此时的囧仙中之人是 @离散屑波变换 。以下的游记都是这个屑写的。

• 初赛得分 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

• 第六题先是不会。但这提示的也太明显了，随便讨论讨论逆序对就出来了……

• 第十九题似乎在你谷有原题的样子。引恐禁三警告。很水。

• 第二十题相对有难度，这种背包优化没看过（）

  • 第一小问应该是 \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 天、巨麻烦的闰年判断）直接被砍没了……

• 然后考虑二分年份，计算它和 1600 年之间的天数只差（因为我数学不好，为了防止奇奇怪怪的边界条件，我选择计算差值，这样就能统一削除误差了）。确定了年份，月份和日期可以直接枚举。

• 对着大样例调了一会儿，过了。这时候我非常高兴。这时候比赛已经将近 2 \text{ hour} 过去了。

• 做完了第一题就回到了第四题。我发现，吃蛇的顺序是永远不变的，并且最多会吃 n-1 次。考虑先求出全过程再说，于是我花了 20\text{min} 模拟了一下吃蛇的过程。

• 根据往常惯例，我选择从后往前枚举全过程。经过一番激烈的思考，我发现最强的蛇会吃最弱的蛇，当且仅当从这一步到最后一步它不会被吃。否则游戏局面就会止步于此，我们就可以更新最后一步了。

• 想到了 n^2 做法，还是比较兴奋的。花了 30\text{ min} 写完了程序，发现只需要求当前序列的最大值和最小值就可以了。因此，我们只需要一种数据结构，支持以下操作：

• 显然平衡树是能做到这些的。把暴力模拟改成了 \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} 少爷机和出题人能手下留情吧（悲）