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

A. Gregor and Cryptography

题解

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

代码

Java

C++

B. Gregor and the Pawn Game

题解

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

代码

Java

C++

C. Web of Lies

题解

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

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

代码

Java

C++

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

C++