NOI 2018 网络同步赛酱油记

Day 0

上午wuvin神犇给我们上课， 讲了后缀三姐妹，后缀仙人掌，etc…感觉整个人都不好了， 在掉线的边缘徘徊…

下午考试（同步赛前一天还考试）， 板题大赛， 前两道轻松切掉， 最后一道一眼SAM$SAM$，暴力20分之后弃疗。自称字符串完全不会的linners倒是AK了…

到楼下看推荐SAM$SAM$博文， 看了一个小时仍然头大， 然后请Rockdu$Rockdu$ Dark ♂Lao 讲了一下， 还是没有搞懂…

晚上做了一道回文自动机的板题， 感觉自己好菜啊QAQ

Day 1

上午8点15到教室， 打好配置8点25， 登邮箱上了在线赛网站（怎么比文老网站还丑…）。

8点半到了， 点击登录， 果然不出所料卡住了。 最后还是wuvin搞到了试题包发在QQ群上。

开题：

T1: 想了一会，发现离线的情况只需要先最短路一遍， 再把询问按水位排序，然后倒序插入边， DSU维护连通性、最优解即可。 在线的情况不会， 只会O(NM)$O(NM)$…

T2：这冒泡排序是WA$WA$的吧… 想了一会毫无思路， 只会O(N!×N2)$O(N!\times N^2)$的…

T3: 心里一句mmp$mmp$， 怎么昨天讲了SAM$SAM$今天就考了？？！！ 而且裸SAM$SAM$有68pts$68pts$？？！！* ….

然后开始码T1， 大概过了2个小时把两个暴力调好了， 测样例， 发现最后一个点一组数据跑了2.6s$2.6s$， 这才发现似乎出题人在暗示卡SPFA$SPFA$， 于是现场脑补了Dijkstra$Dijkstra$出来…（平时都是SPFA$SPFA$）。 自己觉得自己稳的一逼， 大概有75分了。 然后发现如果写个树剖还有5分， 但是懒得写了…

开始next$next$_permutation$permutation$给T2打表， 然后发现不考虑字典序似乎打出来是卡特兰数？？ 这玩意我只会O(N2)$O(N^2)$筛啊， 似乎Rockdu$Rockdu$讲过？？ 想了半天还是不会， 只好特判了不管字典序的情况和阶乘复杂度的枚举…

最后一道题直接弃疗…谁叫我字符串菜如狗啊…码了一个缓慢的O(N2)$O(N^2)$哈希， 暗想应该不会炸内存， 就把vector$vector$开大了些。

考试结束， 期望得分75+16+10$75+16+10$， 感觉Day1$Day1$过百没有问题…

回来的时候wuvin说他拿到数据了， 叫我们在网站上测一下…

自信提交T1$T1$， 发现只有5pts$5pts$？喵喵喵？？？

仔细检查才发现， 良心出题人给的样例都只有1组数据， 然后我head$head$数组和分配边下标的cnt$cnt$没有清零…

那5分还是没有边， 只有1个点的情况的…

提交T2， 发现只有8分？？ 我的特判WA$WA$了？？

提交T3，发现这个缓慢而不正确的哈希一分都没有…

Day1=5+8+0$Day1=5+8+0$，完美起飞…

%%%100+0+0$100+0+0$的watson, 100+8+4$100+8+4$的lvmaomao,75+8+28$75+8+28$的Rockdu， 以及差一个cnt=0$cnt=0$ T3就有68分的linners

%%%初三的小朋友xyz32768， Day1 135+….

Day 1.5

wuvin 又上了一天课，讲了图论相关（割点， 虚树， 点分治， 圆方树， 支配树……），而且还意味深长地说了一句：“前天刚讲SAM$SAM$就考了， 明天会不会再考什么？”

这一天的内容还是比较简单， 刷了几道水题。听wuvin说Cu$Cu$线在120分一下， 感觉还有梦想。

Day 2

仍然早早来到机房， 打配置。

今天€€£似乎良心一点了，网站没那么卡， 很快拿到题。

T1：CRT?? 我似乎不会啊（真的是太菜了）… 只会只有一条龙的情况和回血值为1的情况， 不过已经有60pts$60pts$了。

T2：这是个啥玩意？？我似乎只会O(N2QT)$O(N^{2}QT)$的啊…15pts$15pts$ gets。又想了一会，貌似一条链的情况可以O(Nlog(N)QT)$O(Nlog(N)QT)$搞啊？？似乎可以多苟5∼10$5\sim 10$分…

T3：说好的算几去哪了…一道只有题目和算几有关的题QWQ…哈密尔顿回路有啥性质？不管反正我会大力DFS…

T1码好的时候已经过了两个半小时， 测了大样例一点没问题（当然是60pts$60pts$的部分分）， 看了一下样例感觉还是挺良心的。

T2疯狂暴力， 链上的情况单独一个暴力， 跟$O(N^2QT)的拍了感觉没什么大问题。

T3大暴力疯狂WA$WA$， 第二个样例死活比答案大，这玩意还可以WA$WA$？反正知道考试结束都没有调出来…不知道是不是边连到了一些妙妙的地方。

考完之后并没有马上对答案， 第二天才在洛谷上面交了一下。

T1疯狂RE，直接爆0， 发现是multiset$multiset$的end()$end()$没有特判， *那几个大样例怎么就没RE…

T2数据包太大了测不了， 我也不敢去loj$loj$上面测了…

T3理所当然爆0。

大家T1基本上都有30∼70pts$30\sim 70pts$不等…

%%%Ag$Ag$稳的一逼的linners

%%%Ag$Ag$更稳的xzy32768

后记

感觉自己真的是太菜了啊qwq， 正解写不来， 暴力还打WA$WA$。

继续这样子怕不是省一退役系列…

数学和字符串方面的确是我的弱项， 需要立即抓起来。

考试习惯也有待改进，多组数据都没有复制一下强行造成多组的…

不过话说回来NOI$NOI$还是比想象中友善一些…