洛谷秋令营Day8-模拟赛

比赛实况

• 早晨 5 点 50 就醒了，且由于上午临时有别的安排，以至于下午 2 点 45 分才开始参加模拟赛，迟到了 15 分钟，但问题不大。
• 由于没有睡觉，感觉精神状态一般，于是还是先不写代码，先把 4 道题目看一遍。
• T1 有很好写的 $O(n^3)$ 暴力，正解差不多也看出来了，只需要枚举区间左端点，然后右端点强制是 $n$ 就好了。T2 的 8 分暴力不算难写，只要暴力枚举选哪些点，然后再把这些点的子树深度分别求出来，求交即可。T3 我们发现如果倒序考虑所有询问，那么就是增加路线而不是删除路线，直观来想这样应该会好做很多，每次加完边暴力求最短路就好了，12 分暴力应该是容易的。T4 题意有点复杂，等会儿写完已知的这些分再看吧。此时大概是 3 点 5 分。
• 开始写 T1，暴力光速写完，然后写正解，但是脑子有点不清楚，上来写了个树状数组，后来发现完全是没必要的，直接使用 map 就好了，这浪费了几分钟时间。然后写了个对拍，15：25 分对拍完毕，应该是没有问题。最后检查了一下数组大小、溢出等小数据拍不出来的问题，就不管 T1 了。
• 15：28 分开始写 T2，写的时候发现这个暴力并不是特别好写，直到 16：00 我才把暴力写好并测好，预期拿到 8 分。
• 然后我考虑了一下 k = 2 的特殊性质，发现可以枚举两个点。假如两个点无父子关系，则可以分别用 dfs 序求出深度范围，然后再求出 1 的深度范围；如果有父子关系，则稍微复杂一点，但也还好，本质上也是在 dfs 序上查区间 max 和 min，但因为枚举了两个点，所以最快也是 $O(n^2 \log n)$，但这个代码一点也不好写，这样只能多得 4 分，太不划算了，需要想一个复杂度更低的解决 k = 2 的做法，最好能拿 20 分。想了一会儿，没想出来。
• 去写 T3 的暴力，写代码前首先发现题目读错了，本题不允许换乘，只有直达的车一次到达才行，这样反而简单了。我们用矩阵暴力维护目前能走的路，然后每次询问暴力枚举得到最小代价的路就好了。这样写好之后测了一下，有问题，发现由于一条路可能是被多次删除的，所以倒着的话，需要遍历到第一次删除的时候才能把这条路加回来，改了之后好像就对了。然后惊奇的发现，完全不用倒着做，直接正着写这个暴力就好了，于是重写了一遍正着的暴力，好写又不容易错，得了 12 分。到现在已经 16 点 45 了。
• 去看 T4，大概算了一下复杂度，感觉最暴力的暴力不一定能得分，但还是莽了一下去写了。写的时候也真不好写啊，到了 5 点半才把这个最多得 8 分的暴力做了，测了测 debug 之后好像对了，这个时候已经 5 点 40 多了。
• 后边的时间很尴尬， 时间好像不足以我做任何其他分数了，于是检查了一下 6 点 10 分之后就提交了。预期的分 100 + 8 + 12 + （0-8），感觉打得很烂。
• 出分了，100 + 8 + 12 + 0，最后一题果然暴力也全部 TLE 了，没能拿到任何分数。
• 本场比赛有很多失误，一个是读错题浪费了时间，然后因为没有完全想清楚做法就写代码，导致写了一些没用的代码，也浪费了时间，最后写 T4 的暴力没得分，也是浪费了时间。