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

A. Two Vessels

题解

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

代码

Java

C++

B. The Corridor or There and Back Again

题解

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

代码

Java

C++

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

C++

D. Plus Minus Permutation

题解

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

代码

Java

C++

E. Data Structures Fan

题解

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

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

代码

Java

C++

F. Selling a Menagerie

题解

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

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

代码

Java

C++

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

C++