HNOI2020同步赛退役祭

Imakf · 2020-06-18 22:11:47 · 个人记录

前情提要

菜鸡 Imakf 因为联赛爆炸了失去了去 HNOI 的机会……

只能为高二同学和yxt和yfy和我的爱豆soulist场外加油啦！

关于我联赛爆炸的经历可以看看可以看看可以看看这个：

https://www.luogu.com.cn/blog/Imakf/ji-you-jiang-2s-psc

https://www.luogu.com.cn/blog/Imakf/xiguanle

\texttt{DAY -1}

Imakf：oejiwojoitjoww5%#)@^#Vv勘破神机235几3九v就撇具体为拒签哦v……

Daniel_yuan：欸我之前去北京集训的时候，那个出题人把 3\times n 改成了 8 \times n 给我们做。

众人：/jk

Daniel_yuan：你们知道这题的数据范围为啥是 52501 嘛？

Imakf：不会是谐音梗吧…… 501 是哪位？

Daniel_yuan：出题人是个人赢，501 是他 npy 学号。

众人：狗粮吃饱了。

\texttt{DAY 0}

好像要去烈士公园的样子……和 Daniel_yuan, fhs_lzx, _wxyz 。xiaolilsq 因为身体原因时间冲突没法去qwq。

一开始没带伞，走到篮球场突然雨变大了，就回机房顺了几把伞。然后讨论了一下显然今天下大雨的事实，浏阳河探险队员，有向图探险队员，楼主湘潭县第一之类的事情。没有办法去省选的弱弱只能一边感叹自己的弱，一边祝神仙考个好成绩。

到了公园，先穿过了一片林子到了游乐场——然而我们并不能玩。再往前走就经过了湖，相亲角的旁边有一家蓝蓝路，店员热情地接待了我们。我们在M记吃了会炸鸡，看了会金鹰卡通。返璞归真一会~Ysu 说待会我们要去划船，在船上我们要玩游戏，输的了有惩罚。

大家果然来了兴致，但金鹰卡通实在是太好看了，大家实在不肯离去。终于Ysu说我们走吧QWQ。

结果船上的惩罚游戏就是谁输了谁去驾驶脚踏船……规则是，对于下列两个问题，顺时针每人说一个答案，谁 5s 之内说不上来谁就去开船：

• 请说出一种数据结构的名字。
• 请说出你在机房中干过的，且船上其他人没干过的事情。

数据结构嘛……大家说了一大堆高级数据结构，结果根本没意识到链表、栈、队列都没说。

第二个问题就简直是黑历史大会/Daniel_yuan的炫CF/ATCODER rating/Ysu的炫教练特权大会……

呐呐呐，不知道为什么，我踩了 \dfrac{2}{3} 程的船，船开到一半，显然又开始下大雨 >_<。不知船是什么神仙设计的，打在顶棚的水滴全部会滴落到船侧面的栏杆上，溅得到处都是（好像只溅到了我），结果我只能在船上打把伞。

下了船之后，我踩了一滩水……

回去的时候我们好像聊得挺开心的，贴心的 Ysu 给 xiaolilsq 带杯茶颜悦色作为补偿（

中午偷偷打了下邦多利，下午好像在划水（好吧其实 vp 了场 cf，然后人均 4 题我 3 题哭了，问题是前三题我做的最快，然后被 D 卡到自闭了……）

晚上好像也一直在颓东方吧……

\texttt{DAY 1}

《幻视》

我上个厕所，

地上盆子倒扣，

大概是匡瓢；

回来定睛看，

原来是破铃铛

懂了，我爆零了！

有人来破译一下这首诗吗

原本以为可以 10 点考到同步赛，结果咕咕咕到了 1 点。

初三和高一一起坐了辆中巴，12:40 赶到了*********学校，走进学校，三步检查，房卡体温健康码。推门而入——

不得不说，这里实在是太大太空旷了，给人一种财大气粗的感觉。机房的各种线路都被罩在钢板里，外面看不出一丝杂乱，非常清爽。屋顶用六边形的平板装饰着，体现着数学之美。这里将会成为 NOI2020 的考场。“要是我能来当志愿者给 C 神端茶倒水有多好啊！”我心想。

回过神来老师带着我们到角落就坐，似乎高二在这里考过省选模拟，有几台机子没被还原233。

然后老师说我们 1 点开考……好像这时候正式赛就下考了……没想到**为了防止作弊竟然如此细致仔细！爱了爱了!

我马上调了一下 vim，我搞了三个快捷键：<F9> 编译，<F8> 用 gedit 打开，<F5> 用 gdb 调试。然后写了份对拍程序，搞了个 a+b.cpp，结果马上就开考了！

考试开始

拿到题目……怎么题目都这么长啊？哦这个 T2 最短，咋是个数学题啊？看来只能硬着头皮去看题目了……

\texttt{T1 icefire}

前缀和，三……分？

仔细一想发现不太对，整数域上面肯定有很多重复的，所以三分不了……

那就是……二分……赶快敲！树状数组！

不对啊……打完才发现这不是 \log^2 n 的吗……好，那就当打个暴力，也可以当对拍 233。

一测样例，发现没过！！！原来是树状数组下标不能从 0 开始，但我离散化是从 0 开始的，改了之后样例 1 过了，样例 2 依然没过 QAQ。

正当我绞尽脑汁，按下 <F5> 时，整个世界突然变得黑暗……

这个时候正好是 1.5h。

老师马上来紧急通知：“不要吵闹交流题目！大家快抓紧时间休息一下，我们等电来了继续……”我自然不能浪费这大好时间来睡觉啊，于是我继续思考 T1 正解。然后我就想有没有啥可以直接在线段树二分一次就能得到答案的方法……

结果事好的，我好像想出来了，找到冰比火多的最后一个位置和火比冰多的第一个位置就行了！查询就像平衡树查前驱后继一样，可以直接用线段树维护！！！太激动了，我居然可以做出一道省选题！

终于不紧张的我遵循老师的意见，开始睡觉啦！

等了 1h 后，老师说，怕是不来电了，要我们马上坐车回去。

我问老师这停电是怎么回事，老师说：

***本来有两根高压线的，坏了一根另一根还能接着用，你们运气是真的好。前几天断了一根还没修，今天又起火自燃了一根……我们一中肯定不会有这种问题的。

老师接着说，因为拿不到刚刚写的代码，回到一中还给我们 0.5h 回忆代码的时间。太爽了哈哈哈！

我们刚走出门，灯光就打在我们的背影上——来电了。

黄人问号.jpg

我马上冲回去打开电脑，码刚刚想到的思路。

结果电脑重启了之后时钟不对了 /jk，所以此后的大半时间我都只能靠生物钟了。

码了很久，调了很久……调到一半调不出来就先去看了下 T2，这个下文再讲。终于调到了【答案正确，但方案不正确】的地步了。此时我发现可能还需要一个二分，但是一想想：单次就要【修改】*1+【查询】*3，是不是常数巨大啊……

写完之后，样例 2 过啦，常数确实巨大……本机极限数据 4.5s……怕是完蛋了。于是我最后的时间里一直在给这题卡常……

\texttt{T2 problem}

怎么还有这么没诚意的名字啊（

脑子短路，觉得 1\sim 3 太难了，就先写了 4\sim 6。再看到 7\sim 8，发掘就是个二项式定理……马上删了直接补了个 (x+1)^n。

然后终于发现组合数是可以递推的！把 1\sim 3 过掉力！时间紧迫，马上滚回去调试 T1 辣。

\texttt{T3 shop}

大概没怎么想，暴力都很难打的样子……不如去给 T1 卡常啦！

结束了…… T1 才卡到 4.3s，可见我卡常水平之低。

回学校路上大家一开始有说有笑，最后都累到不说话了。

其实挺想问问 Daniel_yuan 的成绩的……但是还见不到他人。

正式选手们要加油啊！！

\texttt{DAY 2}

上午一直睡到 10:00，累死力……

起床后开始单曲循环《少女綺想曲 ～ Dream Battle》，恍惚间想起自己好像什么时候学过钢琴的样子，要不就练练吧。试了一下右手，有点自闭……

时间过得好快，一下就到了中午，简单吃了点饭就去了学校门口集合。11:45 居然还没人（汗)。过了一会人到齐了就出发了！

感觉在车上没聊什么，大概 Tiger1033 给别人糊了几道神仙题——显然我是做不出的，为了不影响自己的心情我赶快闭上了(?)我的耳朵。然后大家有猜了几个题目名称：【辟配】、【纸糊船】。

对了，昨天一道 dp 都没有，今天是不是 3 道啊？
昨天也没考字符串呀……而且也只考了一道数据结构！
懂了，今天是在 AC 自动机上优化建图跑 dp！
——一群人瞎吉儿闲聊

今天有个 count！ ——fhs_lzx

进了考场，依然没有数清这里有多少台机子……打开昨天机位的机子，发现并没还原卡，昨天写的对拍程序还挂在桌面呢……进了终端输入了个 metacity -c 然而没有透明成功，想起 ztz_cpp 的忠告，于是就干脆用了个假透明QAQ。

考试开始

好的，我一个题目名称都没奶中。

不好的，怎么都不开 O2 啊？

\texttt{T1 transfer}

说实话这个题目名称很不爽……原因是我在终端里输入了 cd t<tab> 没给我自动补全，然后我写了个 cd tr<tab> 还是没给我补全，原来还有道 tree……

嗯 30pts sb，但是不想写……这个什么鬼东西 O(2^mm) 能过吗？算了下接近 2e8，大概少爷机是可以过的吧，不过两天的 T1 都卡常就很屑。

想了一想，发现有个显然被卡空间的 dp，想了几十分钟想到如何省空间了……把信号塔拆开算贡献就是了……于是花了 1h 过了此题。测了大样例 2.8s /jk。经过 30min 的卡常，变成了 2.3s。

啊？我居然又能做出一个省选题？

\texttt{T2 tree}

这波啊，这波是 52501。

好不可做啊……反正时间还够，写个 10pts 暴力先吧！

……后面好像没啥部分分可做唉……这咋一个 \log 做嘛？

分析一下，我们只要做这个：

区间 +1，区间异或和，如果这两个可以用线段树做的话就可以强上线段树合并。

但是我并不管前面这两个东西能不能用线段树，直接先敲了个线段树合并 QAQ。想了一会发现好像并不行 >_<。于是就跳了题看 T3。

做完 T3 我又滚回来看，发现可以按位考虑，考虑一个节点对于从它到根部这一位的贡献，发现是一个隔 2^k 位切换一次的开关，我们只需要知道开关的开始位置，并且知道相同开始位置的开关的奇偶性就行了。发现可以线段树合并！

码完力，调了很久，好像终于拿到了 40 分 O(n \log ^2 v)……

\texttt{T3 count}

fhs_lzx 带预言家实锤了！！！

这波……这波还是 52501……

显然不可做，马上敲了个暴力，就有 10pts 啦！

啊，怎么还有个基环树，就又有 20pts 啦！

啊，怎么还有个矩阵树定理，好像忘了，哦记起来了，就又有 20pts 啦！

啊，怎么还有容斥啊，就又有 20pts 啦！

啥啥啥，这暴力有 70pts！？

结束了……为啥 D2 比 D1 暴力分多。

一想到要回去学文化，我就生无可恋了……

那我这个场外选手就祝正式选手们都进队，然后 NOI Au 脱离文化课苦海吧！

总结

稍稍总结一下吧。其实想来，这两天我还是比较莽的——坚信联考必然一天一道送分题，所以上来就直接怼 T1。还好最后是赌对了，确实是送分题。

第一天考得有点不好……也是因为 T1 占用了太多时间（将近 3h），如果再腾出来一点时间说不定可以用来推 T2 式子。

高级暴力分数与去年基本持平：