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

Submission #140178453 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #140178560 - Codeforces
Codeforces. Programming competitions and contests, programming community

B. Missing Bigram

题解

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

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

代码

Java

Submission #140180603 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #140180730 - Codeforces
Codeforces. Programming competitions and contests, programming community

C. Paint the Array

题解

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

代码

Java

Submission #140182897 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #140183130 - Codeforces
Codeforces. Programming competitions and contests, programming community

D. Array and Operations

题解

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

代码

Java

Submission #140596362 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #140596487 - Codeforces
Codeforces. Programming competitions and contests, programming community

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

Submission #140723967 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #140724122 - Codeforces
Codeforces. Programming competitions and contests, programming community

F. Reverse

题解

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

代码

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

Java

Submission #140726198 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #140731042 - Codeforces
Codeforces. Programming competitions and contests, programming community

G. Trader Problem

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

Codeforces Round #760 Trader Problem 题解 (Java/C++)
题解首先,我们可以直接把所有物品一起考虑。我们考虑下面的例子(我基于样例改了一点点):我们考虑k=2时,经过若干次交易之后的结果:
点击上面链接查看详细题解
展示评论