Codeforces Round 936 (Div. 2)

Codeforces Round 936 (Div. 2)

 A. Median of an Array

题意：给一串数字，每次操作可以将一个数字+1，求最少多少次操作使得数组中位数增加

思路：分奇偶讨论：

1：如果是奇数的话看中间的数字，如果中间的数字只出现过一次，那么次数就是1，否则看从中间位到右边最后出现这个数字的地方看这个数字一共出现了多少次

2：如果是偶数的话就需要考虑中间的两个数字，如果这两个数字不相等只需要一次操作，否则看从n/2出发到右边看这个数字出现了多少次

void solve(){
    ll n;
    cin >> n;
    vector<ll> a(n + 1);
    map<ll, ll> mp;
    for(int i = 1; i <= n; i ++) cin >> a[i], mp[a[i]] ++;
    sort(a.begin() + 1, a.end());
    if(n & 1){
        int ans = a[n / 2 + 1];
        if(mp[ans] == 1) cout << 1 << '\n';
        else{
            int res = 0;
            for(int i = n / 2 + 1; i <= n; i ++){
                if(a[i] == ans) res ++;
            }
            cout << res << '\n';
        } 
    }
    else{
        if(a[n / 2] != a[n / 2 + 1]){
            cout << 1 << '\n';
        }
        else{
            int res = 0;
            for(int i = n / 2; i <= n; i ++){
                if(a[i] == a[n / 2]) res ++;
            }
            cout << res << '\n';
        }
    }
}

B. Maximum Sum

题意：给定一个数组，每次可以选取任意数字之和再次加入数组（可以是0个数字，那么和就是0），求操作k次之和数组和的最大的可能

思路：求最大连续子数组，如何把这个子数组不断翻倍加入数组和

void solve(){
    ll n, k, ma = 0, sum = 0, sum2 = 0;
    cin >> n >> k;
    vector<ll> a(n + 1);
    for(int i = 1; i <= n; i ++) cin >> a[i], sum += a[i];
    for(int i = 1; i <= n; i ++){
        if(sum2 + a[i] > 0) sum2 += a[i];
        else sum2 = 0;
        ma = max(ma, sum2);
    }
    for(int i = 1; i <= k; i ++){
        sum = (sum + ma + Mod) % Mod;
        ma = (ma + ma + Mod) % Mod; 
    }
    cout << sum << '\n';
}

C. Tree Cutting

题意：给定一棵树，求删掉k条边之后的最大的最小连通块的大小

思路：二分答案，贪心的删边即可，最后要注意根节点所在的边的大小是不是大于等于mid，如果小于，那么删去的边数-1

vector<int> edge[N];
 
void solve(){
    int n, k;
    cin >> n >> k;
    for(int i = 1; i <= n; i ++) edge[i].clear();
    for(int i = 1; i < n; i ++){
        int u, v;
        cin >> u >> v;
        edge[u].push_back(v);
        edge[v].push_back(u); 
    }
    auto check =[&] (auto && check, int u, int fa, int x) -> PII{
        int num = 0, siz = 1;
        for(auto v : edge[u]){
            if(v == fa) continue;
            auto [rnum, rsiz] = check(check, v, u, x);
            num += rnum;
            siz += rsiz;
 
        }
        if(siz >= x){
            siz = 0;
            num ++;
        }        
        return pair(num, siz);
    };
    int l = 1, r = n;
    while(l < r){
        int mid = l + r + 1 >> 1;
        auto [num, siz] = check(check, 1, 0, mid);
        if(siz < mid) num --;
        if(num >= k) l = mid;
        else r = mid - 1;
    }
    cout << l << '\n';
}

D. Birthday Gift

题意：给定一个数组，将数组分为若干份，每一份内的数字进行异或操作，如何每一组再进行与操作，使得最后的结果小于等于x，求最多的组数

思路：定义res为每一组的异或的结果，首先先将res=x，贪心的选数字，如果选到的数字异或之后为x，这些数字就作为一组，然后从接下来的数字接着选，如果最后遗留的数字为0就可以。接着将res定义为x的每一位二进制位，舍去这一位，低位全部取1，例如10000->01111,然后按照同样的方法分组，只考虑高位，因为低位已经不影响了

void solve(){
    int n, x;
    cin >> n >> x;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i ++) cin >> a[i];
    int ans = -1;
    int res1 = 0, cnt1 = 0;
    for(int i = 1; i <= n; i ++){
        res1 ^= a[i];
        if((res1 | x) == x){
            res1 = 0;
            cnt1 ++;
        }
    }
    if(res1 == 0) ans = max(ans, cnt1);
    
    for(int i = 30; i >= 0; i --){
        int p = 1 << i;
        if(p & x){
            int num = (x - p) | (p - 1);
            int res = 0, cnt = 0;
            for(int i = 1; i <= n; i ++){
                res ^= a[i];
                if((res | num) == num){
                    cnt ++;
                    res = 0;
                }
            } 
            if(res == 0) ans = max(ans, cnt);
        }
    }
    cout << ans << '\n';
}