囧仙 的博客

囧仙 的博客

CSP2020-S 【游记】

posted on 2020-10-13 23:49:51 | under 游记 |

前言

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

  • $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

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

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

  • 第二十题相对有难度,这种背包优化没看过()

    • 第一小问应该是 $\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}$ 少爷机和出题人能手下留情吧(悲)