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

A. Casimir's String Solitaire

题解

显然，当且仅当字母A和字母C的数目之和等于字母B的数目时Yes，否则No。

代码

Java

C++

B. Shifting Sort

题解

显然，我们从右到左，做n次操作，每次操作只恢复1位即可。

代码

Java

C++

C. Ticks

题解

从下往上依次遍历，每当发现一个被涂色的格子就尝试寻找尽可能的大的d，如果d>k，则从这个点出发把相关的点都标记一次。最后只需要检查是否所有被涂色的格子都有被标记过即可。

代码

Java

C++

D. Productive Meeting

题解

模拟即可。每次都把社交意愿最强烈的两个人用优先队列找出来，让他们聊天即可。

代码

Java

C++

E1. Permutation Minimization by Deque

题解

模拟即可，只需要看当前的数是不是小于最前面的数，如果是那么就放最前面，否则就放在后面。

代码

Java

C++

E2. Array Optimization by Deque

题解

不难发现，当我们添加一个新的数的时候，不论我们放在前面或是后面，这个数和之前其他数的关系都会被确定下来。而这个数和之后的数的关系其实完全由之后的数决定。

于是我们只需要贪心的添加每个数。我们添加一个新的数的时候，我们只需要看看已有的数中，有多少数小于自己，有多少数大于自己即可。

为了统计大于或小于某个数的数字个数，我们可以将a hash到1到$10^5$的范围，然后用树状数组或者线段树统计区间内的数的个数即可。

代码

Java

C++

F. Array Stabilization (AND version)

题解

以n=5，d=2以及n=4，d=2为例，我们能得到下图的变换。

不难发现，每一个位置都是一个固定的循环。我们找出这些循环，然后统计出其最长的连续的1即可。

因为是循环，所以我们直接循环两次来找出最长连续的1。
另外需要注意的是，如果全是1的话，则输出-1即可。

代码

Java

C++

G. Minimal Coverage

是一个不错的DP问题。关键是找出真正的有效的状态。之后就能比较容易的想到状态转移方程。