Codeforces Round #753 ABCDEFGH 题解 (Java/C++)

A. Linear Keyboard

题解

根据题意模拟即可。

代码

Java

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

C++

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

B. Odd Grasshopper

题解

不难发现,每4次跳跃之后一定会回到原点。

以$x_0$为奇数为例:$x_1=x_0+1$必为偶数。$x_2=x_1-2$也是偶数。$x_3=x_2-3$必为奇数。$x_4=x_3+4$必为奇数,且$x_4=x_0$。

代码

Java

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

C++

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

C. Minimum Extraction

题解

因为每次操作都是对所有数做相同的改变。所以每次选中的最小值是按照一开始的从小到大的顺序依次选取的。

所以只需要排序后依次模拟计算即可。

代码

Java

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

C++

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

D. Blue-Red Permutation

题解

考虑如下图所示的某个“Yes”的颜色分布情况。我们不难发现,一定可以通过继续对3和7做操作已得左边全是蓝色,右边全是红色的情况。

因此,我们只需要把蓝色和红色分别排序之后,依次放到最左边和最右边即可。过程中,我们如果发现有逆行的,就说明一定无解,输出No即可。

代码

Java

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

C++

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

E. Robot on the Board 1

题解

我们从(1,1)出发,按照命令执行即可。执行过程中,我们记录所访问到的点的范围。一旦发现范围超过了n和m,那么就停止执行。

代码

Java

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

C++

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

F. Robot on the Board 2

个人很不推荐这个题目。如果你没有AC这个题目,建议直接跳过本题。

Codeforces Round #753 Robot on the Board 2 题解 (Java/C++)
题解很明显是一个记忆化搜索。很明显,当前的点能走的最大距离=这一个点的下一个点的最大距离+1。这个题的麻烦之处在于代码实现,在实现过程中,有以下几点需要注意:
点击上面链接查看详细题解

G. Banquet Preparations 1

我们可以根据m的值计算出每道菜中a的取值范围,进而就可以根据剩下的总重量来决定a的值。

Codeforces Round #753 Banquet Preparations 1 题解 (Java/C++)
题解我们令每一道菜剩下来的总重量为$remain_i$,显然有$remain_i=a_i+b_i-m$。
点击上面链接查看详细题解

H. Banquet Preparations 2

和G题类似,根据a的取值范围,我们发现如果两个a的值域不相交,则必然是两个不同的菜。因此离散化即可。

Codeforces Round #753 Banquet Preparations 2 题解 (Java/C++)
题解显然,如果两道菜一样,那么两道菜的总重量也一定一样。而根据上一道题目,我们知道我们是可以算出最后剩下的a的取值范围的。于是问题就转化成了:对于剩余重量相同的菜来说,根据a的取值范围,最少需要多少种不同的a。
点击上面链接查看详细题解
展示评论