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

A. Shortest Path with Obstacle

题解

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

代码

Java

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

C++

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

B. Alphabetical Strings

题解

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

代码

Java

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

C++

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

C. Pair Programming

题解

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

代码

Java

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

C++

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

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

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

C++

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

E. Air Conditioners

题解

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

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

代码

Java

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

C++

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

F. Array Stabilization (GCD version)

题解

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

代码

Java

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

C++

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

G. How Many Paths?

题解

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

代码

Java

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

C++

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