A

分析

分出两个集合要求 。考虑直接贪心选到不能再选，因为每个数的对答案的贡献都是 ，不错的签到题。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 4e5+100,inf = 0x3f3f3f3f;
int read() {int x;scanf("%d",&x);return x;}
int cnt[N],n,m;
int main()
{
    int T = read();
    while(T--) {
        n = read();
        int ans1 = 0,ans2 = 0;
        memset(cnt,0,sizeof(cnt));
        for(int i = 1;i <= n;i++) {
            int x = read();cnt[x]++;
        }
        while(cnt[ans1]) cnt[ans1]--,ans1++;
        while(cnt[ans2]) cnt[ans2]--,ans2++;
        printf("%d\n",ans1+ans2);
    }
}

B

分析

选出五个数使 。由小到大排序，那么答案一定是一个前缀积乘上一个后缀积。

#include<bits/stdc++.h>
using namespace std;
const int N = 4e5+100,inf = 0x3f3f3f3f;
#define LL long long
LL read() {LL x;scanf("%lld",&x);return x;}
LL a[N],n,m;
int main()
{
    int T = read();
    while(T--) {
        n = read();LL ans = -0x3f3f3f3f3f3f3f3f;
        for(int i = 1;i <= n;i++) a[i] = read();
        sort(a+1,a+1+n);
        for(int i = 0;i <= 5;i++) {
            LL res1 = 1,res2 = 1;
            for(int j = 1;j <= i;j++) res1 *= a[j];
            for(int j = n;j >= n-(5-i)+1;j--) res2 *= a[j];
            ans = max(ans,res1*res2);
        }
        cout << ans << endl;
    }
}

C

分析

分类讨论。如果只有一个重心，随便断一条边再连回去。如果有两个重心。因为我们知道如果一棵树有两个重心那么这两个重心一定被一条边链接着。考虑先把一个重心中的叶子断掉，再接到另一个重心上。这样就只有一个重心了。考虑正确性。证明：很容易看到，的子树必须正好 。切割和链接后，一个重心的最大子树为成为 而另一个的最大子树仍然是 。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 199;
vector<int> G[N];
bool vis[N];
int read(){int x;scanf("%d",&x);return x;}
int Max,rt[4],n,si[N],mx[N],fa[N],top,leaf;
void dfs1(int x,int F) {
    si[x] = 1;fa[x] = F;for(auto y:G[x]) {
        if(y == fa[x]) continue;
        dfs1(y,x);si[x] += si[y];
        mx[x] = max(si[y],mx[x]);
    }
}
void dfs2(int x) {
    mx[x] = max(si[1] - si[x],mx[x]);
    if(mx[x] < Max) {top = 1;rt[top] = x;Max = mx[x];}
    else if(mx[x] == Max) {rt[++top] = x;}
    for(auto y:G[x]) {if(y^fa[x])dfs2(y);}
}

void solve(int x,int F) {
    int tot = 0;fa[x] = F;
    if(vis[x]) return;
    vis[x] = 1;
    for(auto y:G[x]) {
        if(!vis[y])tot++;
        solve(y,x);
    } 
    if(tot == 0) leaf = x;
}
int main()
{
    int T = read();
    while(T--) {
        Max = 0x3f3f3f3f;top = 0;
        memset(vis,0,sizeof(vis));memset(mx,0,sizeof(mx));
        n = read();
        for(int i = 1;i <= n;i++) G[i].clear();
        for(int i = 1;i < n;i++) {
            int a = read(),b = read();
            G[a].push_back(b);G[b].push_back(a);
        }
        dfs1(1,0);
        dfs2(1);
        if(top == 1) printf("1 %d\n1 %d\n",G[1][0],G[1][0]);
        else {
            int x = rt[1],y = rt[2];
            if(fa[x] == y) {
                vis[y] = 1;solve(x,0);    
                printf("%d %d\n%d %d\n",leaf,fa[leaf],leaf,y);
            }
            else {
                vis[x] = 1;solve(y,0);
                printf("%d %d\n%d %d\n",leaf,fa[leaf],leaf,x);
            }

        }
    }    
}

D

分析

非常好的一道题。考虑 不升， 不降。所以答案为 。考虑钦定 。那么为了让 更小。当 时， 。其它时候一定可以保证 是不降的。令 。那么 。所以 时是最优的。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 100;
#define LL long long
LL read() {LL x;scanf("%lld",&x);return x;}
LL a[N],n,sum;
LL Q() {return ceil(((double)a[1] + sum)/2);}
void work(LL i,LL x) {
    if(a[i] > 0) sum -= a[i];
    a[i] += x;
    if(a[i] > 0) sum += a[i];
}
int main()
{
    n = read();
    for(int i = 1;i <= n;i++) a[i] = read();
    for(int i = 2;i <= n;i++) {
        if(a[i] > a[i-1]) sum += a[i] - a[i-1];
    }
    for(int i = n;i >= 1;i--) a[i] -= a[i-1];
    printf("%lld\n",Q());
    int m = read();
    while(m--) {
        int l = read(),r = read(),x = read();
        if(l==1) a[1] += x;
        else work(l,x);
        if(r != n) work(r+1,-x);
        printf("%lld\n",Q()); 
    }
}

E

因为 E 题是要交互的，先放着。