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尽可能的小。