Codeforces Round 898 (Div. 4)

A. Short Sort

大致题意

有三张卡片，分别为 $a, b, c$，已经在桌面上乱序排好，最多交换两张卡片的位置，问是否能够变成有序的 $a, b, c$

思路

简单题，判断一下是不是至少有一位是保持 $a, b, c$ 的顺序即可

AC code

B. Good Kid

大致题意

有一个数组，允许你给其中一个值加一，问最终所有值的乘积最大是多少

思路

简单题，如果有两个及以上的 $0$，那么最终结果一定还是 $0$。如果只有一个 $0$，那就等于忽略这个 $0$ 即可，剩下的情况，因为加了之后的效果是 $\frac{x+1}{x}$，所以 $x$ 越小越好，那么让最小的值 $+1$ 即可

AC code

C. Target Practice

大致题意

有一个飞镖靶，根据结果计算总分

思路

简单题，根据当前的下标距离四个边最小值是多少即可

AC code

D. 1D Eraser

大致题意

有一个串，其中有白色和黑色方块，每次可以选择连续 $k$ 个块让其变成白色，问最少几步可以全部变成白色

思路

简单题，从左往右考虑即可，毕竟最左边遇到的第一个黑色方块肯定需要消耗一次操作，为了最大化使用必定会让 $k$ 个的左边界是当前的黑色方块

AC code

E. Building an Aquarium

大致题意

有一个线性水池，水池底部形状已知，最多可以使用 $x$ 个单位的水，问水池两边应该造多高才能尽可能容纳更多的水的同时，在水池满的时候不会使用超过给出的水

思路

简单题，二分答案即可

AC code

F. Money Trees

大致题意

给出一个数组，其每个值都有两个属性：$a, h$，需要找到一个连续的子数组，使得这个连续的子数组 $[l, r]$的 $h$ 值满足 $\forall i \in [l, r], h_{i-1} \space mod \space h_i = 0$，同时 $\sum_{i=l}^{r} a_i \leq x$

问最长的子数组的长度

思路

也是二分答案即可，毕竟在确定要找的最终串的长度的情况下，只需要 $O(n)$ 即可求出是否符合预期，注意平移区间的时候状态的转化

AC code

G. ABBC or BACB

大致题意

有一个字符串，由 $A, B$ 两个字母组成，每次可以将 $AB$ 转为 $BC$，或者将 $BA$ 转为 $CB$，问最多可以操作几次

思路

很显然，如果是一串联系的 $A$，然后其中一侧有一个 $B$，那么这种情况下的答案就是 $A$ 的数量

那么将整个数组拆成所有连续的 $A$ 段，然后为每个 $A$ 段找合理的 $B$ 即可。比如如果整个字符串开头或者结尾是 $B$，那么必然可以为每个 $A$ 段找到一个 $B$。除开上面的情况，只需要看看 $B 的数量是否大于等于 $A$ 段的数量即可，因为如果等于或者超过也必然可以分割。如果还不行，那么只能舍弃价值最低的 $A$ 串了

AC code

H. Mad City

大致题意

有一个图，$n$ 个点，$n$ 条边，有两个人分别从 $a, b$ 出发，其中前者希望追赶后者，而后者希望摆脱前者的追捕，问能否追上

思路

首先，$n$ 个点和 $n$ 条边，那就意味着必然图中必然存在环。而两人速度相同，如果同时都在环上，那肯定追不到。所以必须要在后者进入环之前抓到，也就是提前或者刚好到达环上的某一个点。所以只需要找出后者刚进入环的时间点和位置，看看前者能否在指定时间内达到即可

AC code

Generated by RSStT. The copyright belongs to the original author.

Source