Codeforces Round #827 (Div. 4) ABCDEFG 题解 (Java/C++)

A. Sum

题解

直接排序后看看前两个数之和等不等于第三个数即可。

代码

Java

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

C++

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

B. Increasing

题解

直接排序,然后看看相邻两个数有没有相等的。

代码

Java

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

C++

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

C. Stripes

题解

每行都扫一次,看能不能找到一整行都是R的。如果能,那么最后涂的必为R,否则必为B。(总不能啥都不涂吧)

代码

Java

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

C++

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

D. Coprime

题解

首先,观察到数据范围只有1000。而1000以内互质的数直接$10^6$的找出来就是了。
我们把找出来的这些互质的数分别放在1000个列表里,对于第$i$个列表,里面只放于$i$互质的所有数。

接着对于数组$a$中出现的每一个数,我们都记录其出现的最大的下标,记为max_pos。(如果结果真的选择的是这个数,那选下表大的总比小的强。)

最后,针对每一个出现的数$i$,去一开始的那个链表里找到与之互质的$j$,然后看看$j$的max_pos是不是存在,然后算一下这一对数的结果是多少,最后取最大的即可。

代码

Java

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

C++

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

E. Scuza

题解

显而易见的二分。

根据数组a,维护一个max。其中max[i]为,0到i中,a[i]的最大值。也就是跳到第i级,过程中会遇到的跨度最大的台阶。
再维护一个a的前缀和。

于是根据输入的k,只需要二分max即可。找到的i直接用前面维护的前缀和输出即可。

需要注意的是,a的取值范围可以到$10^9$,所以要注意前缀和要用64位的int。

代码

Java

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

C++

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

F. Smaller

题解

我们统计s和t中的各个字母个数。

显然,如果字符串t中存在非a的字母,那么直接把这个非a的字幕排在最前面,同时s把a排在最前面。

现在t中全是字母a。现在假设s中有一个不是a的字母。
如果s的字母a的个数小于t,那显然无论如何s都比t大。
如果s里a的个数多于或等于t,那么s一定比t长,所以s还是比t大。
综上,s里只要出现了非a的字母,那么s一定比t大。

最后,就只剩下s和t都全是a的场景。那就直接比长度即可。

代码

Java

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

C++

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

G. Orray

题解

首先,显而易见,数组b单增。同时,根据a的取值范围,b最多有64个不同的数。因为无非是每次把一位or成1。(实际上32个,但是不想思考long还是int,直接写64也一样)
因此,对于数组a的排列,其实只有前64位的排列会影响结果。(如果64位后,b还增加,则可以把这个对应的a放到前面,结果一定更优)

于是直接暴力枚举前64个数,对于第i个数,我们只需要保证所对应的b[i]尽可能大即可。

代码

Java

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

C++

Submission #178707967 - Codeforces
Codeforces. Programming competitions and contests, programming community
蜀ICP备19018968号