Codeforces Round 890 (Div. 2)

A Tales of a Sort

阿尔芬有一个长度为 \(n\)的正整数数组 \(a\)。

阿尔芬可以进行以下运算：

对于从 \(1\) 到 \(n\) 的所 \(i\)，用 \(\max(0, a_i - 1)\) 替换 \(a_i\)。

阿尔芬将执行上述操作，直到 \(a\) 排序完毕，即 \(a\) 满足 \(a_1 \leq a_2 \leq \ldots \leq a_n\) 。阿尔芬将执行多少次操作？在问题的约束条件下，可以证明阿尔芬将执行有限次的操作。

这题一开始写了一个暴力，~~想不到为什么Div. 2的T1还要先写暴力~~ ，然后一看样例，就想到了。

本题的思路就是我们倒序求出第一个无序的 \(a_i\) ，记录这个 \(i\) ，接着求出在这个区间内最大的 \(a_i\) ，这个就是答案。这题还有个做法是（二分），但是除了 kzy 等巨佬没人会这么写吧。

B Good Arrays

给你一个长度为 \(n\) 的个正整数数组 \(a\)

我们把长度为 \(n\) 的个正整数数组 \(b\) 称为好数组，如果：

从 \(1\) 到 \(n\) 的所有 \(i\) 都是 \(a_i \neq b_i\)、

\(a_1 + a_2 +\ldots + a_n = b_1 + b_2 + \ldots + b_n\).

存在好的数组吗？

这题一开始写了个假又很真的算法，就是

for (ull i = 1; i <= n; ++i)
		scanf("%llu", &a[i]), sum += a[i];
	
if (n == 1) {
    puts("NO");
    return ;
}

if (sum >= n * 2 - 1)
    puts("YES");
else
    puts("NO");

这个算法既能过样例，又能过自己的hack数据，（这个数据连 kzy 的假算法都过不了）。过了一个多小时，脑子灵光一闪，发现我们只需要记录 \(1\) 出现的个数，用 \(n\) 来减掉他，记减完的数为 \(cnt\) ，用 \(a\) 的总和记 (\(sum\)) ，减去 \(cnt\) ，如果他大于等于 \(2 \times 1的出现个数\) 。就是 YES 否则就是 NO 。

C To Become Max

给你一个长度为 \(n\)的整数数组 \(a\)。

在一次操作中，你

选择一个索引 \(i\)，使得 \(1 \le i \le n - 1\) 和 \(a_i \le a_{i + 1}\)。

用\(1\)增加\(a_i\)。

求最多进行 \(k\)次这一运算后所得到的 \(\max(a_1, a_2, \ldots a_n)\)的最大可能值。

只能说B题花了太多时间，T3只看了题面。

对每个位置二分查可能出现最大值

假如 \(id\) 位置能到 \(x\)，\(id\) 右边会变成阶梯下降，要能组成这个阶梯，阶梯最右点的 \(a_j\) 不能比阶梯低

D. More Wrong

又是交互题。

E1 PermuTree (easy version)

你一棵以顶点 \(1\) 为根、有 \(n\) 个顶点的树。

对于某个排的长度为\(n\)时，设\(f(a)\)是使得\(a_u < a_{\operatorname{lca}(u, v)} < a_v\)的顶点对数\((u, v)\)。这里，\(\operatorname{lca}(u,v)\)表示顶点 \(u\) 和 \(v\) 的最近共同祖先。

求所有长度为 \(n\)的排列 \(a\)中 \(f(a)\)的最大可能值。

\(^\dagger\)长度为 \(n\) 的排列是由 \(n\) 个不同的整数组成的数组，这些整数的顺序从 \(1\) 到 \(n\)。例如，\([2,3,1,5,4]\)是一个排列，但\([1,2,2]\)不是一个排列（\(2\)在数组中出现了两次），\([1,3,4]\)也不是一个排列（\(n=3\)但在数组中有\(4\)）。