赛后 VP Div.1，感觉还行。

A

一个挺容易想的 DP，维护每中数字的位置，多了就删前面的。

B

交互题。

按照一贯思路，先考虑极端情况。把机器人移动到右上角，即往右移动 \(2e9\)，再往上移动 \(2e9\)。

此时绝对值可以去掉，设距离为 \(dis\)，即：

\[ dis = x+2e9+y+2e9 - \max\{x_i+y_i\} \]

再把机器人移动到右下角：

\[ dis = x+2e9-(y-2e9)+\min\{y_i-x_i\} \]

C

赛时挺快想到思路，但没调出来。

树一定可以随便涂色。

考虑奇环，一定只能全为 \(0\)，偶环上所有数一定要一样。

因此先把所有奇环找出来，填数，再跑边双连通分量，填偶环上的数。

最后的 \(-1\) 一定有 \(V\) 种填法。

D1

还是交互。

一样考虑极端情况，先问 \(10^5\) 个 \(1\)。

设答案为 \(l_1\)，容易发现此时能求出 \(W\) 的范围：

\[ W\in \left[\left \lceil \dfrac{10^5}{l_1}\right \rceil,\left \lceil \dfrac{10^5}{l_1-1}\right \rceil-1\right] \]

证明

因为 \(l_1 = \left \lceil \dfrac{10^5}{W}\right \rceil\)，所以 \(l_1-1 < \dfrac{10^5}{W} \le l_1\)。

推得：\(W(l_1-1)<10^5\le Wl_1\)，两边分别变形即可。

我们记 \(W\in[L,R]\)，可以证明 \(2L > R\)。

证明

首先肯定有 \(\left \lceil \dfrac{W}{L} \right \rceil = \left \lceil \dfrac{R}{L} \right \rceil\)。

假设 \(2L=R\) 时，\(\left \lceil \dfrac{W}{2L} \right \rceil = \left \lceil \dfrac{\frac{W}{2}}{L} \right \rceil = \left \lceil \dfrac{\left \lceil\frac{W}{2} \right \rceil}{L} \right \rceil \neq \left \lceil \dfrac{W}{L} \right \rceil\)，不成立。

因此 \(2L > R\)。

考虑神奇构造：\(\{L,\ 1,\ L,\ 2,\ L,\ 3,\ \cdots,\ L,\ R-L\}\)。

序列每组形如 \((L,i)\)，若 \(W\in[L,L+i-1]\)，则造成 \(2\) 的贡献，否则为 \(1\)。

所以 \(l_2 = (W-L) + 2(R-W)\)，即 \(W = 2R - L - l_2\)。

D2

延续 D1 的思考，考虑如何缩小查询的大小。

将第一次查询换为填入 \(N\) 个 \(B\)。

若回答 \(l_1 = 0\)，说明 \(W < B\)，容易发现 \(\left \lceil \dfrac{m}{1} \right \rceil，\left \lceil \dfrac{m}{2} \right \rceil，\cdots，\left \lceil \dfrac{m}{\sqrt{m}} \right \rceil\) 这 \(\sqrt{m}\) 个数互不相同。

因此询问 \(B^2\) 个 \(1\) 即可。

若回答 \(l_1 \neq 0\)，同 D1 一样，我们也可以求出 \(W\) 的范围。

\[ W\in\left[\left\lceil\frac{C}{A_1}\right\rceil\cdot B,\min\left\{10^5,\left\lfloor\frac{C - 1}{A_1 - 1} + 1\right\rfloor\cdot B - 1\right\}\right] \]

证明与 D1 类似，不再展开。

这种方式的询问次数为 \(\min\{C+B^2,C+2(R-L)\}\)，写一个暴力找出合适的 \(N\) 与 \(B\) 即可。

接下来步骤同 D1。

E1/E2

F

不知道为什么，总感觉 CF 的最后一题没有倒数几题难。

先考虑每个点的 \(f_u\) 会是什么样子。

定义 \(X\) 是 能级数 当且仅当以下两个条件其一成立时：

  • \(X=x\)。
  • \(X=x^{X_1X_2X_3\cdots X_n}\)，其中 \(X_i\) 也是 能级数，并且 \(n\) 是一个常数。

\(f_u\) 就形如 能级数。

考虑比较 能级数 \(X = x^{X_1X_2X_3\cdots X_n}\) 和 \(Y = x^{Y_1Y_2Y_3\cdots Y_m}\) 的大小。

将指数从大到小排序，按照类似字典序比较即可。

证明略，本人数学不好。

接下来我们可以发现一个事实，一个父亲的 \(f\) 一定大于它的儿子的 \(f\)。

所以我们按照拓扑从叶子开始计算每个点的 \(f\)，维护一个堆，每次拿出一个最小的 \(f\) 更新。

用 vector 暴力维护 \(f\) 即可（排序，插入）。