Codeforces Round 890 (Div. 2)

A. Tales of a Sort

大致题意

有个数列，每次操作可以将所有值减少 $1$，除非它已经是 $0$ 了，问需要多少次操作，才能将整个数列变成非递减数列

思路

很明显的一点，如果发现一对不满足条件的相邻对，即 $a_i > a_{i + 1}$，如果不把他们都减少到 $0$ 的情况下，永远无法满足题目条件，故只需要找到不满足的对，然后取最大的那个值即可

AC code

B. Good Arrays

大致题意

题目给出一个数组 $a$，要你判定是否存在另外一个数组 $b$，满足 $\sum_{i=1}^n a_i = \sum_{i=1}^n b_i, \forall i \in [1, n], a_i \neq b_i, a_i > 0, b_i > 0$

思路

读题易得：若原来的值是 $1$，那么必须找别的值借 $1$ 才能保证 $a_i \neq b_i$，而其他值则都可以简单变成 $1$ 解决。故只需要计算有多少可以冗余调配的值即可

需要特判一下只有一个值的情况

AC code

C. To Become Max

大致题意

有一个初始数组 $a$，每次可以选择一个 $i \in [1, n - 1]$，若 $a[i] \leq a[i + 1]$ 则使得 $a[i] = a[i] + 1$，问在最多操作 $k$ 次的情况下，数组的最大值可以为多少

思路

注意到数据量，$n$ 仅有 $1000$，意味着复杂度可以达到 $n^2 log(1e9)$ 的级别，然后再做思考

按照公式，那么最终得到的数组，必定存在一个恰好递减的阶梯。另外很明显的是，数组的最后一个值必定不可动，那就意味着实际上最大值的可行性是被最后一个值限定的，最大值为 $a_n + n - 1$

由于复杂度有非常大的冗余，故可以作出如下的暴力搜索

• 遍历所有可能为最大值的下标 $i$
• 二分查找最终的最大值
• 尝试构建最大值的可能性，是否能够在 $k$ 消耗内，完成构建一个阶梯

这样下来恰好复杂度满足预期

AC code

D. More Wrong

大致题意

交互题

有一个 $n$ 的排列 $a$，只知道长度 $n$，每次可以询问 $[l, r]$ 区间下，逆序对数量，每次询问的代价是 $(r - l)^2$，问如何在 $5 \times n^2$ 的代价下，找到最大值的下标

思路

区间逆序对，很容易想到归并排序

先得到两个简单的结论：

• 若已知一个区间的逆序对数量，再最后加入一个元素，且没有改变逆序对数量，那么这个加入的元素必定是当前区间的最大值
• 若已知一个区间的逆序对数量，再最前面加入一个元素，且增加了恰好等于原来元素个数的逆序对，则新加入的元素必定是当前区间的最大值

这两个结论显而易见，就不再解释

从归并排序的视角看，我们假定找到了一个区间前半部分的最大值的下标，又找到了后半部分最大值的下标，那么需要判断这两个值谁更大的时候，就可以通过上面的定律来判定，只需要两次查询即可

如此递归下去，可以得到最终的查询费用为

可以证得这个方法的消耗低于要求

AC code

E1. PermuTree (easy version)

大致题意

有一个树和一个 $n$ 的排列 $a$，求出使得满足 $a_u < a_{lca(u, v)} < a_v$ 这个等式的最多的排列下，满足多少次

思路

在树上并没有 $u, v$ 之分，实际上可以相互对掉，所以这棵树实际上需要尽可能满足二叉搜索树的结构才行，即每个节点下，左边的值都小于当前节点，右边的值都大于当前节点。

但是这不一定是一颗二叉树，而是多叉树，而在满足上述等式的情况下，则需要人为的将所有子节点划分为两份，一份大于一份小于。即，假如一个节点有 $3$ 个直接子节点，那么必定存在有两个直接的子节点的下的所有值都小于当前节点，同时另外一个直接子节点下的所有值都要大于此节点，那么最终的满足等式的量级为 $(cnt_1 + cnt_2) \times cnt_3$

而又因为划分的时候，总共的子节点数量之和是确定的，故需要尽可能对半分，那么就需要背包运算

而这又是树结构，所以只需要在树上 dp 上做背包 dp 即可

AC code

Generated by RSStT. The copyright belongs to the original author.

Source