HEOI 2019 游记 - Noble

真的是**游记** ------------ ### Day -2 边颓边等放假，然后觉得太颓了，替罪羊树敲了下列队。 然后全是锅，回宿舍之前调出50pts. ### Day -1 出发去火车站，大巴非常非常热，喜提晕车（我吃晕车药了呀！）。 ~~后排一个老哥晕车手机掉在车上了。~~ 隔着过道，两个神仙正在讨论题。晕的不行完全不知道在说啥。 高架堵车，大巴车一冲一冲的挪，差点吐在车上。 ~~火车站吃麦当劳花了90块。~~ 火车上：睡觉真爽。 下火车去燕大路上学长提到出题在parent树搞事，成功奶中（虽然不是在奶考点）。 下午到燕大宾馆，掏出电脑准备打游戏，发现没带电源。也没有手机。 瞬间心态爆炸。 晚上吃黄焖鸡米饭，为选科和大学的事发愁~~（但是黄焖鸡真香）~~。 ### Day 0 去劝业场在一个小店里花55买了个电源。 路上手机看了qq群里发的省选模拟题，想了一个t2的二分答案nlog^2n做法，~~反正没电脑也敲不了。~~ ~~后来知道这好像是是D1T1做法之一来着？~~ 然后和我妈逛商场，买了不少吃的。又在商场吃了饭（砂锅排骨味道算是不错）。还买了好利来回旅馆吃。 下午打游戏+手机看B站。 试机敲了替罪羊，出锅。 ~~找了好久的锅~~，然后和vector对拍，拍了好久之后溜了（yy了.cmd对拍，要一直盯着）。 晚上把列队调过去了。 ~~要吸氧+洗脸才能过。~~可能把平衡树从2棵改成n+1棵会好一些的说。 11点睡觉，燕大宾馆的枕头真的不舒服。 不过本质燕大招待所。 ### Day 1 枕头非常不舒服，脖子很难受，没睡好，头昏昏沉沉的。（难受到现在，可能是扭到了？） 在燕大食堂吃早饭，味道海星。 然后进考场，等考试开始的时间灰常无聊，险些睡着。 压缩包密码zongzizizizzzz？黑人问号脸。 先看t1，又是一个问全部(l,r)怎么怎么样的问题。 t2字符串，显然后缀数组，溜了。 t3啥神仙传统题？数论大杂烩？gcd还没背过呢，溜。 60分暴力白送啊。~~（机房就一个暴力敲对的，还有一个神仙trie树正解敲炸）~~ 开始看，求异或最大，这不明显01trie吗。 要求所有区间，那可以可持久化一下，然后根据每个右端点搞出最大异或。 问题是还需要求次大，然后不到2分钟想了一个记录贪心路径再回溯的玄学做法~~我trie树深度还开成64的了，还好内存给的够大~~ 去年敲的唯一一个01trie，~~（总共只敲过两次trie）~~，然后11点敲完+改完锅。 大样例一直少6万左右，调到12：25，完全自闭。 出考场5分钟事后诸葛亮，和我妈聊天时想起来叶子结点要维护计数器。 ~~幸好考场上没维护，不然mle 80变60.~~ 出分t1拿了80，海星。如果11点之后换t3其实还能多拿几分。 中午黄焖鸡米饭。 下午继续打游戏，beamng+cod4联机，但是网不好cod打的并不爽（全是毛子服延迟太大...） 晚上黄焖鸡米饭+好利来蛋糕。 11点睡觉。 ### Day 2 脖子依旧不舒服，枕头是真的难受。 早上燕大食堂，吃的海星。 在楼下玩了会手机，快50时带着一堆吃的进考场，边吃香蕉边等开考。 压缩包密码非常混乱，完全记不住。 t1带一堆限制推方案数，方案数不会推，溜了。 t2看着比较可做来着，搞t2. 题面意思就是把子节点连有向边到父节点，两节点不可达就可以合并。 像独立集来着？布星啊这不会啊。 思考dp，布星。 思考网络流部分分，布星。 那就从一条链下手，在草稿纸上画了个序列，~~然后忘记题面开始研究独立集。~~ 链也搞不出来，甚至不懂为啥1不是端点。。。~~爆零~~ 滚回树上，突然发现一条链上的点全都不能合并。 所以以1为端点的链其实就求个和呗！~~所以说链有时候也不要随便横过来当序列看。~~ 那就可以求子问题了，两个能合并的点显然合并更优。 A<-B,和C merge，显然AC<-B不劣。 直接dfs之后往上合并就完了。 布星啊，复杂度不对啊，priority_queue这样显然上界n^2logn 但是序列可以全程维护有序，所以不用优先队列，直接vector也能搞。 n^2也布星啊？！ 然后完全没想起来启发式合并.~~也不会证启发式合并复杂度~~ 写了个生成器，现场yy出了对拍，拿vector和优先队列拍。 ~~随机数据跑飞快，就连优先队列都不超时，还没吸氧。~~ ~~vector比优先队列快一倍。~~ 然后祈祷数据随机就溜了。 剩下时间敲了十分的t1. 推了下t3，感觉不可做，~~（猜对了）~~，趴下开始睡觉。 中午黄焖鸡米饭。 下午坐火车回石家庄，火车站买了份德克士。 火车上继续睡觉。 晚上坐公交回学校，箱子砸脚，砸在了嵌甲上，疼死。 在学校搞了搞选科的事，然后回宿舍睡觉。 ~~我的月假呢？就这样就完了？~~ #### Day3 day2拿了70，省选裸分四十二三名，算上noip47，海星。 改d2t2代码，改了十分钟洛谷就Ac，难受。 yy了一下启发式合并的复杂度证明，貌似稍微明白了一点。 晚上改d1t1，发现加计数器mle，庆幸考场没想起来。 不想换思路，最后把计数器搞进了叶子结点的左儿子指针里，io流换成scanf就A了。 ### Day n（19/4/10） 4月新番：RE:从零开始的不想学文化课的生活。 ~~然而还是要学的，小门小户，日子终究要过，哪有钱加里敦大学。~~