Codeforces Round #760 ABCDEFG 题解 (Java/C++)

A. Polycarp and Sums of Subsequences

题解

我们假设a[1]<a[2]<a[3]。于是自然有b[7]=a[1]+a[2]+a[3], b[6]=a[2]+a[3]，b[5]=a[1]+a[3]。
于是a[1]=b[7]-b[6]，a[3]=b[5]-a[1]。最后a[2]=b[7]-a[1]-a[3]。

代码

Java

C++

B. Missing Bigram

题解

如果当前的字符串的第一个字符等于之前的字符串的最后一个字符，那么就继续。如果一旦发现不等，那么此处一定是漏掉了一个串，补上即可。

如果整个过程一直相等，那么最后随便补充一个字符即可。

代码

Java

C++

C. Paint the Array

题解

显然这个d要么是所有奇数位的最大公约数，要么是所有偶数位的最大公约数。
而这一个d，必然不能整除剩下的任意一个数。

代码

Java

C++

D. Array and Operations

题解

显然，我们尽可能拿大的数来执行操作，且尽可能使每次操作的结果是0即可。

代码

Java

C++

E. Singers' Tour

题解

这就是一个一个线性方程求解的问题（以n=5为例）：$$\begin{cases}
1\cdot a_1 + 5\cdot a_2 + 4\cdot a_3 + 3\cdot a_4 + 2\cdot a_5=b_1 \\
2\cdot a_1 + 1\cdot a_2 + 5\cdot a_3 + 4\cdot a_4 + 3\cdot a_5=b_2 \\
3\cdot a_1 + 2\cdot a_2 + 1\cdot a_3 + 5\cdot a_4 + 4\cdot a_5=b_3 \\
4\cdot a_1 + 3\cdot a_2 + 2\cdot a_3 + 1\cdot a_4 + 5\cdot a_5=b_4 \\
5\cdot a_1 + 4\cdot a_2 + 3\cdot a_3 + 2\cdot a_4 + 1\cdot a_5=b_5 \\
\end{cases}$$

于是$15\cdot a_1 + 15\cdot a_2 + 15\cdot a_3 + 15\cdot a_4 + 15\cdot a_5=b_1+b_2+b_3+b_4+b_5$。所以$a_1+a_2+a_3+a_4+a_5=\frac {b_1+b_2+b_3+b_4+b_5} {15}$。

我们令$sum=\frac {b_1+b_2+b_3+b_4+b_5} {15}$
于是$$\begin{cases}
4\cdot a_2 + 3\cdot a_3 + 2\cdot a_4 + 1\cdot a_5=b_1-1\cdot sum \\
-1\cdot a_2 + 3\cdot a_3 + 2\cdot a_4 + 1\cdot a_5=b_2-2\cdot sum \\
-1\cdot a_2 + -2\cdot a_3 + 2\cdot a_4 + 1\cdot a_5=b_3-3\cdot sum \\
-1\cdot a_2 + -2\cdot a_3 + -3\cdot a_4 + 1\cdot a_5=b_4-4\cdot sum \\
-1\cdot a_2 + -2\cdot a_3 + -3\cdot a_4 + -4\cdot a_5=b_5-5\cdot sum \\
\end{cases}$$
我们发现，上面的式子中，相邻两个表达式就能求出一个a的值（不包含$a_1$）。

最后我们根据其他的$a_i$，计算出$a_1$即可。
期间，我们需要验证几个点：1. sum应该是一个整数；2. $a_i$不能超出范围；3. $a_1$要计算两次确保有解。

而不论是sum的值，还是a的值，整个求解过程都是$O(n)$的。

代码

Java

C++

F. Reverse

题解

直接暴力搜索即可。因为不难发现，往右侧添加0其实是非常困难的。事实上添加0是困难的。因为右侧添加了0并且反转了之后，0会消失。所以其实可能出现的值其实是非常有限的，因此直接暴力搜索即可。

代码

建议参考Java代码，C++由于DFS过程中的堆栈，有一些优化，降低了可读性。

Java

C++

G. Trader Problem

这是一道非常优秀的并查集和离线处理的题目。