老实人的NOI2019AFO记-游记

在7.20日之前，我也不知道应该用什么形容词去形容。 - 2019.7.15 找到形容词了：老实人~~555555~~ - 2019.7.16 神tmDay1的数据这么水，就我这个*老实人*数组大小只开对应部分分的... ~~等NOI回来再补游记吧，先简单记记。~~ ## Day -1 来广东。极其闷热。中午简单凑活了一下。 和czy，zzh一个屋，据ztb说czy晚上打呼噜贼响，但实测不是。宿舍在C栋，所以信号更差了。之前把手机放在窗户旁边就可以了，现在得放到门外，看着特别蠢。 ~~辣鸡移动~~ 晚饭差评。为啥给了我一堆鸡爪？这并不会是我第一次吃鸡爪——因为我把它们都鸽掉了。伙食比WC差啊...THUWC>WC>NOI... 宿舍空调貌似还可以，就是我们屋一直忘了关门导致没啥用。睡觉之前怕着凉把空调关上了~~我蠢~~。D类选手的待遇比不交钱选手好一些？ 然后就是无聊的背笔试和看博客了。 ## Day 0 早晨的铃是6:20 开幕式连续放送出锅，获奖名单是录好的音，而且播的时候停不下来。导致音画极其不同步。 介绍来宾时dzd和wh收到的掌声明显多。 dzd又发表了一番演讲。竞赛~~收钱~~ 是正义的（ 这次还颁了“钻石教师”奖？ 然后是各省选手被当众消费。不过这次不点名了也不喊口号了（河北原计划口号：`京畿福地，燕赵儿女。信竞赛场，所向披靡。`~~在是了在是了~~） 背了好久的笔试，给duck.ac好评，可以离线~~被鄙视~~ 下午笔试的网页很古朴的样子。6,7分钟就写完了，但是第2遍检查出错了（c的后缀名我眼瞎选成cpp了）然后就很慌，检查了很多很多遍。 还好100了。 然后是练习赛，题目分别是：优秀的拆分、CTS2019随机立方体、I君的商店。~~全鸽了~~ CCF强烈暗示今年有交互？ 其实我觉得交互挺好的，因为提答太浪费时间了。 晚上在机房上自习，有网好评。但是BIOS没开VT-x，忙活了一阵没装成VMWare。 ## Day 1 今天早晨的铃是6:30，晚上看了一晚上空调，稍微有点冷。 ~~这次考试之前没有拉肚子~~ 早饭吃的好像挺多的？我觉得挺好的，考到13点也不饿（也可能是太专注了）。 考试惯例鸽了1min 开题，扫了一眼发现都是传统题。 开T1，嗯？“猫”？猫锟又出题了？（后来发现是上交zky假冒的，差评！~~草，zky真签上交了~~）。先自闭了一会，发现没啥思路，然后去想部分分，先看A=0的点，愣了一会发现取个前缀max就行了。接着看完全的部分，发现把前缀max换成单调队列凸包就行了，然后推了一些细节，快9点的时候开始写，9:10写完了，过了前两个，第3个显示“已放弃”——没想到`-ftrapv`查自然溢出真的帮到我了，是叉积爆int了。改了以后一发过大样例然后就扔了。后来听说大样例贼水，于是下午就特别担心细节写错（我甚至都没有再看一遍代码），所幸没挂。这时候是9:20左右 然后看T2T3，都有一些暴力分可打，我选择先刚T2。 首先转化题意为笛卡尔树，于是就有一个显然的$O(n^2V)$的做法~~此时如果我写记搜就能多拿10分~~。然后觉得太划水，看$l=1,r=10^9$应该是差值做，打表发现是n+1次多项式。于是现场推了一下拉格朗日差值，就当过了。 正解似乎是进一步的，对每个区间维护多项式，然后乘起来就行了。标称5k左右~~是我写不出来的~~ 然后开T3，其实T3分配的时间有点少了，离结束就剩不到一个半小时了。先胡了一个$O(n^4)$大暴力（这里我又实诚了，如果无脑莽是可以过150的点），然后感觉这个恰好的限制应该是用wqs二分做，但是一直没找到好的check方式，感觉写的是一种和贪心本质相同的东西，于是乱搞成功爆0了。~~可能是因为时间有点紧？~~没有往费用流去想，不然能得48分...（卡常） ------ T2讲题：展示分数分布时贼有意思。爆多>巨多？0分（的情况）就不要鼓掌了。 ------ 下午鸽掉了活力嘉年华（其实是想去的，但是查完分之后还要等40+min，就鸽了）然后就去机房摸了。 换了台电脑进BIOS开VT-x，然后学习了一下smb协议在两台电脑之间传了下文件。装VMWare千万不要选“简易安装”，怕是自动帮你下载各种软件，等了1个小时结果进不去系统~~垃圾VMWare~~，然后手动安装了一次就OK了。~~日为啥这学校网速看脸啊，zrq下*就12M/s，我下chromium就20k/s？？？~~ ------ 看群的时候忍不住吐槽，这数据怎么tm这么水！！！ T1：SPFA+剪枝$n=10^5,m=10^8$可过？？？好吧这道题我做出来了就不说什么了。阶乘级暴力可拿85？ T2：“状态量不多”，拿记搜写区间DP能比for循环多拿10分... T3：这是最**的了，神tm$O(n^4)$暴力DP能过150...我太实诚了就开了n=50的数组，把数组开大，卡卡空间和常熟就能过40.什么水数据！ **关于SPFA：它活了**。T1SPFA可过（数据水），T3SPFA（费用流）可得48分 ------ 讲题的时候十分震惊，开$10^6$个空`deque`，理论空间`<100M`，实际空间`1G`！！！某位选手被这个卡了，好惨。~~这再次印证了我之前说的：deque是最垃圾的STL~~ 听完讲题才意识到自己有多菜。真自闭了。 怕是T2能用wqs二分拿60+，但是我当时wqs二分的方向好像不对，所以一直过不了样例。当时也是太紧张了。 怕是T3裸的费用流建图能拿40~48分...但是我一看题以为是数据结构/贪心DP方面的，没往费用流想。 怕是凉了。水平不足。今天200+的41人，150+的200人...Day2只能保银了...算了一下，就算加上T2T3能多得的22分，也是50开外了...更何况我觉得T2我不一定能想到记搜会比for循环快很多。**但是T3数据tm这么水我就不能忍了！** 算了算了，没啥实质的影响。技不如人，甘拜下风，想不出更高级的做法，怎么做都是在挤分数。Day1没挂分就好，已经没啥遗憾了。 ------ zhoutb2333不幸MLE了...在代码中开了$2\times310^3\times 2$的LL数组，1G空间成功Boom. Miracle不幸CE了...原因是结束前最后一刻才把代码放到文件夹下，结果手抖打了个`','`，然后也没编译...（这个事似乎还被王宏在会上说了...） 真的太恐怖了...没想到这些错误居然在我的同学身上发生了...**如果你是看到这边博客的学弟学妹们，一定一定一定一定要谨防MLE，CE的错误！！！**这不是玩笑！ ------ 好像对面中学考的分都很相近？ 外省人均比我高.jpg 毒奶Day2考字符串~~失败了~~ ## Day 1.5 去参观博物馆...在广州千万不要在室外待着...待2min就浑身出汗... ~~感觉广州博物馆和科技馆差不多，看起来很大，其实很空~~ 上面那句话是假的，最后rush一波还是没有看完。拍了挺多照片的。 最开始很有耐心的看，对每个展品会想象当时的场景，后来发现展馆里都是差不多一样的东西就嫌烦了。哦还有一些恐龙化石和海洋生物啥的，interesting。 回来之后贼累...ztb和czy在我屋里，我就去ztb的屋睡觉了。~~躺到3点才起~~ 草，ywy在楼下见到猫锟了...`Day2.problem().count()--`。毒奶猫锟出交互。 ri，想到昨天T3没开大数组莽过150好亏啊...起码亏了30名？ 睡前向卓裕毒奶：“你看序列交互出过，树交互出过，是不是该出图交互了”。 ## Day 2 ~~Today is the Last Day I Touch the Computer? - 19.7.17~~ 到现场看纸质题面 跳跃——嗯好 斗主地——草 I君的探险——草 为啥Day2只有1道题啊... 开题，T1貌似是个kdt送分题。T2...原来不是爆搜啊，虚惊一场；T3...草真的是图交互。 先推T2，推了推发现暴力分可以组合数算出来。拆了拆式子发现是网格图路径带权统计，以为自己能推出来，结果太天真了。 开T3，大概还有2h。先把最前边$O(n)$的暴力写了。然后A是sb整体二分，推了推细节开始码码码...然后一直在调一直在调，始终过不了拍。到考试最后瞎改了一番不知道能不能过。 ------ 下午查分，T3果然整体二分写挂了...然后A的做法似乎是随机分治？被踩智商了5555 cao，我T2fst了10分，而且挂的是最小的点...调了一会发现是数据分治写挂了：这道题有两个部分分，我跑完第一个后忘记`exit(0)`了，而最小的点$m=1$恰好满足这两个条件，然后第二遍读不进数就TLE了... ------ orz山西gsh全国rk57，他稳了sto。 然后下午十分焦急的等前100线，因为fst了10分，day1又因为**水数据亏了12分所以很慌，感觉自己要是进去也是卡在前100线边缘。 下午CCF极其鸽，到5点才出分，得知前100线427我428高兴的...真的无法想象，直接就跳起来了。悬着的心也放下来了，唉，谁叫自己挂分了呢。 所以这次NOI成功挂掉$12+10=22$分...唉之前的比赛从来没有挂过分，这次都还给老天爷了。虽然加上这些分，也拿不了金牌，但还是有些...不爽嘛... 算了算，今年NOI似乎打满暴力是进不了队的，必须在某一道计数题上获得高分才行；这也几乎是Au的充要条件...听他们银牌50多名的讨论，似乎都是挂在计数题上了，做出来就进队了... 所以今年河北集体被踩的很惨，怕是最高分衡中yxy450，离队线有很大差距。从高一开始学，现在真的很困难了。 怕是二中集体上演卡线奇迹。我和zrq,czy卡前100线，zky和zzh卡银牌线。 ------ 然后就是紧张的签约环节了。在出分之前清北只签集训队（似乎今年北大只签集训队和PKU营一等奖），其他学校都开始签了。zky，zzh，zrq，czy都签了上交，zyz签了北邮。ywy签了...人大？what他考得那么好为啥去人大？~~怕是还不如北邮...(纯属玩笑，我对两校实力并未了解)~~而且人大4h之后告诉ywy没过面试，~~好坑啊，~~然后ywy又去签了上交？？？这波操作看不懂啊为啥不先去上交...反正除了我都有学上就是了。 *hide* *\\hide* 然后早晨我和czy，zrq去领了奖。 ~~替czy，zrq感到高兴又尴尬，为自己感到庆幸~~ ------ 下午闭幕式接着放送事故。dzd讲话时突然鸣锣... dzd：“饭还是要吃的”~~公然恰饭~~ 主持人： 填江中学？镇江中学？ 余桃中学？余姚中学？ ------ 最后说个有意思的事情：早餐的粥的盛饭方式 第一天：把勺靠在锅里自己盛。有选手把勺沉入了锅中... 第二天：在旁边放了一个盆用来放勺。很多人盛饭撒了，而且粥非常烫。 第三天：预先把粥盛到碗里23333333333 ------ 一 波 三 折，有 惊 无 险。 NOI2019，AFO. 但是OI并不会离我而去 ------ 最后估值排名27，通过1.3K（仅洛谷）