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

A. Square String?

题解

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

代码

Java

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

C++

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

B. Squares and Cubes

题解

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

代码

Java

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

C++

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

C. Wrong Addition

题解

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

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

代码

Java

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

C++

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

D. New Year's Problem

题解

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

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

代码

Java

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

C++

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

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

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

C++

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

F. Let's Play the Hat?

题解

每次都轮流安排人即可。

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

代码

Java

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

C++

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

G. Unusual Minesweeper

题解

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

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

代码

Java

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

C++

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

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