Codeforces Round #736 (Div. 2) ABCD 题解 (Java/C++)

A. Gregor and Cryptography

题解

如果P是偶数,则输出2和P即可,这样同余0。如果P是奇数,则输出2和P-1即可,这样同余1。

代码

Java

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

C++

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

B. Gregor and the Pawn Game

题解

如果直线可以走过去,那么这些棋子优先走过去。
接着考虑必须要吃一个对方棋子的。从左往右依次考虑剩下的棋子,并且优先往左吃。

代码

Java

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

C++

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

C. Web of Lies

题解

如果一个贵族有一个比他更大的贵族朋友,那么这个贵族迟早被干掉。因为比这个贵族小的贵族一定会被干掉,下一个就是这个贵族。

因此我们只需要统计有多少贵族有比自己大的朋友即可。

代码

Java

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

C++

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

D. Integers Have Friends

题解

$a_i \bmod m = a_{i+1} \bmod m = \ldots = a_j \bmod m$则必有$(a_{i+1} - a_i) \bmod m = (a_{i+2} - a_{i+1}) \bmod m = \ldots = (a_j - a_{j-1}) \bmod m = 0$。

令$d_i=a_{i+1}-a_i$于是我们如果我们要验证i到j这个区间内是否存在这样的m,我们只需要验证$\gcd(d_i, d_{i+1}, \ldots , d_{j-1})$是否不为1即可。

于是我们很自然的想到利用线段树维护区间GCD。然后通过枚举i和j获取最长的区间即可。
而我们枚举j的时候,不需要每次都从i开始重新枚举,我们可以基于上个i留下的j继续向后枚举即可。

代码

Java

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

C++

Submission #124880246 - Codeforces
Codeforces. Programming competitions and contests, programming community
展示评论