Codeforces Round 942 (Div. 2)

Codeforces Round 942 (Div. 2)

A. Contest Proposal

题意：有n个题目，每个题目的难度为a[i]，要求每个题目的难度不大于对应的b[i]，每次可以添加一个题目并且删去最难的题目，求最多能添加几个题目

思路：暴力枚举即可，只要a[i]大于b[i]，就把a[n]改为b[i]，然后重新排序

void solve(){
    int n;
    cin >> n;
    vector<int> a(n + 1), b(n + 1);
    for(int i = 1; i <= n; i ++) cin >> a[i];
    for(int i = 1; i <= n; i ++) cin >> b[i];
    int ans = 0;
    while(1){
        bool ok = 1;
        for(int i = 1; i <= n; i ++){
            if(a[i] > b[i]){
                ans ++;
                a[n] = b[i];
                sort(a.begin() + 1, a.end());
                ok = 0;
            } 
        }
        if(ok) break;
    } 
    cout << ans << '\n';
}

B. Coin Games

题意：有n个硬币围成一圈，每次可以把朝上的硬币拿走并且翻转相邻的硬币，直到不能翻转硬币就输了

思路：看样例猜？奇数先手必胜，因为每次只能减少奇数个向上

void solve(){
    int n;
    string s;
    cin >> n >> s;
    int sum1 = 0;
    for(auto c : s){
        if(c == 'U') sum1 ++;
    }
    if(sum1 & 1) cout << "YES\n";
    else cout << "NO\n";
}

C. Permutation Counting

题意：开始对应i的牌有a[i]张，同时还有k张可以随意选择点数的空白牌，求把所有牌任意顺序排列后，这个序列中n的一个排列的子串数量的最大值

思路：先按照数量排序，大的在前，可以发现牌的点数顺序是无所谓的们只要n张不同的连在一起就是一个排列，然后二分能过组成的完整整套排列的数量，答案就是l * n - n + 1,最后把多出来的牌往后补，直到无法补，别忘了可能剩余的空白牌

这里要注意一下二分的上界，应该是a[i]+k，所以是2e12，如果太大会炸longlong

void solve(){
    int n, k, sum = 0;
    cin >> n >> k;
    vector<PII> a(n + 1);
    for(int i = 1; i <= n; i ++){
        int x;
        cin >> x;
        a[i] = {x, i};
        sum += x;    
    }
    sort(a.begin() + 1, a.end(), greater<PII>());
    
    auto check =[&](int mid) -> bool{
        int k1 = k;
        for(int i = 1; i <= n; i ++){
            if(a[i].first < mid){
                k1 -= mid - a[i].first;
            }
        }
        if(k1 >= 0) return true;
        else return false;
    };
    int l = 0, r = 2e12;
 
    while(l < r){
        int mid = l + r + 1 >> 1;
        if(check(mid)) l = mid;
        else r = mid - 1;
    }
    for(int i = 1; i <= n; i ++){
        if(a[i].first >= l) a[i].first -= l;
        else{
            k -= (l - a[i].first);
            a[i].first = 0;
        } 
    }
//    cout << l << '\n';
    int ans = l * n - n + 1;
    for(int i = 1; i <= n; i ++){
        if(a[i].first > 0) ans ++;
        else{
            if(k > 0){
                k --;
                ans ++;
            }
            else break;
        }
    }
    cout << ans << '\n';
}

D1. Reverse Card (Easy Version)

题意：给定n, m，求1<=a<=n,1<=b<=m，满足(a+b)能整除b*gcd(a, b)的数量

思路：设k为(a+b)/b*gcd(a, b)，则kb = (a+b)/gcd(a+b)，如果gcd(a, b)|(a+b)，则a是b的倍数，所以gcd(a, b)==b，则k*b*b = a+b，枚举k即可

void solve(){
    ll n, m;
    cin >> n >> m;
    ll ans = 0;
    for(int i = 1; i <= m; i ++){
        if(i * i - i > n) break;
        for(int j = 1; j; j ++){
            if(j * i * i - i > n) break;
            if(j * i * i - i > 0) ans ++;
        }
    }
    cout << ans << '\n';
}

D2. Reverse Card (Hard Version)

题意：如上，但是求满足b*gcd(a, b)能整除(a+b))的数量

思路：(a+b)|(b*gcd(a, b))，假设gcd(a, b)=d，则(pd+qd) | gd²,gcd(p, q)是1，因为两个数除以它们的gcd肯定互质

（a+b)|(b*gcd(a,b)) <==> (pd+qd)|(qd²) <==> (p+q)|(qd)

已知 gcd(p+q,q)=gcd(p,q)=1，所以(p+q)|d

又因为a=pd, b = qd，则a整除p，b整除q

二者要同时满足，取min即可

void solve(){
    ll n, m;
    cin >> n >> m;
    ll ans = 0;
    for(int i = 1; i <= n / i; i ++){
        for(int j = 1; j <= m / j; j ++){
            if(__gcd(i, j) == 1){
                ans += min(n / ((i + j) * i), m / ((i + j) * j));
            }
        }
    }
    cout << ans << '\n';
}