Codeforces Round #730 (div 2)

 

第一次div2做了三题，好耶

CF Round #730

A Exciting Bets (1543A)

思维题+数学题+签到题

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

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

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

代码如下：

#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 (草

代码如下：

#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 的时候就已经得到了正确结果。

代码如下：

#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;
        }

    }
    
}

 

综上，这波捡了个大便宜（逃