CSP-S2020游记

蒟蒻爆零的游记

Before the Beginning

转载请将本段放在文章开头显眼处,如有二次创作请标明。
原文链接:https://www.codein.icu/csps2020/

DAY0

去纪中考试……
周五中午提前回家,下午打了打板子,打累了就睡了一觉,睡醒了吃饭就出发。
提前一天跑到附近的酒店里,维也纳酒店,停车场的充电桩坏了,酒店的花洒水压过大。
附近的百果园很便宜,买了几十块的水果还送了把水果刀。
吃点水果就睡了,半夜爬起来上厕所……

DAY1

快九点才起来,酒店的早餐不好吃。
上午看了看以前的博客,看了看数论相关内容,虽然感觉并不会考。
出去吃饭,吃一家湘菜馆,味道还可以。
吃完去酒店集合,看到群里有人谈论普及题目,随口糊了个T3动态DP然后感到有些疑惑。
怀着被题暴打的心情上路。

虽然好像已经立冬了,但是太阳很大,穿长袖比较热。
跑到纪中的音乐厅休息,然后发现纪中的厕所没有纸巾。
休息了一会就出发去考场了。

等到两点半才能动电脑,然后毒瘤的密码两边带括号实在是令人迷惑。
键盘手感比较硬,体验恶劣。不过桌面上有 vim 和 emacs,算是比较贴心,不过不打算考场上用。
然后开始看题。
先把题看完。

T1:毒瘤大模拟,出题人**
T2:应该跟位有些关系,到时候再看。
T3:看起来好毒瘤,没啥想法。
T4:感觉暴力分比较多?比较可做的样子。

然后回来码T1,先打了一个暴力。
一年年跳,然后再跳月。打了好几个函数,调了半天过了小样例。
似乎已经过了半小时多了,看隔壁的小朋友也在T1,我感到有些操蛋。
然后开始码正解,分段硬上二分,拿暴力跑出几个关键值来分段。
二分地不够优雅,被判闰年卡了特别久。好不容易过了小样例。
一个小时过去了,时间有些紧张。

出题人**

然后一测大样例锅到飞起,fc 命令行输出一大团。
打开notepad++开始定点调试,修复了不知道多少个闰年有关的锅。
打了半天,然后发现取月份天数写锅了,忘记某个月只有21天了。
赶紧修好,然后继续被大样例爆锤。

出题人**

最后终于过了大样例,长出一口气,然后一测小样例又锅了。
我:???

又打了一会修好了,明明二分应该有简化不少才对,怎么这么难打。
其实主要是二分的是当前年份,而要拿间隔来算闰年需要+1 -1之类的来取整比较麻烦。

总之测了一发样例没啥问题,已经四点左右了,心态有点爆炸,没心思写对拍了,赶紧上T2.

T2 读题比较简单,然后随手先码了个暴力,枚举每一位算出需要的饲料,然后把对应的位标成可用,一发过了样例。
然后发现每种饲料跟一位对应,饲料根本没用,只要把养了的动物或起来就行了。
码完过了样例,看一眼 $k \le 64$ 随手开了个 ull 就不管了,没想到其实是会挂的……

此时四点半左右,还剩两个小时,感觉 T2 赚回来了一些时间,没那么紧张了,就出去上了个厕所。

又看回 T3,没啥想法,先打了个模拟纯暴力。然后发现其实全局乘可以用 tag 维护,然后加就 $\dfrac{add}{tag}$,处理一下逆元就可以了。
感觉也多拿不了多少分,懒得码,去看 T4 先了。

T4 看了一会,暴力分感觉挺多的,$n \le 10$ 就能拿到 40pts,但是没怎么想出来。
先把 $n = 3$ 打了,然后想想爆搜、状压之类的东西。
想了一会,对于每个剩余状态,似乎每条蛇的战力都是固定的。
再想了想,吃与被吃的对应序列其实是固定的,因为每次最大最小值唯一,假定每次每条蛇都选择吃,那么一定能得到唯一的 $n-1$ 长度的互吃序列。
如果一条蛇吃了之后,它后面会被吃,那它一定就不吃了。

感觉挺真的,先打个 $n^2$ 暴力试试。
打完过了样例,大样例测了测也过了,感觉正确的可能比较大,决定投入更多的时间。
其实打暴力的时候就想到能优化了。

把最大最小值用 multiset 优化,这样 $n \log n$ 就能求出互吃序列了,然后开个 vis 数组记录谁被吃了谁没被吃,时间戳清空一下。

总复杂度 $O(n \log n)$,看看数据 $10^6$ 自以为挺稳。

然而只剩一个小时左右,T3 应该来不及了,先处理些后事。

于是把对拍写了,T1 T2 T4都拍上,又出去上了趟厕所。

隔壁的小朋友似乎不在做T1了,前桌似乎在看函数调用了。

感觉T1很容易挂分,T2简单得令人有些难以相信,T4压轴总感觉应该没这么容易被做出来。

上完厕所回来,开始检查 freopen,放好文件。
然后感觉 $10^6$ 还是有些大了,于是写了个 fread 快读塞进去。
此时发现 T4 其实多组数据,$10^7$ 总数据量应该是跑不过去的,但我们要抱有对CCF 8700K的信仰!!!

其实应该就是过不去的,也想不到有啥办法优化,70pts不错了,扔掉不管。

加上快读之后挨个手测了样例,把T1 T2 T3 T4都调整到了能提交的状态,还剩20min结束考试,干脆去优化下T3暴力吧。

于是就照着原来的思路打了个优化暴力,可以做到 操作1/2 都在 $O(1)$ 解决,然后发现需要处理乘零的情况。
用一个时间戳来解决,测了下样例感觉没啥问题,把优化暴力塞到了提交文件夹里。

还剩6min左右,打算造组带乘零的数据试试。
然后造好了,锅掉了。
草草草。
离考试结束只有几分钟,赶紧回来看,决定交靠谱的暴力还是跑得比较快但有可能出锅的暴力。
查了下错,改了一个弱智错误,再测一发,又锅掉了。

虽然样例全过,但出题人说不定毒瘤地卡了这个点,然后挂得连暴力都不如?
犹豫了一下,然后考试就结束了。

没办法,只能祈祷数据水了。

出来跟同学汇合,先一起喷了一波 T1 的出题人,然后我问他们 T4,结果他们全去肝 T3 了。
就我觉得T4较为可做吗……(仅仅因为题面比较短)
然后对了一下 T2 的做法,安心了一些。
发现 T1 大家做法不同,T神打了暴力有80pts然后明智地放弃了??非神打了倍增之类的东西。
感觉我的二分又臭又长,130行,蠢到爆炸。

跟他们口胡了一下T4,他们似乎题都没怎么看,都说时间不够。我也觉得时间不够,一起痛骂了一顿出题人。

出去吃饭的时候他们把T3拓扑做法口胡出来了,我还在担心乘零处理错导致我爆零。

CSP与NOIP没有任何关系。

希望如此。

坐车回家,看你谷神仙们一起喷 T1,然后 OI题库 数据已经造出来了?
似乎全世界只有我不会 T3,枯了。似乎 T4 有些人没时间写……

教练在群里把广东代码发了出来,还赞美了特派员的勤快。

回到家,到 OI题库 上测测。

T1直接过了,T2 95pts应该是卡了ull,T3 暴力莫名水到 75pts,看了看评论是数据造水了。T4 带 $\log$ 做法有 70pts,跟题目里的数据范围比较契合。

我原来还疑惑那档分究竟是给谁设的,原来就是给我的啊(

粉兔造好了 T1 数据,去洛谷上交一发,也过了,不枉我将尽两小时的艰苦调试。
然后发现我的代码长度名列前茅(

是我太蠢了,好几个地方可以复用。

在群里膜拜 AK 的神 tiger,又感到自己的弱小。

T3 想了想还是不会,可能是脑子不好使了。

突然发现这场又没有动态规划,又没有树,学了一年的算法像是白学了似的。

看起来很有算法的 T3 我场上还压根不会……其实仔细想想应该也是可做的。

发现 T2 的数据范围可以把没特判卡掉四十分,希望出题人珍惜他的母亲不要这么毒瘤吧……

T4 有人说 OI题库 数据水了,希望我的乱搞没啥问题。

100 pts + 60~95 pts + 0~20 pts + 0~70 pts = 160~285 pts

大部分人都是 123 或者 234 的组合,而我 124 ??

最后,NOIP RP++

Update:洛谷自测 100+90+30+75=295pts
T4感觉多拿了5pts,而T3没特意卡0的点,不知道官方数据会怎么样。

Update:官方初评:100+95+55+70=320pts

本文标题:CSP-S2020游记
本文作者:Clouder
本文链接: https://www.codein.icu/csps2020/
转载请标明。

评论

  1. 3周前
    2020-11-08 3:40:47

    您太强了 我比您低100+

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇