HNOI2020同步赛退役祭

## 前情提要 菜鸡 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%#)$@^#V$v勘破神机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> 时，整个世界突然变得黑暗…… $\texttt{考场停电了。}$ 这个时候正好是 $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$ 式子。 $T2$ 我则是出于【没有时间】+【对于省选数学的恐惧】，没有仔细思考，而是只观察了部分分、实现了部分分做法。回到教室仔细想来，考场其实完全有可能做出这个题的。这么一说，好像我还是没有改掉 Ysu 说过的“思维定式”的问题。 $T3$ 则是【完全没有时间】+【暴力复杂度好像不对】而根本没有写暴力，也算是小亏了一波。然而考后知道这是个“保序回归”问题，则是庆幸没有考场硬刚这个题。 第二天于是就调整了一下自己，上午睡了很久 + 听歌。 这一天 $T1$ 我记得 Ysu 是给我们很久以前考过一个类似的题，我觉得我应该能想出来，于是就一直怼这个题，结果在 $1h$ 就做出来了，挺惊讶的。感觉是最近集训积累的挺多套路还是有点用的？ 时间还有盈余，我就先打了 $T2,T3$ 所有暴力。矩阵树什么的还好记得，不然又是白白损失 $40$ 分。 再来单独想 $T2$，倒是没有想出正解如何，凭借着 HNOI 选手的做题思路，往各种数据结构上套，总算是观察到一些性质，套到了线段树合并上，也在最后的时间成功打出来了。 我自己的估分是：$[60,100]+40+0+100+40+70=[310,350]$。 -------- 感觉自己考前也没有复习什么东西，基本上都是靠的平时积累和最近集训的内容——这可能是我个人的一大特色。该拿的分也都拿到了（只希望不要卡常）。省选的时候感觉时间特别紧张，以至于根本没有时间对拍，只能靠 ccf 给的几个大(小)样例来调试。（希望不要挂分） 感觉今年原题有点多，对于板刷 AT 、CF 选手自然是十分友好。也确实，我从停课以来一直和我们组的几位聚聚一起做 CF，Daniel_yuan 也带着我们打 AT。我最近一次打线段树合并就是 AT 的 F 题，想必如果没有这个题，我恐怕就少了 $30$ 分。但是这些网站上的题目质量也是参差不齐的，要提高对自己的要求，不要满足于在 $div2$ 的前 $4$ 题上。考后要钻研 tutorial，把最难的几个题改出来。 之前也有提到过，省选的暴力分呈现越来越少的趋势，比如今年纯暴力分有： $30+30+0+30+10+30=130$ 高级暴力分数与去年基本持平： $60+40+?+80+40+70=310$。 数据结构依然是大头，其中一道中档题，一道简单题，与往年类似。dp则减少了，且放在了简单题的位置。 可以看到__数学题__数量有明显增加，有 $3$ 道，__线性代数__则破天荒的增加到 $2$ 道，让人不得不重视数学方面的内容。 我今年是深刻体会到了被卡常数的恐惧，两天的 $T1$ 我本机都比额定时间也要多出很多。借用一下 lzx 的话： > 卡常数也是今年省选的一大特色，两天 T1 ， DAY2 T3 均有卡常之嫌。这可能对选手的代码实现能力提出了更高的要求。在平时做题的时候，其实并不应该喷毒瘤出题人谢题卡常数，而应该练习如何更高效，更好地实现一份代码，这必定也是今后的学习中需要练习的。 今年省选的心态倒是非常好的，没有什么升学压力，且没有亲临考试现场，参加了这么一场同步赛。同步归同步，它也是对我们省选停课的一次能力检验。能在停课时与同学每日交流毒瘤题，考试学习，倒是现阶段莫大的幸福。这次同步赛也让我觉得，努力是肯定有回报的。 省选结束了……但下一轮还有 $5months$ 后的 NOIp。自强基计划出台后，想必停课时间是没有多少了……一定要更加抓紧长假时间。但现在，更重要的是迎接期末考试，捡起失落的文化课。呐，让我们所有人一起加油吧！ ## 对此文的评价 家母：别写这种“退役记”，宝吧！ 家母*2：你把你写的那个什么微博删掉吧。 ## 后记 被卡常了 + 容斥写挂了。 $60+40+0+100+40+50=290$