Codeforces Round 730 (div 2)

Codeforces Round #730 (div 2)

 

第一次div2做了三题,好耶

CF Round #730

A Exciting Bets (1543A)

思维题+数学题+签到题

题意大致是:给两个数,可以同增 1 或者同减 1 任意次(也可以不操作),求所能得到的变化后的两个数的最大公约数,以及到达这个结果所进行的“操作”的最小次数。

公约数肯定也是两者差的公约数,所以显然操作后取得的最大公约数就是二者之差。

最少操作次数 x ,满足 $(a + x)%{gcd} = 0$或者$(a - x)%{gcd} = 0$。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;


int main()
{
int t;
cin >> t;
while (t--) {
long long a, b, ans, ant;
cin >> a >> b;
//cout << a << b;
ans = a - b;
if (ans < 0) ans = 0 - ans;
if (ans != 0)ant = b % ans;
else ant = 0;
if ( ans - ant < ant) ant = ans - ant;
cout << ans << " " << ant << endl;
}

}

 

B Customising the Track (1543B)

数学题,甚至不要思维(x

题意就是将所有的数取整数的平均值(就是调配之后最大值和最小值相差不超过 1 );然后算就完事。注意开 long long (草

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;


int main()
{
long long t;
cin >> t;
while (t--) {
long long n;
cin >> n;
long long a = 0;
for (long long i = 0; i < n; i++) {
long long temp;
cin >> temp;
a += temp;
}
long long ans = a % n;
cout << ans * (n - ans) << endl;
}

}

 

C Need for Pink Slips (1543C)

泻药,题没看懂,英语太菜了(淦

据朋友说是 dp,先挖个坑在这里,补了再来写题解。

//

 

D1 RPD and Rap Sheet (Easy Version) (1543D1)

交互题!第一次做!

好题!                                        (算是一道数学题

总之就是做出来之后非常爽

观察到允许判断 n 次时,答案范围在 $0\leq ans < n$ 间,故想到“从零开始一个一个试密码(过于草率的决定)”

因为在试密码的过程中,密码会变化,因此要先去掉这个变化,再测试;因为两次异或同一个数,结果不变,所以只需要再异或一次上一次试的密码就能去掉“这个变化”。

举个例子:

假设 n = 3,密码是 2

那么先试 0

密码变成了 2 ^ 0

不对,再试 1

要消除 0 的影响(虽然0没有影响),我们先异或 0,再试 1

密码变成了 2 ^ 0 ^ 0 ^ 1 $\rightarrow$ 2 ^ 1

不对,再试 2

要消除 1 的影响,先异或 1,再试 2

这一步可以看到 2 ^ 1 在异或 1 之后,恢复成了原密码 2;然后再异或 2 ,变成了 0 。

实际上当密码变成 0 的时候就已经得到了正确结果。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
using namespace std;


int main()
{
long long t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;

for (int i = 0; i < n; i++) {
if(i == 0)cout << 0 << endl;
else cout << (i ^ (i - 1)) << endl;

int x;
cin >> x;
if(x) break;
}

}

}

 

综上,这波捡了个大便宜(逃