[题目链接](https://codeforces.com/contest/1946)

A. Median of an Array

题意

给出一个数组，每次操作可以让其中一个数增加一。 问最少需要几次操作能改变中位数的值。

长度为n的数组a的中位数表示为，令b是a排完序后的数组，那么 即为a的中位数。

思路

假设中位数为 ，那么我们就需要让最终的中位数变为 。做法就是对一些值为 各进行一次操作。我们假设小于等于m的数的数量为 , 起初一定有为了让是中位数，就必须 。 每次操作能使得cnt减少1 。于是我们需要的操作数量就是

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
void solve(){
    map<int,int> mp; //每个数都出现了几次
    int n;
    cin>>n;
    rep(i,1,n){
        int num;cin>>num;
        mp[num] ++;
    }
    int cnt = 0;
    for(auto p:mp){
        if(cnt+p.second < (n+1)/2){
            cnt += p.second;
        }
        else{//这时候找到了中位数，并且数量是cnt
            cout<<cnt + p.second - (n+1)/2 + 1<<endl;
            return;
        }

    }
}
signed main(){
    int T = 1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

B. Maximum Sum

题意

给出一个初始长度为的数组 。

对于每步操作，你可以选出其中一个子数组，将这个子数组的总和作为一个新项，插入到整个数组的任意位置。(可以选择空的子数组，这样就插入了一个0)

按照如上操作进行k次后， 问整个数组的总和最大是多少。

思路

首先介绍选取策略：我们选取总和最大的子数组（最大区间和）作为第一步操作。这样得到的第一个sum一定是最大的。接下来我们将sum放在这个子数组的末尾，下一次选取子数组时，我们就可以多加上新的那个数(如果新增的数小于0，那么肯定是不能加的，直接令子数组设置为空，sum就变为了0），依次类推共进行k次即可。

例如：

1
2
3 3
2 2 8

我们进行的三步操作为

1
2
3
4
5
6
7
2 2 8
## 选取[2 2 8]
2 2 8 12
## 选取[2 2 8 12]
2 2 8 12 24
## 选取[2 2 8 12 24]
2 2 8 12 24 48

可以发现，如果我们新增了一个sum在这个子数组之后，下一次就会是 ，也就是每次新增的都是上一次的两倍。最终整段子数组的数值总和即为 （表示最初子数组的总和，k表示操作次数），那么整个数组的总和就是 ，其中表示整个初始数组的总和。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
int mod = 1e9+7;
int qpow(int x,int n){ //快速幂
    int ans = 1;
    while(n){
        if(n&1) ans = ans * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return ans;
}
void solve(){
    int n,k;
    cin>>n>>k;
    vector<int> dp(n+5,-INF);//dp数组用来找最大区间和
    vector<int> num(n+5);
    int sum = 0;
    rep(i,1,n){//求整个数组的和
        cin>>num[i];
        sum += num[i];
    }
    rep(i,1,n){
        dp[i] = max(num[i],dp[i-1]+num[i]);
    }
    int mx = -INF;
    rep(i,0,n){
        mx = max(mx,dp[i]);
    }
    //此时的mx就是最大区间和,也就是sum0
    int ans = sum;//
    if(mx > 0) ans+=mx%mod*qpow(2,k)-mx;//这里记得要对mx取模再乘2的次幂
    cout<<(ans%mod+mod)%mod<<'\n';//记得取模

}
signed main(){
    int T = 1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

C. Tree Cutting

题意

给你一个树，让你删掉其中k条边，于是就得到了 个子树，现在问在进行完k次删边后，**这些子树的大小(即子树中节点的数量)的最小值x** ，最大可能是多少。

思路

最小的最大值（或者最大的最小值），一般情况都是二分答案。

check函数为: 使用dfs遍历整棵树，来检索最多能分成几棵子树，如果分出的子树数量大于等于 那么就是True，否则就是False

对于dfs函数，我们可以使用一个返回值来表示**当前节点下的子树能贡献多少个节点给祖先** 。

  • 如果当前收获的节点数大于等于x，那么就意味着当前这棵子树可以独立地构成一个合格的子树。于是我们切断他和父亲的边，让答案加一。并且return 0;
  • 如果当前收获的节点数小于x，那么就不能独立构成一个合格的子树，就需要将所有的节点都传递到父亲节点。也就是return cnt;

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
const int maxn = 1e5+5;
vector<int> ed[maxn];
int n,k;
vector<int> vis(maxn);
int ans;
int dfs(int now,int x){
    int sum = 1;
    vis[now] = 1;
    for(auto v : ed[now]){
        if(!vis[v]){
            vis[v] = 1;
            sum += dfs(v,x);
        }
    }
    if(sum >= x) {ans ++;return 0;}
    else return sum;
}
bool check(int x){
    //初始化一些变量为0
    ans = 0;
    rep(i,1,n) vis[i] = 0;
    //dfs求一下ans的值
    dfs(1,x);
    return ans>=(k+1);
}
void solve(){
    cin>>n>>k;
    rep(i,1,n) ed[i].clear();
    rep(i,1,n-1){
        int u,v;cin>>u>>v;
        ed[u].push_back(v);
        ed[v].push_back(u);
    }
    int l = 1,r = n;
    while(l<r){
        int mid = (l+r+1)/2;
        if(check(mid)) l = mid;
        else r = mid-1;
    }
    cout<<l<<endl;
    return ;
}
signed main(){
    int T = 1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

D. Birthday Gift

题意

给你一个长度为的数组,即 。 现在你需要将他们划分为一些部分，来使得 **每一部分的异或和** 全部**按位或** 起来后的答案 满足 。问你最多能划分多少部分。如果无解就输出undefined1$。

即找到k组undefinedl,r)l_i \le r_ir_i + 1 = l_{i+1}, l_1 = 1,r_k = n(a_{l_1} \oplus a_{l_1+1}\oplus … \oplus a_{r_1})|(a_{l_2} \oplus a_{l_2+1}\oplus … \oplus a_{r_2})|…|(a_{l_k} \oplus a_{l_k+1}\oplus … \oplus a_{r_k}) \le x $

问k最大是多少。

思路

我们用表示**a的前i项的异或和**。即 ，那么原式就变为了undefinedsum_{r_1}\oplus sum_{l_1-1}) | (sum_{r_2}\oplus sum_{l_2-1})|…|(sum_{r_k}\oplus sum_{l_k-1}) \le x sum_{r_1} | sum_{r_2}|…|sum_{r_k} \le x$ 。于是我们就把区间异或的或，变成了单点的或。

有一点需要注意的是， 是必选项。

于是我们考虑x的每一位，

  • 如果这一位是0， 那么就不做改变，直接看有多少个满足 。
  • 如果这一位是1，那么我们就可以将这一位置为0，然后将所有较小位置为1，我们设处理后的x为xx，那么有 ，我们可以看有多少个满足 。

因为是必选项，所以如果 不满足上述条件，那么这一整组应该直接跳过。

在所有的按位分组中，找到最大的分组数即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
void solve(){
    int n,x;
    cin>>n>>x;
    vector<int> vec(n+5);
    rep(i,1,n){
        cin>>vec[i];
        vec[i] ^= vec[i-1];
    }
    int ans = -1;
    rep(k,0,32){
        int xx = x;
        int cnt = 0;
        if((x>>k) & 1){
            xx -= 1<<k;
            xx |= ((1<<k)- 1);
        }
        if((vec[n] | xx) != xx) {continue;}
        rep(i,1,n){
            if((vec[i] | xx) == xx){
                cnt++;
                ans = max(ans,cnt);
            }
        }
    }
    if(ans) cout<<ans<<'\n';
    else cout<<-1<<'\n';
}   
signed main(){
    int T = 1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}