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

A. Casimir's String Solitaire

题解

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

代码

Java

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

C++

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

B. Shifting Sort

题解

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

代码

Java

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

C++

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

C. Ticks

题解

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

代码

Java

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

C++

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

D. Productive Meeting

题解

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

代码

Java

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

C++

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

E1. Permutation Minimization by Deque

题解

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

代码

Java

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

C++

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

E2. Array Optimization by Deque

题解

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

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

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

代码

Java

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

C++

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

F. Array Stabilization (AND version)

题解

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

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

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

代码

Java

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

C++

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

G. Minimal Coverage

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

Codeforces Round #744 Minimal Coverage 题解 (Java/C++)
题解首先,我们先思考最朴素的做法:显然对于每一个线段来说,都会产生往左或者往右两种可能。每种可能都会包含三个信息:最左端的位置,最右端的位置和当前结束的位置。
点击上面连接查看详细题解
展示评论