GXOI 2020 游记

每一轮都会有三个阶梯，现在第一次过了第二阶梯，留下一些纪录，结束一个阶段的学习，开启一段新征程。 试题是B卷。 ### $Day -7$ 开始停课冲刺，每天写题总结刷题，以及在机房摸鱼。 ### $Day\ 1$ ~~入场即可领取价值的价值$700$元的无限能量包和无限续杯农夫山泉，配备不可上网的点，堪称南宁最高配，自助餐厅。~~ ~~day 1没有自带零食真的亏了。~~ 有些时候考后绝得非常简单的题目，考场上未必能够一下子做出来，比如$T1$，高估难度下，直接读错题，理解成选**任意一段**消除，将新的牌添加到最左侧。 这题直接把我搞自闭了，想了一个半小时以上，中途跳去写了$T2$，还有$T3$的暴力，最后还剩大概半个小时了，回头一看题目，人都傻了，花五分钟敲完，过一遍大样例。 ~~要是当时放弃的话就要调出省队了呢。~~ $T2$是一道点分树的板子，询问树上距离$u$距离为$k$的点有多少个，也可以用点分治，但是感觉不够点分树自然。一开始嫌麻烦还想用静态链分治做，但是想想也不知道怎么转移，最后写了点分树。 寒假唯一钻研的算法，结果考了板子，还是有点庆幸的。 不过说实话感觉考板子的行径不适合放在省选呢。 $T3$是$A$卷的$T1$，这就是强弱省的差距吗?? 题意大概是两个非负整数数组，求使$min(pre_{a_i}, suf_{b_i})$的最大值以及此时的$i$。 实际上就是求两条直线的交。 第一时间想到的是三分法，但是由于不严格单调，用不了，考虑过平衡树维护值域之后再三分法，可以做到$O(nlog^2n)$，能拿下$60$分部分分，但是感觉自己码不完（只剩下一个小时多一点时间了），就放弃了，先码个暴力。 期间想到过一个暴力优化，就是通过上一个答案位置进行转移。可惜由于细节太多，我写个完全扫描的暴力以及感觉心态爆炸了，就没有去写。而且当时想的是这玩意是肯定会被卡，只需要在端点插入删除一个很大的数就可以了，毒瘤出题人怎么可能不卡呢？ ~~然而讨论区有人用这个A了这道题。~~ 正解是作差之后线段树上二分求零点，现在一看也非常简单，有一种我为什么没有$AK$的感觉，大概这就是考场吧。 最后三十分钟写了暴力对拍$T2$，毕竟最慌的$T2$会不会写炸。 然而正解写对了，暴力调到结束还没有调出来。 ~~由于暴力程序的遗失，我们至今仍未知道暴力到底炸了哪里。~~ ### $Day\ 2$ 买了两根香肠和一包苏打饼干，苏打饼干吃起来可能会有点声音，但是感觉完全没有键鼠吵。 作为前一天的教训，这次的$T1$很认真地看题了，搞明白题目的意思，信心满满地交了个离散化+差分。 结果值域没有加够，没有提供规避区间的选择。 以后遇到这种还是把加一减一全部丢进去，反正都是常数。 $T2$状压$dp$，但是想到正解方向的时候已经比较晚了，不到一个小时这样子，没有考虑清楚就开始敲了，结果是爆炸，没有写出来，只有暴力分。 $T3$现在还不会正解，写了个状压，开数组的时候没有认真计算，导致丢了$15$分。 ### $Day\ 2+$ $100+100+30+60+30+35$ 没有发挥出理想水平，但看起来也不差。 马后炮是人人都的，现在看来的话我觉得自己可以写到$555$，只有最后一题是真的不会感觉也想不出来。 考场上总是有各种各样的遗憾，只希望以后会做得更好。 接下来就是对标外面的强省了，大概要被虐菜了。 ### $others$ 既然是纪录，那当然应该有索引啦： [比我小还比我强的大佬JasonL](https://www.luogu.com.cn/blog/JasonL/gxoi-2020) [wzy大佬](https://www.luogu.com.cn/blog/GamerDiaosi/gxoi2020-dian-di-ji) [关于兄弟学校选手考GXOI这档事](https://yuwenzhou-sakana-chn.blog.luogu.org/gxoi-2020-you-ji) [卡密甜柠檬的GXOI 2020——走在告别路上](https://www.luogu.com.cn/blog/Sweetlemon/gxoi-2020)