Codeforces Round #730 ABCD 题解 (Java/C++)

A. Exciting Bets

题解

如果两个数相同,那么显然答案是无穷大。

如果两个数不同,那么可以令两个数为a和a+x。在执行若干操作后,两个数分别为a+y和a+y+x。
设操作后的最大公约数为q。则有$a+y\equiv 0\pmod q$且$a+y+x\equiv 0\pmod q$。进而有$x\equiv 0\pmod q$。
于是有$q\leq x$。因为最坏的场景下两个数可以变成0和x。因此两个数不同的时候,最大公约数必为x。

于是我们只需要寻找a附近的x的倍数即可。

代码

Java

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

C++

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

B. Customising the Track

题解

显然,均分即可。假设均分的余数为x,于是n条路中有x条路多1辆车。因此最终结果为$x\cdot (n-x)$。

代码

Java

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

C++

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

C. Need for Pink Slips

题解

递归暴力模拟即可。虽然输入的概率可以有4位小数,但是由于v最小是0.1,因此最多有10层递归。

代码

Java

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

C++

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

D. RPD and Rap Sheet (Easy/Hard)

题解

首先我们发现,异或操作满足:若$a\oplus b=c$则$c\ominus a=b$。

假设初始密码为x。经历过若干查询之后,当前的密码其实是可以推导出来的。设第i次查询的内容为$q_i$,查询后的密码为$x_i$,则有$$\begin{equation*}
x\oplus x_1=q_1\\
x_1\oplus x_2=q_2\\
x_2\oplus x_3=q_3\\
...\\
\end{equation*}$$

于是我们可以从0开始依次枚举初始密码,根据我们假设的初始密码,推导出当前的密码,并且查询即可。
以第4次查询为例,我们假设的初始密码是3。则当前的密码是$q_3 \ominus q_2 \oplus q_1 \ominus 3$。
以第5次查询为例,我们假设的初始密码是4。则当前的密码是$q_4 \ominus q_3 \oplus q_2 \ominus q_1 \oplus 4$。

代码

Java

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

C++

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