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

A. Stone Game

题解

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

代码

Java

C++

B. Friends and Candies

题解

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

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

代码

Java

C++

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

C++

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

C++

E. Funny Substrings

题解

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

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

代码

Java

C++

F. Interesting Function

题解

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

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

代码

Java

C++

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

C++