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

A. Elections

题解

直接计算与另外两个人的票数的最大值的的差后再加一即可。

代码

Java

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

C++

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

B. Make it Divisible by 25

题解

能被25整除的数的特征是最后的两位只有4种可能:00,25,50,75。于是我们从后往前找这四种可能即可。

代码

Java

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

C++

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

C. Save More Mice

题解

因为猫到达洞口的时间是一定的,所以我们只需要在有限的时间内救出尽可能多的老鼠即可。而要救出一只老鼠需要花费的时间和一开始这只老鼠和洞口的距离直接相关。

因此,我们直接按照与洞口的距离排序,从距离短的依次救就可以了。

代码

Java

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

C++

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

D. All are Same/Half of Same

D1的做法不难想到。而D2对比D1,关键是想到可以通过暴力求出所有因数这一点。

Codeforces Round #748 All are Same/Half of Same ​题解 (Java/C++)
题解D1. All are Same首先,如果所有数都一样,那么k可以是任意值。所以我们只需要考虑存在不同的值的情况。因为通过减去若干次k后可以得到相同的数。所以一定可以在减去若干次k之后得到数组中最小的那个数。
点击上面连接查看详细题解

E. Gardener and Tree

题解

拓扑排序,只是需要用两个队列来计算次数。

代码

Java

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

C++

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

F. Red-Black Number

很明显的一个DP问题,关键是找出这个问题中的4个关键状态:前i个数、红色与黑色的数目的差、除以A和除以B的余数。

Codeforces Round #748 Red-Black Number 题解 (Java/C++)
题解一个很明显的dp问题。不难想到有这样几个状态:1、 前i个数字;2、|r-l|;3、除以A的余数;4、除以B的余数。于是我们就有这样的dp定义:dp[i][diff][x][y]表示前i个数,红色比黑色多diff个(不取绝对值),除以A余x,除以B余y时是否可能。
点击上面连接查看详细题解

G. Changing Brackets

这个题目的关键是发现括号下标的奇偶性对结果的影响。

Codeforces Round #748 Changing Brackets 题解 (Java/C++)
题解首先,根据题意,我们可以知道括号的方向完全不影响结果。那么很自然的,我们只需要考虑不同类型括号的奇偶性。于是我们注意到,如果两个相邻的方括号之间有奇数个圆括号(反过来也一样),那么至少需要1个圆括号改成方括号。
点击上面连接查看详细题解