Codeforces Round #730 Div. 2

本文主要是介绍Codeforces Round #730 Div. 2，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

好！

A.Exciting Bets

给俩数，一步操作为让他们同时+1或者-1，问最少几步操作让他们最大公约数最大，且这个数是多少

注意到俩数差不变，最大公约数必定为两数之差，找到一个最小数让他们为该数的倍数即可，直接模一下 取加减的最小值

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include<map>
#include<vector>
#include<string>
#include<math.h>
#include<time.h>
#include<set>
using namespace std;
using ll = long long;
typedef pair<ll, ll> P;
ll T;
int main() {
    cin.sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> T;
    ll a, b;
    while (T--)
    {
        cin >> a >> b;
        if (b > a)swap(a, b);
        ll det = a - b;
        ll k = 0;
        if(det!=0)
         k = b % det;
        cout << det << ' ' << min(k, det - k)<<'\n';
    }
}

B.Customising the Track

给个数列a，为每个车道上车的数量，定义拥挤值是\(\sum\limits_{i=1}^{n} \sum\limits_{j=i+1}^{n} \lvert a_i-a_j\rvert\)然后可以随意移动每辆车，问拥挤值最小是多少

先把所有车辆平均分配，相同部分消了，最后就是0和1，随便排列都行，其实就是0的个数乘1的个数

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include<map>
#include<vector>
#include<string>
#include<math.h>
#include<time.h>
#include<set>
using namespace std;
using ll = long long;
typedef pair<ll, ll> P;
ll T;
ll n;
int main() {
    cin.sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> T;
    while (T--)
    {
        cin >> n;
        ll a;
        ll sum = 0;
        for (int i = 0; i < n; i++) {
            cin >> a;
            sum += a;
        }
        sum %= n;
        cout << sum * (n-sum) << '\n';

    }
}

C. Need for Pink Slips

给定c，m，p三种彩票和其初始的概率，以及一个波动系数v，如果抽中p游戏立刻结束

如果当轮抽中某个彩票，且其概率为a，如果a>v则a-=v，如果a<v则a归零

a减少的值会平均分配给剩余概率不为0的彩票中去

问游戏结束轮数的数学期望

写个深搜完事了。。。比赛犯懒题都没看

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include<map>
#include<vector>
#include<string>
#include<math.h>
#include<time.h>
#include<set>
using namespace std;
using ll = long long;
typedef pair<ll, ll> P;
ll T;
double v;
double check(double a) {
    if (a < 1e-7)return 0;
    else return a;
}
double solve(double c, double m, double p,double pre,ll n) {
    double res = 0;
    res += n * pre * p;
    double prec = c;
    double prem = m;
    if (c) {
        double cc = c, mm = m,pp=p,pree=pre;
        pree *= cc;
        cc -= v;
        cc = check(cc);
        if (mm) {
            mm += (prec - cc) / 2.0;
            pp += (prec - cc) / 2.0;
        }
        else pp += prec - cc;
        res += solve(cc, mm, pp, pree, n + 1);
    }
    if (m) {
        double cc = c, mm = m, pp = p, pree = pre;
        pree *= mm;
        mm -= v;
        mm = check(mm);
        if (cc) {
            cc += (prem - mm) / 2.0;
            pp += (prem - mm) / 2.0;
        }
        else pp += prem - mm;
        res += solve(cc, mm, pp, pree, n + 1);
    }
    return res;
}
int main() {
    cin.sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> T;
    while (T--)
    {
        double c, m, p;
        cin >> c >> m >> p>>v;
        double ans;
        ans = solve(c, m, p, 1, 1);
        printf("%.10f\n", ans); 
    }
}

D. RPD and Rap Sheet

定义一种新的k位异或：先把a和b变为k进制数，每位都变成（a+b）mod k

给一个数n 密码是0到n-1 的一个数， 有n次机会猜密码 但是猜错密码 密码改变

假设猜错时密码是x 猜的数为y 则密码变成z 且 x k异或 z = y

k是2的简单版本时 就是普通异或， 这时候有传递性 直接每次猜 i-1^i就完事了

k大于2时就没有这个性质

方法如下：

定义一种新的kxor 是(a-b)modK

答案猜错会变成y kxor x

然后又有(a kxor b)kxor(a kxor c)=c kxor b (b kxor a)kxor(c kxor a)=b kxor c

所以就有了新的传递性:

偶数 i kxor i-1

奇数 i-1 kxor i

然后答案会一路变成

x-> (0 kxor 1) kxor (0 kxor x)=x kxor 1 -> 2 kxor 1 kxor (x kxor 1)=2 kxor x ->2 kxor 3 kxor (2 kxor x)=x kxor 3.....

所以答案在i为偶数时是 x kxor i-1 奇数时是 i-1 kxor i

结果照着题解抄我都犯病了 啥时候能不忘记！ 和 &的优先级啊

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include<map>
#include<vector>
#include<string>
#include<math.h>
#include<time.h>
#include<set>
using namespace std;
using ll = long long;
typedef pair<ll, ll> P;
ll T;
ll n;
ll k;
ll check(ll a) {
    ll tmp;
    cout << a << endl;
    cin >> tmp;
    return tmp;
}
ll kxor(ll a, ll b) {
    ll res = 0;
    ll p = 1;
    while (a>0||b>0)
    {
        ll m = a % k;
        ll n = b % k;
        a /= k;
        b /= k;
        ll tmp = (m - n + k) % k;
        res = res+tmp * p;
        p = p * k;
    }
    return res;
}
int main() {
    cin.sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> T;
    while (T--)
    {
        cin >> n >> k;
        for (int i = 0; i < n; i++) {
            ll flag = 0;
            if (i == 0)flag = check(0);
            else if (!(i &1))flag = check(kxor(i, i - 1));
            else flag = check(kxor(i - 1, i));
            if (flag)break;
        }
    }
}

这篇关于Codeforces Round #730 Div. 2的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！