Codeforces Round #762 (Div. 3) ABCDEFG 题解 (Java/C++)

A. Square String?

题解

首先看能不能被2整除，接着验证前半段和后半段是否相同即可。

代码

Java

C++

B. Squares and Cubes

题解

提前预处理好所有的这些数。之后放在map里或者二分都可以解决这个问题。

代码

Java

C++

C. Wrong Addition

题解

从右往左依次模拟即可。如果某一位的s大于等于a，这一位上的a+b一定不会大于等于10。反之，上一位的s和这一位的s凑起来必然等于a+b。

如果过程中发现无法构造，那么就是无法构造。

代码

Java

C++

D. New Year's Problem

题解

二分搜索最终的结果。如果这个结果可以成立，那么一定满足下面的条件：

1. 每个人都至少能找到一个店家，使得这个人的满意度在这家店高于当前的结果。
2. 至少存在一个店家，使得这个店家可以同时满足至少两人。

代码

Java

C++

E. MEX and Increments

题解

首先我们统计每个数字的出现次数，记为count。

对于第i个数，显然我们至少需要将count[i]全部改为i+1。
接着我们再加上需要多少步才能使0到i-1都有值即可。

显然，为了使0到i-1都有值，需要做操作的情况一定是：某一个count[j]=0 (j<i-1)。而此时，从j往左找到最近的k使得count[k]>1。
于是我们用一个list维护所有的count[k]>1，每当发现count[j]=0，就从list中拿一个填上来即可。
于是，我们就能按照在计算完当前的i之后，顺便更新这个list，并且提前计算好使0到i都有值的最小开销。

代码

Java

C++

F. Let's Play the Hat?

题解

每次都轮流安排人即可。

以m=3，n=8为例，我们做出以下的安排：

代码

Java

C++

G. Unusual Minesweeper

题解

首先我们通过DSU，把会一起爆炸的地雷都联系在一起。

于是我们对所有的连通块进行排序。然后一秒一秒的模拟，直到所有的连通块都爆炸为止。

代码

Java

C++

还有个H题，看了一眼是2400，然后好像又比较麻烦。毕竟新年了，就偷个懒。