前天和昨天考了省选, 在此做一下记录. 标点符号的风格可能比较混乱, 因为有些是回来的路上用手机码的. # Day 0 下午试机, 贺神来看我们, 于是又多了一个吐槽我的宏定义的人......QAQ
晚上和学长们一起吃饭.
吃完饭把一道未完成的题写完, 看《指环王3》以放松紧张的心情，看到了阿尔温选择成为凡人那里，然后去睡觉了，比平时早一些。但仍然无法控制焦虑的情绪，强迫性地想一些问题，最终并没有睡着多久（重蹈NOIP的覆辙）……
只睡2小时就去考省选是一种怎样的体验?
Day 1
早上带咖啡进入考场。考虑到睡眠不足带来智力-2的加成，决定无论如何先写暴力。
在考场的门口成功识别出兄弟学校的友人 ovo
原本准备出门前再看一眼emacs的配置文件（并不懂elisp，东拼西凑的QAQ），走到半路才想起，却没有带手机……在考场里果然敲错了（重蹈NOIP的覆辙……）。再加上本身去得比较晚，所以开始考试后10min，大家都在看题，而我还在尝试让文本编辑器正常工作。好像有点本末倒置......没啥关系啦……手动开启了几个模式，并回归手敲编译指令的工作方式……
考试开始15min后, 突然涌现出一波键盘敲击的声音. 有了一定经验, 这多半是在写暴力......
发现3道题的暴力都不难写，所以开始搞。
想不到我在考场上手写的第一棵平衡树竟然是Spaly……想不到花了几分钟才让代码通过编译……QAQ
第二题出了一些变量名打错的问题……
写第三题的暴力，发现这是一个二次函数，那对于某种确定的对应关系，最值可以O(1)地求出来？还是先写完暴力再说。
写完暴力是10:00左右。
捣鼓了一下表达式，发现的确如此。这就70分？又去确认了一遍题目没读错……
返回去看第二题。理解了一下p1=2p2这一条件的用意，开始思考部分分做法。和去年Day 1 T1有点相似。但过了好一段时间都没有成形的思路。
返回去看第一题。大概要用其他数据结构来维护这棵Spaly。画了画图，发现把最小结点单旋到根，树的形态很好确定。又发现题目确实只单旋最小最大结点。先前忘了这一点, 转而去考虑单旋任意结点这个更一般的问题, 所以没搞出来. 又去确认了一遍题目没读错......
只剩下一个小时了, 以我的能力很难写出正确的代码. 但还是决定试一试, 写不完就注释掉, 考完下发源代码之后继续写......
告诉自己要镇定. 离考试结束还有15分钟的时候写完了, 过了编译, 过了样例, 就没去管了.
考试结束.
马老师果然切掉了T1. 而我的T1得分目前是[20,100]上的离散型随机变量.
马老师还会做T2 Orz
回宾馆补觉, 但是没睡着. 然后起床接着看 <指环王3>. 看到一半, 得知成绩出来了, 但是有点怪......60分? rank 3 ? T1 大概是挂了, T3 0分? 全省集体看错题? CS说T3的数据可能有误......
心情稍微平静了些, 继续看电影. 如果我是精灵就好了, 然而我是个人类, 而且不在中土世界.
Finger_Leader同学和他的哥哥嫂子请我们吃海底捞. 得知马老师的T1出了点问题, 调试时的输出没有删除......删掉就AC了, 变全省rank 1. 很佩服马老师的某种特质: 楚变不惊, 永远满怀自信. 明天仍有翻盘的机会.
T3数据更正后, 发觉它被yp同学切掉了......Orz
晚上继续看电影. 魔戒被毁灭. 阿拉贡登基. 精灵的时代结束. 明天要考 Day 2.
Day 2
这次没把配置文件敲错.
第一题叫 dalao, 题面有点长. 第二题是几何......第三题求一下组合数就能拿到一定分数, 然而是对10^9取模. 不怕我会扩展Lucas.
拟定一个策略. 先写T3的暴力递推求组合数, 再写T1的暴力, 然后推T2的式子. 如果还有时间, T3写一写扩展Lucas.
T1加一个记忆化大概能拿到更多的分数, 但是一时犯傻, 以为嘲讽值会很大......留下一个彻底的暴力.
根据样例猜测T2只用考虑起点, 终点, 和所有射线的端点, 那么判一判线段和射线是否相交, 建图跑DAG上的最短路即可. 判断是否相交, 可以根据它们所在直线是相交, 平行, 还是重合分类讨论. 选用什么方程来刻画这些几何对象呢? 斜截式? 竖直的情况得单独讨论. 一般式? 线段的范围看x还是y仍要讨论. 参数方程! 刘汝佳老师好像在书上也是这么说的. 它的形式足以表达所有直线, 对参数t限制一下范围就能表示线段和射线了. 虽然并没有学习 <参数方程与极坐标>, 但是可以yy嘛......手算了一会儿, 把交点解了出来. 写完了程序. 发觉直线重合的情况考虑的不对, 修复了一下.
左边的小哥一直在狂点鼠标, 以为他在使用 Dev-C++ 单步运行的功能, 结果是在扫雷.
此时11点多, 可以去写T3的扩展Lucas. 又得现推式子, 因为记不清了......手动对拍, 发现出现了负数. 原来取模之后做减法没有加上模数. 离考试结束还有20min的时候, 终于差不多正确了. 试一试70分的极限数据? 1.6s才出解......而时限是10组数据1s......
翻车了......
为什么, 会变成这样呢?
算了, 这次估计得掉到我省平均分以下......
出了考场, 有点忧郁.
看到了wyl同学 QAQ
看了群里的讨论, 发现我把扩展Lucas的时间复杂度弄错了, 它带两个log, 而且在本题中常数较大.
去宾馆退房, 坐动车回家. 在车站, 成绩出来了. 105分? rank 2? T2的数据怎么这么弱? T3怎么连基础的暴力都挂了?
稍微松了口气, 感觉T2有可能重测.
同学说, uoj群里说, T2各路乱搞拿到高分, 最奇葩的是, 输出 "nan" 获得100分, 更神奇的是, 这位仁兄就在我们省......挺厉害的......
T3重测了, 我又掉了15分. 忽然想起, 暴力递推的版本, 取模之后做减法也没有加上模数. 为什么犯了这种错误......不过我的rank变得正常了, 比较公平. 忽然发现我T1的暴力拿到的是记忆化搜索的分数......今天的数据真是神奇......
后记
以上是本次省选之旅的记录.
精神疲惫, 并且最终的结果是6道暴力.
很难控制焦虑的情绪, 因为我知道自己实力不足. 实力充足体现出来是什么样的呢? 看一看WJMZBMR的IOI游记便知......
对于我而言, 考试还是先写暴力比较稳妥. 看了题目之后, 要大致确定一下接下来的几个小时怎样虐待自己. 要镇定, 即便这不容易.
要提高算法水平, 争取写完暴力之后还有事做, 争取能用上对拍脚本. 争取代码一次写对, 注意细节.
EOF