Noip2018

# Day-2~Day0 考前抱佛脚，赶紧刷刷各种模板 # Day 1 在开考之前打好了拍子模板，然后试题密码就发下来了（这是我前面的神仙打了$100$多行$emacs$的配置$QAQ$）。 先按照惯例，看完了$3$道题，发现都不会做，于是我就猜$T1$是道结论题，但是想了$10$分钟没什么思路，就开始看$T2$。 重新看了$T2$以后发现似乎可用完全背包做，然后就$naive$的认为今年$T1T2$交换了。 把$T2$写完后就重新看$T1$，发现似乎是一道线段树，我就想：如果$T1T2$交换的话，$T1$考线段树也就不算太恶心吧，然后就开始打线段树 写完后时候大约还有两个小时，开始肝$T3$。 感觉似乎可做，一眼二分+树形$DP$。但又想没那么简单，就开始想其它思路。 然后就往带权并查集这块想，想了很久发现可做，分析了一波样例，放弃。 然后又想一个堆来维护所有边，发现不好标记用过的边，放弃。 一个小时后，没一点思路，期间各种胡思乱想，时间就过得飞快 这是开始肝部分分，发现$m=1$跑$n$边$Dij$就行了，写完后一时脑抽，认为是最长路，改成$SPFA$，改完后又发现不对，但是懒得改了，就用的$SPFA$。 还有菊花图的情况，这似乎可做，拍一遍序二分贪心找最接近的行了，但是没时间了，就放弃了。 考完后听别人说才知道T3的特殊数据：分支不超过3是二叉树的意思，不然可能还有55分的QAQ $Day1$估分：$100+100+15=215$ 洛古数据：$100+100+20=220$ # Day2 签到的时候发现旁边的旁边竟然是罗凯，赶紧%了一波。 还是先看三道题，还是发现一道都不会做，只是想吐槽考了两道字典序问题。 然后静下心来开始肝$T1$，发现前面的$m=n-1$的情况很好做，就开始写。 大概$20min$就写完了，又发现$T1 n=m$且是一个环的情况也好做，就打了两个$namespace$去肝$T2$了。 $T2$一眼状压，发现复杂度不对，然后就像数论或者结论题，想写暴力，发现暴力都不会写，于是就跳过写$T3$ $T3$的问法和国旗计划比较像，但是拓展到了树上，感觉树形$DP$，想了一会就发现是没有上司的舞会改一下就行了，于是就开始肝$T3$的$nm$暴力。 $10$分钟码完，调了$30$分钟左右（标记的时候出了一个问题，看了好久才发现） 当时大概是过了一个半小时左右，还有两个小时，但发现其他的题目没任何思路，就开始准备打$T1$后面部分分的暴力。 结果发现和前面貌似没什么区别，仍然先贪心，遇到环就特判一下就行了，于是我就想判环的方法。 只会$N^2 DFS$，显然过不去，突然想到$Tarjan$，于是就缩点之后判断唯一的环，打个标记之后就可以做了。 感觉细节很多，删删改改老师就说只有半个小时了（~~时间都去哪了~~）。 于是准备放弃$T1$开始看$T2T3$，发现没仍然一点思路，就继续看$T1$，然后又删删改改突然一发过了第三个样例！！！ 测第四个样例，前面$10$个貌似是对的，后面乱七八糟$QAQ$ 问下老师还有多长时间，老师回答：$15min$左右 凉了，$AFO$了。 ~~期间输出了一波T2样例，但是太仓促了多打了一个引号，就编译失败了QAQ~~ 突然发现了一个地方犯了一个很明显的错误，于是就马上改掉，在测大样例，发现前面$50$项都是对的，但是后面全是$0$。 老师说：时间到，大家赶紧离开吧。 然后我就过了第四个样例了QAQ $Day2$估分：$100+0+44=144$ 洛古数据：$92+0+44=136$ # Day2.5 特别虚$T1$，总感觉要出锅，但是被父母叫去补文化去了，晚上九点才回来，一测$T1$，有$92$分？！感觉人生终于有了希望。 总共估分：$100+100+15+100+0+44=359$ 洛古数据：$100+100+20+92+0+44=356$ 官方数据：$100+100+15+96+0+44=355$ 我还是太菜了，反正写的分基本都拿到了，也算是一个进步吧。 要是Day2后面的两个小时肝T2去找规律就好了（虽然也不一定找得出），~~说不定还能混个WC~~。Day1T3没去多打一些部分分，Day2T2的炸零，也算是一些遗憾吧，希望明年继续加油，创造佳绩。