NOIP2018 Day1 游记
NOIP2018 OI好气啊，昨天晚上RP++没有发出去，我肯定是受到RP--的制裁了。
早上到的比较早，7：40到的，基础实验楼前面还没有什么人。过了几分钟llf就骑车来了，我立马就走过去%了他，随后zk也来了，他问我打算考多少分，我说大概150的样子吧。
之后和llf（其实不包括他）复习了一下exgcd啊inv1啊lca啊pow什么的背诵内容，但是今天都没有考。不久cyc也来了。他远远一看就是要ak的样子。一直到7：55cw的校车都没有来，结果zk说车牌登记错了被卡在门口了。过了一会就有一大群黑白绿相间的oier徒步走了过来，zml和xyc给我们发了准考证就进去了。
T1 Road
这道题相当显然啊，让我都怀疑我是不是在考普及组了。一分钟读题五分钟码字，直接过了大样例，大概估算了一下1e6*1e5不会爆int，就不管了。这道题我连对拍的暴力都想不出来。我看我旁边的妹子对着这道题的题面看了半个小时，唉。我感觉这个题应该没有什么坑。
T2 Money
这题看到什么求最少的个数以为是二分+贪心，仔细一看发现这样不好做，应该就是一道数学题。然后看到n<=100，估计是什么O(n^3)或者O(n^4)的东西，再加上半个小时前踩复习背诵了exgcd，所以我以为是数论规律题，怎么枚举一下公式什么的。之后随便找了几个数试了一下，发现m里面的数都是n里面肯定有的。最后确认了规律应该就是从n里面去掉能作为其他几个数的和的数，剩下的就是答案。于是我又在想枚举大法，先枚举一个数的倍数，两个数的倍数，三个数的倍数……似乎复杂度太高了。接下来我又想用数学公式去简化，又推了二十分钟，放弃。突然发现了这个过程好像筛法（其实早就应该看出来了），又注意到a[i]最大只有25000，就动手写了，花了五分钟研究哪里continue最快，最后秒过大样例，又造了几组随机大数据，都是秒过。算了一下复杂度大概是O(n*a)，应该能A（何况€€£还换了新电脑）。
考后听说背包也能做，不过没仔细想了。
T3 Track
啊啊啊前十分钟读错题意了，以为就是普通的树上K长路，心想今年NOIP怎么这么简单，结果有限制条件……
然后还剩一个半小时，对正解毫无感觉，连是什么算法框架都没想到。于是就只能做特殊情况了。m=1的情况简单淀粉质，20Pts到手。但是，菊花图的情况我写炸了！！！应该是排序然后首尾相加，但我写成了排序然后第M组相邻相加！！！好气啊！退化成链的情况并没有想出来。写了一个奇怪的二分贪心，反正没有过自己造的数据，不知能不能撞对一个点。二叉树的情况就更不会写了。
此时我发现身边不少人都在扫雷了。我检查了一下文件名什么的，没太大问题，还剩十分钟的样子。
感觉今年D1的题偏简单啊，一定有不少dalao要ak。反正我是不行的。明天RP++，不要再考数论了，最好来三道模拟。但是借用zml的话，水涨船高。
1 | while(1) |
本文采用 署名-相同方式共享 4.0 国际 许可协议，转载请注明出处。
