洛谷秋令营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 的暴力没得分，也是浪费了时间。

赛后补题

T2

选的点 $b$ 是深度单调不降的，第一个点是 $b_1$，则 $d_{b_1} \le d_{b_i}$ 是成立的。

对于每个 $b_i$，这棵断开的子树里面都必须有 $d_{b_1}$ 这个深度的点，而 $d_{b_i}$ 是最浅的点了，所以选的 $b_i$ 其实必须在同一层才行。

如果只能选两个点，那么我们可以选择枚举 $b_1$，则 $b_2$ 就是它的某个深度一样的兄弟，另外还有一个以 $1$ 为根的子树，$1$ 应该也得包含 $d_{b_1}$ 这个深度，所以要求 $b_1$ 这一层至少要有 $3$ 个点，所以题目才给了 $n$ 叉树这样一种特殊情况。

假设 $b_1$ 所代表的那棵子树的深度范围是 $[l, r]$，则现在要求 $1$ 树和 $b_2$ 树的交的深度也恰好是 $[l, r]$。

那么要求 $1$ 树和 $1$ 树除去 $b_1$ 和 $b_2$ 之后，剩下的部分至少深度 $\ge r$。

此外，要求 $b_2$ 树的深度 $\ge r$。

并且，要么 $1$ 树深度最深恰好是 $r$，要么 $b_2$ 树深度最深恰好是 $r$。

这意味着什么，意味着对于深度 $depth$，我们要选的 $b_1$，这个子树的深度和 $1$ 树和 $b_2$ 树相比是更浅的。并且，$1$ 树和 $b_2$ 树至少有一个和 $b_1$ 树一样浅，否则求交最后交出来的集合会太大。

综上，$k = 2$ 的情况下，可以这样去做：

• 预处理每个子树的最深的结点的深度
• 枚举 $b_1$，假设 $b_1$ 这棵树最深的深度为 $maxd[b_1]$，$b_1$ 自己的深度是 $d[b_1]$
• 下面看到底是 $b_2$ 树还是 $1$ 树的最深深度是 $maxd[b_1]$。
  • 如果是 $b_2$，则需要看同层有多少个恰好深度是 $maxd[b_1]$ 的点，任选一个即可。此外，还要保证 $1$ 树的深度应该 $\ge maxd[b_1]$，为满足这个条件，需要这一层里原本就存在至少 $3$ 个最深深度 $\ge maxd[b_1]$ 的子树。 并且至少有两个是恰好等于 $maxd[b_1]$ 的。
  • 如果是 $1$ 树，由于 $1$ 树的最深深度是除去 $b_1$ 和 $b_2$ 之外的最深的，这个东西要恰好 $= maxd[b_1]$，并且 $b_2$ 的最深深度要 $\ge maxd[b_1]$，这要求这一层至少有 $3$ 个点的深度 $\ge maxd[b_1]$，其中一个是 $b_1$，一个是 $b_2$，剩下的归 $1$ 树，且至多有 $1$ 个点的深度 $> maxd[b_1]$，出现在 $b_2$ 上，否则 $1$ 树的深度会太大。
  • 我们还需要去掉 $1$ 树和 $b_2$ 树同时最深为 $maxd[b_1]$ 的情况。当且仅当 $d[b_1]$ 这一层的子树的最大深度恰好就是 $maxd[b_1]$ ，且至少有 $3$ 个子树是这样时，才需要去掉。

下面考虑 $k$ 个的情况怎么做：

• 仍然是枚举 $b_1$，其自己的深度是 $d[b_1]$，这个子树的最大深度是 $maxd[b_1]$。
• 下面看到底是 $b_i$ 树还是 $1$ 树的最深深度恰好是 $maxd[b_1]$。我们不妨设这一层中，最大深度等于 $maxd[b_1]$ 的点有 $x$ 个，严格大于 $maxd[b_1]$ 的点有 $y$ 个。
  • 如果是 $1$ 树恰好是 $maxd[b_1]$，其他的 $b_i$ 全都严格大于，则首先要求 $x + y \ge k + 1$，进一步，$x \ge 2$ 才行，否则没法恰好交出来，再进一步，$k - 1 \ge y$，否则 $1$ 树的深度必然严格大于目标。满足这几个条件之后，对于 $b_i$，我们相当于从 $y$ 个严格大于的里面选 $k - 1$ 个，这要求 $y \ge k - 1$，所以应该满足 $y = k - 1$ 才行，所以方案数应该恰好是 $(k - 1)!$。
  • 如果是某个 $b_i$ 的最大深度为 $maxd[b_1]$，且 $1$ 只要大于等于就好，则首先也是要求 $x + y \ge k + 1$ 且 $x \ge 2$。计数时，我们先统计所有 $b_i$ 都严格大于的情况，再用所有的情况减去，就是存在某些 $b_i$ 恰好等于的情况，并且这个时候一定也有 1 的大于等于。这个方案数是 $A(x + y - 1, k - 1) - A(y, k - 1)$。
  • 以上两个分类已经涵盖了所有情况，并且没有重复计数。

这确实是标准的蓝色难度（提高+/省选-）的题目，如果场上给我充足的时间的话，$k = 2$ 的情况我一定能得分，一般的情况可能要折腾折腾，因为我确实最开始分类时没分好，导致还得去重，就比较麻烦，后来才发现一种可以直接不重复的计数的分类方案。

T3

这也是一道蓝题，虽然场上可能切不掉，但是我还是要场下补掉的，明年比赛一定要到场切的水平的。

首先，应该识别出来这是一道数据结构题，因为这基本上就是在对某个东西做修改和查询。

啥时候 $x$ 到 $y$ 完全没车了？似乎只要没操作过区间 $[1, n]$，就总有车可以载到。

如何求 $x$ 到 $y$ 最便宜的？首先如果之前不存在操作的区间 $[l, r]$，使得 $l \le x \le y \le r$，则有恰好从 $x$ 出发，并且恰好走到 $y$ 的。

最暴力的求法是枚举左端点 $l$，再枚举右端点 $r$，看 $[l, r]$ 的车有没有关停，没有的话就更新一下答案，这样总的复杂度是 $O(n^2m)$。

考虑优化，我们枚举 $l$，然后看不小于 $y$ 的最小的 $r$ 是多少。这需要我们考察之前所有操作左端点 $\le l$ 的操作，看这些操作里最大的右端点是啥，假设是 $rmax$，则我们就可以坐 $[l, \max(rmax+ 1, y)]$ 的车。

这似乎需要一个树状数组去维护前缀 $\max$。这样的话总复杂度就是 $O(nm\log n)$，$n = 3000$ 随便做了。

场上应该至少能拿这 28 分才对。

要准确理解性质的数学语言！

考虑特殊性质分，A 性质相当于静态查询。

B 性质意思是每次操作的区间和之前的都没有交集。

C 性质意思是操作的区间前一个一定是后一个的子集，所以每次查询时只需要考虑上一次的操作是啥即可，又拿 8 分。

D 性质不知道有啥用。

E 性质意义不大

复盘

本场比赛，我预期得分 100 + 8 + 12 + [0, 8]，实际得分 100 + 8 + 12 + 0 = 120 分。赛后补题时，我发现以我的能力，应该能打出 100 + 28 + 36 + 0 = 164 分的水平才对。之所以没打出来，是因为赛时有很多环节浪费了时间，并且对题目条件和性质的分析也不够，导致本来该做出来的题目没有做出来。