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

A. Shortest Path with Obstacle

题解

当且仅当ABF三个点在一条直线，且F在AB之间时，答案是曼哈顿距离+2。否则答案就是AB的曼哈顿距离。

代码

Java

C++

B. Alphabetical Strings

题解

找到字母a第一次出现的位置，然后从这个位置开始，往左右依次找后续的字母。如果不能依次把整个字符串找完，就是不能。

代码

Java

C++

C. Pair Programming

题解

直接模拟即可。只要a可以满足条件就优先拿，不然就试试b里能不能满足条件。否则就是不行。

代码

Java

C++

D. Co-growing Sequence

题解

首先第一个数一定是0。同时显然有(x[i]^y[i])&(x[i+1]^y[i+1])=(x[i]^y[i])。于是y[i+1]=[(x[i] ^y[i]) & x[i+1]]^ (x[i] ^y[i])。
也就是说，对于上一次的结果x[i] ^y[i]，如果某一位置都是1，则这个位置的y应该是0。
如果x[i] ^y[i]是1，而x[i+1]是0，则y必须是1。
如果x[i] ^y[i]是0，而x[i+1]是1，则y应该是0，这样可以保证y尽可能的小。

代码

Java

C++

E. Air Conditioners

题解

每个房间的最终温度无非是三种情况：1. 左边的某个空调温度最低；2. 右边某个空调温度最低；3. 自己所在的房间温度最低。

于是很自然的，我们先从左往右扫描，自然的有dp[i]=min(dp[i-1]+1, a[i])。同理，再从右往左扫描一次即可。

代码

Java

C++

F. Array Stabilization (GCD version)

题解

线段树的模板题目。维护区间的gcd之后，二分找出最小的的区间长度使得这个区间内的gcd等于整个数组的gcd。

代码

Java

C++

G. How Many Paths?

题解

两次dfs即可。第一次dfs，我们可以找出：不可达的点、有多重来源的点、产生环的点以及普通的只有一条路的点。
接着，第二次dfs主要是对产生环的点和有多条路的点进行扩展，因为从这些点出发，所有可达的点都是有无数条路或者有多条路可走。

代码

Java

C++