CSP2019 游记

## Last Sunday 祝福 老爸给我充饭卡的钱是600，“你知道是什么意思的，哈。” 背向他的时候，回想最近一年，感到如此对不起他。 ## Day -1 最后一场模拟赛 第一页写着“信心赛”，果然，T1是余数差分题。T2T3似乎也可做。 三个半小时过去了。T2一直徘徊在4个set写起来快还是2个扫描线写起来快，最后两个都没写完。交了个T1上去，爆了零。 今天就不夜跑了。 ## Day 0 秋游 理论上的open day。吃完早饭突然想到，秋游必是孤独之旅，于是决定待在机房玩，看看做题记录、历年原题和tarjan。 上午安静地在hsy电脑上玩95版PVZ。下午晚上类似。安静地颓废，才是彻底的孤独之旅。读一读他们秋游的动态。 20:00想起tarjan，慌忙搜博客，两三个人，静谧的机房。“昨天他们坐在第一排的时候还是那么热闹，然而以后都不会再有了。” 还是要给自己鼓鼓劲。喝牛奶早早睡觉。 ## Day 1 继续调试的决定 ### 7:40 缺氧 下车立刻入场。真实的地下车库考场，深刻暗示着没有O2开关的吝啬。还想翻做题记录但是没信号。 心态要跟去年Day1一样，不会就尽可能拿分，而不是只想着AK。 ### 8:25 令人紧张的题面 迅速解压，题目似乎不友善，而且题面都很长。 T1觉得可以按题意递归。一边写还一边其他做法，各种细节挂，几行写了整整15分钟。因为模拟赛挂过"ref"这一命名，每一个命名都很小心，递归函数名为getint，这本来用作快读，至少平时不会挂。 ### 8:45 复原栈 T2想深搜时维护对应的左括号，想了一会发现当前点新增匹配应该就是(1+对应左括号前面一个括号的新增匹配)，但是return一个点的时候怎么复原栈？又想了一会发现记录一下对应的top，return时加上即可。 由于代码能力为0，又写了很久。大样例突然RE，幸亏碰巧打对了开栈命令。 ### 9:30 浪 还剩差不多两个半小时。读T3。 一棵树内部最小的数字一定有方法走到最小的标号，应该贪心。 钦定people1（数字1）的路径，那么people2能走到哪些点？走点是n^2，问题不大，考虑边的限制是怎样的。 而我不去想本质。似乎people2能走的是一个H型，即最多一次people1的逆向边，禁止1的正向边。立刻开始尝试。 dfs参数一大堆时，突然发现people3与前两人的关系复杂。是每个人的逆向边只能走一次？自己举出反例。 迟钝地觉察到，走一条路径等于承认这些边在整个割法中顺序固定，嘲讽自己这么迟才转换问题。是否有优秀的做法存储边之间的顺序关系？ ### 10:30 起落 不断地喝水试图平静。由于此时感到一些希望，总算允许自己去上移动厕所。跑下来像个在花园中捉虫子的小孩，难道是所谓归来仍少年？ 拓扑图？暴力二维数组，used[i][j]表示i先于j？发现答案路径总长是O(n)（断一条边只会使路径总长+2），直接在dfs出路径以后暴力二维for循环，应该仍是n^2复杂度。慢吞吞地尝试实现，左邻桌的键盘声也激烈起来。 过了小样例的第一组数据，第二组发现错误，于是强行钦定被占用的点不能更新答案，才过了第二组数据。结果第三组，一条短链，永久出错。 ### 11:20 错过机会 发现走一条路径既承认这些边在全局顺序固定，又要求两边之间不能允许该点（两边中间那个点）的其他边插入（包括第一条边，等于第0条边和它之间不得有该点其他边，以及最后一条边）。 大事不妙，看看暴力，想最后20分钟再打。 这怎么维护？按照二维for循环一样的想法，应该有一个n^3的做法，而我的dfs似乎只能表示走过的边之间的顺序。 **屡次提出之前的一个偶然想法：是否只要维护相邻边之间的关系（结点之间独立）就能保证全局合法呢？** 应该是估计不可能，所以没有继续想下去。 我对自己的dfs表示绝望。 估计人均AK，那么10分、35分应该和0分没有区别，因此一再忽视暴力。 ### 11:45 恼人的播报 监考开始不断地提示时间、文件夹，确实很干扰。 ### 11:50 继续调试的决定 仍在平和地F7下一行，特意看了一下时间。 ### 11:55 试图暴力 链比排列的分数多。试图模拟，于是写了一个假的链贪心，链样例一直过不去。气得发声。 ### 12:01 劝停 删除tree.cpp，将tree2.cpp重命名为tree.cpp，打上文件。恨不得删除我的考生文件夹。 站起来时，心已平静许多。 安静地退役，我想。 询问发现A掉T3的人并不多。应该花next_permutation, swap, for的三分钟，珍惜那10分的。 **我的目标应该是超越自己。** ### 13:30 秋游 和同学去学校旁边的物美玩，以前还没去过呢。他们骑自行车，我跟着跑。天气晴朗得有点熟悉。一公里路，单纯的游，无忧无虑又蕴含未知。最后就悠闲地吃了顿饭。回程我饱了不想跑，望自行车的影子，苦笑再次承认： **形成友谊的最好时期是刚刚认识时。早已认识却没有形成友谊，很难再到一个圈子里。** 依然两三个人，松懈的机房。阳光与打双人小游戏的zck和xay。窗帘与寝室里打开黑大游戏的qwk和zby。 ### 22:20 修改的说说 也不想看原题。睡前刷刷动态，一条修改的说说让我始觉暖意。熄灯后跟下铺聊幼稚有趣的想象。 ## Day 2 谢幕之战 闹钟没响，醒来时几乎不敢看手表。 尽管仍遗憾昨天，却在车上看着风景。今日或是谢幕。 ### 8:25 浏览 T1估计是某种容斥，T2感觉经典题然而不会，数据范围4e7大的吓人，T3重心，想到点分写个重心都老是挂，拿个暴力就好。 ### 8:35 浪 T1每个点有值，画了一页纸以后还是只有一个基础的暴力dp。 和去年Day2T1一样，莫名其妙用掉极多时间。 **今天的结局已经定在这一页浓缩荒唐的草稿纸上，颇具谢幕的意味。** ### 9:30 犹豫 一边写暴力总是想哪里能去掉一维，浪费很多时间，一直无果。调试，手模第二个小样例，许久发现赋初值错了，只能随机一个上去，错了再随，就过了。再想想正解。 ### 10:30 暴露实力 没时间了，想T2。实力如此，想如果11:00还没有正解就打两道暴力。 单调队列？斜率优化？玄学规律？可是去哪里找O(n)的状态。 ### 11:00 试图暴力 之前陆续发现了排列暴力，背包暴力，n^3暴力。一开始想n^2还以为单调队列，突然发现while就可以。 T3时间更紧。先打了一个dfs siz。发现链比较直白，又打了一个加减法。 在三题之间穿梭。 ### 11:50 回望 满二叉树大概可以，本质不同的边只有log条，然后这些边的最大子树O(1)求。 感到来不及打了。查一查文件名、long long。算一算今天的分数，开始回望OI的路。 实力确实只值以上。也许还会无限fst。 **总在黑白之间那块灰色地带。** 得对自己的行为承担责任，因此依然平静，似乎OI的终点不再有遗憾。但我以后做什么？难道和之前的爱好一样，最终都不敢提起自己学过？ 我还一直构想一个团队，以为未来从事之。 敏感的话更适合在日记里写。即使意外一再发生，也要自信下去。回忆快乐的模拟赛时光，第一次遇见一种数据结构的精彩，感谢所有关心过弱小的人。今天太晚，日后还会来补游记，还会来修一修题解。 谢谢你们，一路如此美好难忘。