Codeforces Round 891(Div. 3)

A. Array Coloring

给你一个由 $n$个整数组成的数组。你的任务是确定是否有可能用两种颜色给数组中的所有元素着色，使得两种颜色元素的和具有相同的奇偶性，并且每种颜色至少有一个元素被着色。

例如，如果数组是 [$1,2,4,3,2,3,5,4$]，我们可以如下着色： $\color{blue}{1},\color{blue}{2},\color{red}{4},\color{blue}{3},\color{red}{2},\color{red}{3},\color{red}{5},\color{red}{4}$，其中蓝色元素的和为$6$，红色元素的和为$18$。

这题很简单，只需要记录 $a$ 为奇数的个数，如果这个数也是奇数那么就是YES，否则就是NO。

B. Maximum Rounding

给定一个自然数 $x$。您可以执行以下操作：

选择一个正整数 $k$，并将 $x$取整到第 $k$位

注意，位置是从 0 开始从右向左编号的。如果数字有$k$位，则认为第$k$位上的数字等于$0$。

四舍五入的方法如下：

如果第$(k-1)$位上的数字大于或等于第$5$位，则第$k$位上的数字增加第$1$位，否则第$k$位上的数字保持不变（使用数学四舍五入）。

如果在运算之前，第$k$位上的数字是$9$，而它应该增加$1$，那么我们搜索最小的位置$k'(k'>k)$） $k'$-th位置的数字小于$9$，并在$k'$-th位置的数字上加上$1$。然后我们赋值$k=k'$。

之后，所有位置小于 $k$的数字都被替换为 0。

您的任务是在尽可能多次执行运算的情况下，使 $x$尽可能大。

例如，如果$x$等于$3451$，那么如果连续选择：

$k=1$，则操作后$x$将变为$3450$- $k=2$，则操作后$x$将变为$3500$- $k=3$，则操作后 $x$将变为 $4000$- $k=4$，则操作后$x$将变为$0$
要使答案最大化，需要先选择 $k=2$，然后再选择 $k=3$，那么数字就会变成 $4000$。

分步走，可以先求这个数的四舍五入后的数，再来将原本大于5的最高位的位置以及之后的数归零，注意最后的答案可能还会再高一位

C. Power of Points

萨沙有一个由 $n$个整数组成的数组 $a$。他觉得无聊，于是写下了所有 $i$、$j$（$i \lt j$）的最小值 $a_i$和 $a_j$。他得到了一个大小为$\frac{n\cdot (n-1)}{2}$的新数组$b$。

例如，如果 $a=$他就会写[$\min(2, 3), \min(2, 5), \min(2, 1), \min(3, 5), \min(3, 1), min(5, 1)$] $=$。[$2, 2, 1, 3, 1, 1$].

然后，他随机地了数组$b$中的所有元素。

不幸的是，他忘记了数组 $a$，而你的任务是还原任何可能的数组 $a$，并从中得到数组 $b$。

数组 $a$的元素应在数组 $[-10^9,10^9]$的范围内*。

这题我们可以知道 $b$ 数组是通过 $\min(a_i, a_j)$ 得到的，那么我们就很好想到在 $b$ 数组中，最小的数肯定出现了 $n-1$ 次，次小的值出现 $n-2$ 次，以此类推。这样我们就能够造出这个 $a$ 了。

D. Strong Vertices

给定长度均为$n$的两个数组$a$和$b$。这两个数组的元素从 $1$索引到 $n$。您正在构建一个有向图，如果有 $a_u-a_v \ge b_u-b_v$，则存在从 $u$到 $v$（$u\neq v$）的边。

如果存在从$V$到所有其他顶点的路径，则顶点$V$称为强顶点。

有向图中的路径是由若干顶点组成的链，这些顶点由边连接，这样从顶点$u$沿着边的方向移动，就可以到达顶点$v$。

你的任务是找出所有强顶点。

例如，如果有$a=[3,1,2,4]$和$b=[4,3,2,1]$，那么图形将如下所示：

该图只有一个强顶点，其编号为 $4$。

首先根据

\[a_u-a_v \ge b_u-b_v \]

\[a_v-a_w\ge b_v-b_w \]

\[a_u-a_w \ge b_u-b_w \]

那么它就是有传递性的，这样我们就求出最大的 $a_i-b_i$ ，记录个数，然后后面的就是 $a_i-b_i$ 的 $i$ 了。

E. Power of Points

给你$n$个点，其整数坐标为$x_1,\dots x_n$，它们位于一条数线上。

对于某个整数 $s$，我们构造线段 [$s,x_1$]， [$s,x_2$]， $\dots$， [$s,x_n$]。请注意，如果是$x_i \lt s$，那么线段看起来就像[$x_i,s$]。线段 [$a, b$/]覆盖了所有整数点 $a, a+1, a+2, \dots, b$。

我们将点$p$的幂定义为与坐标为$p$的点相交的线段数，记为$f_p$。

您的任务是计算每个$s \in \{x_1,\dots,x_n\}$的$\sum\limits_{p=1}^{10^9}f_p$，即从$1$到$10^9$的所有整数点的$f_p$之和。

例如，如果初始坐标为$[1,2,5,7,1]$，我们选择$s=5$，那么线段将是$[1,5]$,$[2,5]$,$[5,5]$,$[5,7]$,$[1,5]$.这些点的幂将是$f_1=2, f_2=3, f_3=3, f_4=3, f_5=5, f_6=1, f_7=1, f_8=0, \dots, f_{10^9}=0$.它们的和为$2+3+3+3+5+1+1=18$。

排序后考虑先用 $\Theta(n)$ 计算最左边点的值，然后考虑将起点往下移动一位，左边的区间长度增加了多少，右边的区间长度增加了多少

F. Sum and Product

你有一个长度为 $n$的数组 $a$。

你的任务是回答 $q$个查询：给定 $x,y$，找出既有 $a_i + a_j = x$又有 $a_i \cdot a_j = y$的数对 $i$和 $j$（$1 \le i \lt j \le n$）的个数。

也就是说，对于数组$[1,3,2]$，问$x=3,y=2$，答案是$1$：

$i=1$和$j=2$失败是因为$1 + 3 = 4$而不是$3,$也是$1 \cdot 3=3$而不是$2$；

$i=1$和 $j=3$满足这两个条件；

$i=2$和 $j=3$不合格是因为 $3 + 2 = 5$而不是 $3,$也是 $3 \cdot 2=6$而不是 $2$；