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

A. Two Vessels

题解

数据规模很小,都在100以内。所以直接从多的往少的一次次模拟倒水即可。

代码

Java

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

C++

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

B. The Corridor or There and Back Again

题解

很显然,一旦走过某个陷阱,那么就必须在走$\lfloor{\frac{s-1}{2}}\rfloor$后返回。
所以我们只需要计算每个陷阱被踩到并折返时能走到最远的k,取最小即可。

代码

Java

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

C++

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

C. Non-coprime Split

题解

假设a和b存在,且其最大公约数为g。那么$(a+b)=g\cdot(\frac a g + \frac b g)$。也就是说a+b必然被g整除,且$\frac a g + \frac b g > 1$。

那么我们就只需要找到l和r之间的任意一个合数即可。这样,我们选择其中的一个因数作为g,令a=g,$b=\frac x {g} - 1$。

代码

Java

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

C++

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

D. Plus Minus Permutation

题解

显然,x和y的最小公倍数所对应的数不会影响最终结果。所以我们只需要让x其余对应的数尽可能大,y其余对应的数尽可能小即可。

代码

Java

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

C++

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

E. Data Structures Fan

题解

我不是很确定这道题有没有什么更简便的做法。我是直接一个线段树,维护g=0和g=1分别对应的区间异或和。

每次更新的时候无非是吧g=0和g=1的异或和交换一下。最后查询整个区间的异或和即可。

代码

Java

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

C++

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

F. Selling a Menagerie

题解

把动物i害怕$a_i$看作是一条i指向$a_i$的一条单向边。于是就得到了一个有向图,且这个图里的每个点都只能有一条出边和任意条入边。
这个图大体应该是若干个类似下图的结构:

很自然的,对于没有入边的点,删了也就删了,并不会对收入有任何影响。所以优先删入度为0的点。
这样我们就回剩下若干个环。
对于这些环,自然是选择放弃价值最小的点。所以我们找出环上价值最小的点x,删去$a_x$这个点。

代码

Java

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

C++

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

G. Replace With Product

题解

首先,如果$a_i\geq 2$,那么当然是选择乘法比加法的结果好。所以问题的根本在$a_i=1$怎么处理上。

显而易见,位于最左端和最右端的1肯定要排除在[l, r]之外。所以我们可以认为数组的开头和结尾都不是1。
那么剩下的情况就是[2,1,1,1,1,1,1,2]和[3,1,3]的区别。也就是说,中间有大量的1的情况选择加法比乘法好。
但问题是,1最多只能有$10^5$个,也就是说,中间夹着的1的总和最多$10^5$。也就是说,只要有差不多20个2存在,那么无论如何选择乘法都是更优的。因为$2^20>10^5$。
所以大概的思路就是当数组里不是1的数的乘积达到一定数目时,l和r直接选最大的区间即可(当然最左和最右的1要排除)。否则,直接暴力枚举l和r的位置。

需要注意的是,这个乘积的数目不能是$10^5$。因为可能是类似于$[2, 1, 1, ..., 1, 5\cdot 10^4]$。选择乘法的结果是$10^5$,但加法的结果是$(10^5-2)+2+5\cdot 10^4=1.5 \cdot 10^5$。
具体取多少才行我就没算了,直接给的$10^6$。反正$2^32 > 10^9$了,也就是怎么样也就是不到32个数。

代码

Java

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

C++

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