【杂文】SCOI2020 游记

# **【杂文】SCOI2020 游记** [$\mathcal{My}\ \mathcal{Blog}$](https://www.cnblogs.com/Xing-Ling/p/13200642.html) 在这篇日记里记录省选前夕至考试当天的事情，可能会写考后题解，也可能没有。 ------- ### **时间：2020-5-28** 今天教练开始组织专题复习了，首先是计算几何（~~发给我们的题单全是板子~~）。 ------- ### **时间：2020-6-3** 开始复习数据结构（~~虽然题单里大部分都是 splay 和 LCT~~）。 顺便狂刷了一波字符串，现在闭着眼睛都能把 $\text{LCT}$，$\text{AC}$ 自动机、$\text{SA}$、$\text{SAM}$ 打出来。 ------- ### **时间：2020-6-8** 学了一个以前从没听过的新东西：圆的反演。 ------- ### **时间：2020-6-11** 花一上午时间学了插头 $\text{dp}$ 。 下午和晚上继续疯狂刷题，数了一下今天写了 $17$ 道（雾）。 ------- ### **时间：2020-6-12** 填了一个以前挖的[坑](https://www.cnblogs.com/Xing-Ling/p/12708360.html)。 ------- ### **时间：2020-6-13** 刷树形背包，顺手学了下长链剖分（~~为啥感觉每天都在学新东西啊~~）。 ------- ### **时间：2020-6-14** 之前写的[点分树](https://www.cnblogs.com/Xing-Ling/p/12976848.html)成功通过[洛咕日报审核](https://www.luogu.com.cn/discuss/show/47327?page=857)，可惜在退役前是肯定看不到的了。 ------- ### **时间：2020-6-16** 突然迎来一个劲爆的消息：今年的省选考试被阉割成一天了，上午报道、下午 $3$ 道题机试、晚上申诉。至于笔试、面试之类的直接 $\text{SPFA}$ 了。 啊这..... 就 $3$ 道题我 $tm$ 考个 $chui\ zi$ 啊，要是有一点失误就再没有机会翻盘了。 拼 $rp$？ 自闭 $ing...$ 晚上整理了一下资源，[模板库](https://www.cnblogs.com/Xing-Ling/p/10930556.html)施工完毕。 ------- ### **时间：2020-6-17** 开始复习板子。 一天总共只打了 $43$ 个，比预想的要慢一些（主要是那 $22$ 个线段树太蛋疼了）。 ------- ### **时间：2020-6-18** 下午模拟考试人均 $50+10+20=80$ 。 写了一堆贪心+暴力剪枝，总分 $50+30+40=120$，骗分苟到了 $rk\ 1$ 。 ------- ### **时间：2020-6-19** 板子复习完毕。 下午模拟考试一堆暴力加起来又苟到了 $rk\ 1$  晚上翻出了以前写的[斜率优化](https://www.cnblogs.com/Xing-Ling/p/11210179.html)，修锅ing... ------- ### **时间：2020-6-21** 其他省份的巨佬正体验着 $\text{AK}$ 全场的快乐，而我在机房里听着音乐玩 $\text{DS SW}$ ... 下午日环食现象出现时我们在模拟考.... 今天 $\text{T1,T3}$ 都写出了正解，$\text{T2}$ 是一道凭大样例找规律的题，但至到考试结束也没调出来（后来发现是因为多数了一个 $0$），被 $270pts$ 的 $pkh$ 巨佬吊起来锤 $\text{stOrz}$ 。排名 $rk\ 2$。 ------- ### **时间：2020-6-22** 模拟考 $rk\ 2$，被 $pkh$ 巨佬吊锤 $44pts$ 。 $\text{T1}$ 是个决策单调性优化简单 $\text{dp}$ 的板子。$\text{T2}$ 毒瘤图论，只写了 $20pts$ 的蒟蒻二分图。$\text{T3}$ 分别写个 暴力树剖 $\text{LCA}$ 做 $n\leqslant 5000$、点分树上维护 $\text{vector}$ 解决无修改、点分树上维护 $\text{vector}$ + $\text{CDQ}$ 套线段树解决离线、树状数组套主席树解决链，总共能获得 $80pts$ 的部分分。  最后只码了树剖和点分树，在写树套树时脑子一抽以为做法假了（其实是没有问题的），便直接放弃挣扎，只拿了 $50pts$ 。正解貌似是边分治，可惜窝不会。 ------- ### **时间：2020-6-23** 最后一场模拟考试了，依旧是 $rk\ 2$，被 $pkh$ 巨佬吊锤 $43pts$ 。 三道都是 $\text{CF}$ 上的原题，然鹅我只在刷 $\text{IOI2020}$ 集训队作业时做过[$\text{T3}$](https://www.luogu.com.cn/problem/CF611G)..... [$\text{T1}$](https://www.luogu.com.cn/problem/CF513G3) $66pts$ 的暴力 $\text{DP}$ 被卡常到 $39pts$。[$\text{T2}$](https://www.luogu.com.cn/problem/CF573E) 最后半小时想出了正解但没时间写了（$\text{Splay}$ 维护 $\text{DP}$）。 ------- ### **时间：2020-6-24** 核酸检测比我想象的要温柔得多，只是碰一下就做完了。 ------- ### **时间：2020-6-26 (Day0)** 上午把计算几何的所有板子都敲了一遍。 教练从校长那儿嫖来了一辆长长的的商务车，来接送时停在了教学楼底下人群最密集的地方，而上车时又恰巧午睡刚结束，于是周围一大片好奇宝宝都用看猴子似的目光盯着我们...... > 风萧萧兮易水寒，壮士一去兮不复还 ~~晚上打了一晚的饥荒。~~ ------- ### **时间：2020-6-27 (Day1)** #### **早上** 打了一下 $\text{LCT}$、花花特、$\text{SA}$、$\text{SAM}$ 板子。 早饭点了外卖，南瓜粥吃完肚子暖暖的。 #### **下午** 关于只考 $3$ 道题这件事我还是不能释怀，来都来了多考一天有什么不行的嘛，服了。 另外，考场是在大厅临时搭的+键盘巨 $\text{tmd}$ 难用，还要求一直戴着口罩，热得要命....像这样的小情绪有一大堆，但都不及考后心情上下起伏时的痛苦。 开考前打好了头文件和一个对拍板子。 开考后首先花了半小时看题。 $\text{T1}$ 一眼 $40pts$ 暴力枚举三点确定一圆，$\text{T2}$ 应该是个数学计数题，可能要用到组合数之类的东西，$\text{T3}$ 好像是个数据结构大题。 回过头来想 $\text{T1}$，貌似可以圆的反演？对这个东西不太熟悉，便换了个思考方向：考虑求出 $P_1P_2$ 的中垂线 $AB$，用其将二维平面分为两半，那么仅当圆心在靠近 $P_2$ 的一边时合法（我取的是右边）。而根据向量法三点确定一圆的理论，两条中垂线求交直接就得到了圆心，所以我们求出 $P_1$ 与所有点的中垂线 $L$，再按极角排序，并求出它们与 $AB$ 的交点 $Q$，见下图：  可知对于任意的 $j<i$，仅当 $Q_j$ 在 $Q_i$ 上方时满足$L_i,L_j$ 的交点（即 $P_1,p_i,p_j$ 三点外接圆心）在 $AB$ 右边。 到这里其实答案就快出来了，求出 $AB$ 的极角 $k$，把所有点围绕坐标原点顺时针旋转 $(k-\frac{\pi}{2})$ 度，使得 $\vec{AB}$ 恰好竖直向上，然后对交点 $Q$ 的纵坐标离散化，树状数组维护二维偏序即可（也可以不旋转，但似乎会很麻烦，所以没有细想）。 有很多实现上的小技巧可以简化代码，所以并不难写，考场上我只花了约二十分钟一遍过大样例，当时还担心旋转操作被卡精度，结果写出来发现至始至终都没用到 $dcmp$，看来应该是稳的（为某位强行分类讨论结果死活调不出来的同机房巨佬默哀）。 后来检查时发现离散化没有去重，但因为提前按照极角排了序，刚好可以处理交点重合的情况。 $\text{T2}$ 应该要用到生成函数，完全不会，暴力只会 $20$，自闭 $ing...$ $\text{T3}$ 要用到 $\text{CF}$ 上一道题的建图 $trick$，我以前有做过类似的题，但考场上却完全没往这方面想，再次自闭。暴力依旧不会打。 于是后三个半小时总共就拿了 $25pts$ 。 没有心情玩扫雷，只是一遍又一遍地检查着代码。 值得一提的是，检查时改出了不少 $\text{bug}$，包括写法问题和看错题目等等。 最后几分钟开始胡思乱想。 $\text{T2,T3}$ 真的好难好难.... 希望能听到 $pkh$ 报出和我同样的分数。 那样的话应该就能进省队了吧....似乎会很开心的亚子.... 心跳突然加快，比 $\text{CSP}$ 那时还要紧张。 ..... 当看到 $\text{pkh}$ 一脸“难受”地说出 “怎么办，我只有 $280pts$，前面好像有一堆 $\text{AK}$ 的啊”，我知道我是彻底没希望了。 本以为应该逐渐接近他的水平了，但这次考试使我再一次清楚地看见了那条横跨在我们之间的鸿沟。 总分：$100+20+5$ 。 心有不甘。 但技不如人只能认命。 只能恨自己脑子不够灵光，三个半小时连一个分数高点的暴力都想不出来。 #### **晚上** 饭桌上我妈在和 $zth$ 家长商量留级重学高二的事，我实在是待不下去了，便想自己一个人出去走走。 > 两年 $\text{OI}$ 一场空。 要止步于此了， 心情很是沉重。 会发生奇迹吗？ 不要在这时候再给以希望啊.... 感觉整个人都快倒下了——我的心理承受能力可能并没有我妈想象得那么强大。 一个路痴在路边兜兜转转，躲着人群，朝着夕阳走进，穿过一片绿荫，瞎晃悠着最后又回到了起点。 ...... $pkh$ 正在外面打电话，见我回来立马说道 “你好像是 $\text{rk 17}$，有希望进省队。” 奇迹....好像真的发生了..... 算上校限，刚好卡在线上，作为最后一名苟进了队。 日日夜夜甚至是梦里都一直盼望着的东西终于够到了。 但我高兴不起来。 只是一味地想哭。 当家里人和表哥都同时发来鼓励话语时，眼泪都快喷涌而出了，但当着大家的面又不好意思，只好扭过头去迅速擦干。 ------- 我又前进了一点。 （向着那颗天边的辰星） ------ ### **时间：2020-6-28** 晚上简单看了看生成函数的定义和斐波那契数列通项式的推导，回过头来推 $\text{T2}$，发现就是个傻逼题，草（中日双语）。 为什么不早点学啊... （公式太多懒得写题解了） ------ ### **时间：2020-6-29** 照着省队名单挨个了解了下，只有我是从高中开始才接触到 $\text{OI}$。 不知是该骄傲还是叹惋。 只能在心里悄悄羡慕一下。 但无论怎样，尽快提升自身实力才是正道。 希望参加 $\text{NOI}$ 后能给自己的 $\text{OI}$ 生涯交一个满意的答卷。