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

A. Stone Game

题解

首先我们找到最大值和最小值的位置。接着有四种可能:一直删左边、一直删右边、从左往右删最大值且从右往左删最小值、从右往左删最大值且从左往右删最小值。

代码

Java

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

C++

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

B. Friends and Candies

题解

计算所有的糖的数目,如果不能被n整除。那么最终无论如何都没有解。

如果可以整除。那么显然,我们需要做的只是把有多余糖的人的糖都收上来重新分配即可。

代码

Java

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

C++

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

C. Number of Pairs

题解

首先对a排序。对于任意的i,我们可以找到j使得j<i且$l\leq a_j+a_i\leq r$。
于是,对于指定的i,立刻有$l-a_i\leq a_j\leq r-a_i$。于是我们可以通过二分得到j的取值范围。于是我们就能log的求出:当i作为较大的一项时,有多少较小的值可以选择。

代码

Java

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

C++

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

D. Another Problem About Dividing Numbers

题解

首先我们注意到,要把a和b除成相同的数,那么这个相同的数的最大可能的值就是这两个数的最大公约数。

显然。只要$\frac{a}{gcd}$和$\frac{b}{gcd}$不是1。那么无论如何2步一定能把a和b都变成1。如果其中有是1的,那么连2步都用不到。那么,如果k连这个都达不到,那么一定无解。因此这个是k的最小值。

接着,如果a的素因数的数目+b的素因数的数目都不不够还没有k大。那么就算每次我们都只除以一个素因数,最后都还是不够除。因此一定无解。因此,我们得到了k的最大值。

到这里,其实基本上我们已经得到k的最大值和最小值了。只要k在这个范围内一定会有解。但是有一个例外:
我们注意到这样一个现象,对于两个相同的数,如果我们要求k=1,则一定无解。比如样例的2 2 1。
也就是这两个数本身就相同,结果还要求改一步的话,这个是无解的。这是唯一一个例外。

代码

Java

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

C++

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

E. Funny Substrings

题解

我们维护每一个变量对应的字符串的头3个字符和最后3个字符,对应的字符串的长度,以及这个变量目前已经有多少解。

我们可以看到如果两个变量拼接起来。我们发现,其解是:两个变量各自的解,加上前一个变量的后3个字符和后一个变量的前3个字符拼接起来后形成的新字符串的解的数目。

代码

Java

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

C++

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

F. Interesting Function

题解

显然我们只需要得到从0到r的数字变化次数,以及从0到l的数字变化次数。两者相减即可。

接着我们发现,对于任意的x,从0开始到x结束。个位上必然改了x次。十位上必然改了$\frac{x}{10}$次,百位上改了$\frac{x}{100}$次……

代码

Java

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

C++

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

G. Gift Set

题解

对于有两种选择方式,我们假设两种选择方式被选择的次数分别为p1和p2。于是必然有$p1\cdot a + p2 \cdot b \leq x$且$p1\cdot b + p2 \cdot a \leq y$。

我们可以发现p2的值是可以由p1决定的。可以得到$p2=\min(\frac{(x - p1 * a)} {b} , \frac {(y - p1 * b)} {a})$。于是礼物总数为:$p1+\min(\frac{(x - p1 * a)} {b} , \frac {(y - p1 * b)} {a})$。
我们可以发现,这里的f(p1)的斜率是$1-\frac a b$或$1-\frac b a$。显然,斜率的正负取决于a和b的大小。

于是,f(p1)的图像画出来有4种可能:单调递增、单调递减、上凸的曲线,下凹的曲线。
对于单增、单减和下凹的情况,其结果无非是从全选p1或者全选p2。
于是我们针对上凸的曲线按斜率进行二分之后,在和两端取最大值即可。

代码

Java

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

C++

Submission #119188912 - Codeforces
Codeforces. Programming competitions and contests, programming community
展示评论