Codeforces Round #724 ABCDE 题解 (Java/C++)

A. Omkar and Bad Story

题解

显然,如果数组中存在任意一个小于0的负数。那么通过将这个数作为被减数,数组可以被无限增长。

但是如果没有负数,那么从0-100的所有数一定能够覆盖题目中所有的输入。

代码

Java

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

C++

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

B. Prinzessin der Verurteilung

题解

暴力枚举所有可能,然后和原串对比,直到找到符合条件的字符串。也就是首先枚举a,b,c,d,...,z,接着枚举aa,ab,ac,ac,...az,ba,bb,...zz。

为什么可以暴力枚举呢?因为我们考量所有两个字母的组合,总共有26*26=676种可能。如果一个原串能排除掉两个字母的所有可能,那么他的长度大概得高于676*2=1352。(注意,此处并不严谨,因为原串可以是aab,且zb可以由azba覆盖)

代码

Java

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

C++

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

C. Diluc and Kaeya

题解

不难发现,如果有一段的比率是3:1,另一段的比率是6:2=3:1。则这两段合并在一起后是9:3=3:1。

因此对于任意一个位置,我们只需要看前面有多少个点的比率等于当前点即可。

代码

Java

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

C++

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

D. Omkar and Medians

其本质是,对于新的一个b。因为相比之前其实只有两个新的值加入,因此对中位数的影响最多只是1位。

Codeforces Round #724 Omkar and Medians 题解 (Java/C++)
题解首先我们可以注意到,对于b[i+1],相比b[i]来说,其实只增加两个数:a[2i+1]和a[2i]。那么这两个数的中位数的影响其实只有一位。比如[1,3,5,7,9],其中位数是3,现在增加两个数,最多最多使中位数左移1位或者右移1位。
点击上面链接查看详细题解

E. Omkar and Forest

其实我们可以发现,非0位的值其实完全由值为0的位置决定。因此其实就是从#里面选若干点为0即可。

Codeforces Round #724 Omkar and Forest 题解 (Java/C++)
题解有两个结论: 对于图上任意一个点,假设这个点的值为x。则从这个点出发一定能找到一条路径使这个路径上的值为:[x,x-1,x-2,...,2,1,0]。根据题目中第二个条件,这个结论是显然的。
点击上面链接查看详细题解
展示评论