A. Subset Mex

题目大意:

给你一个长度为n的数组a，你需要将其分成两个数组，使得其中未出现的最小非负整数的和最大

思路:

首先第一个数必然是在数组a中就未出现的最下非负整数，这将使得在该数之前的所有数减1，然后再从0到max走一遍找到缺少的值即可

AC Code:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
// #define TDS_ACM_LOCAL
const int N=2e5 +9;
int len, vis[N], x;
void solve(){
    cin>>len;
    memset(vis, 0, sizeof(vis));
    int mx=0;
    for(int i=1; i<=len; i++){
        cin>>x;
        vis[x]++;
        if(x>mx)    mx=x;
    }
    int ans=0;
    for(int i=0; i<=mx+1; i++)
        if(vis[i]==0)   {ans+=i; break;}

    for(int i=0; i<=mx+1; i++)
        if(vis[i]<=1)  {ans+=i; break;}

    cout<<ans<<endl;
    return ;
}   

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int T;
    cin>>T;
    while(T--)  solve();
    return 0;
}

B. Maximum Product（枚举）

题目大意:

给你n个数，从中取出五个数使得其乘积最大

思路:

直接暴力枚举取的正数的个数，相应的获得负数的个数，乘积取最大即可

AC Code:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f3f3f
#define int long long
// #define TDS_ACM_LOCAL
const int N=2e5 +9;
int n, z[N], f[N];
bool cmp(int x, int y){
    return x>y;
}
void solve(){
    cin>>n;

    for(int i=1; i<=n; i++){
        cin>>z[i];
        f[i]=z[i];
    }

    sort(z+1, z+1+n);
    sort(f+1, f+1+n, cmp);
    int ans=-1e18;
    for(int i=0; i<=5; i++){
        int j=5-i;
        int tmp=1;
        for(int k=1; k<=i; k++) tmp*=z[k];
        for(int k=1; k<=j; k++) tmp*=f[k];
        ans=max(ans, tmp);
    }
    cout<<ans<<endl;
    return ;
}   

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int T;
    cin>>T;
    while(T--)  solve();
    return 0;
}

C. Link Cut Centroids（树重心）

题目大意:

给你一棵树的结点数n和n-1条边，你可以删除一条边再增加一条边，使得树的重心唯一
重心部分性质：
1、树中所有点到某个点的距离和中，到重心的距离和是最小的，如果有两个重心，他们的距离和一样。
2、把两棵树通过一条边相连，新的树的重心在原来两棵树重心的连线上。
3、一棵树添加或者删除一个节点，树的重心最多只移动一条边的位置。
4、一棵树最多有两个重心，且相邻。

思路:

当重心只有一个时，只需要找到任意一条连接到它的边，删除再添加即可
若有两个重心，则在一个重心上找到任意一个连接的非重心的点，将其边删除，加到另外一个重心即可
对于重心的找法：
用siz记录子节点个数，son记录删除该点后最大连通分量的子树的节点个数

AC Code:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
#define debug(a) cout<<#a<<"="<<a<<endl;
// #define TDS_ACM_LOCAL
const int N=1e5 +9;
int n;
int siz[N], son[N];
int r1, r2, r3;
vector<int> g[N];

void dfs(int u, int fa){
    siz[u]=1, son[u]=0;
    for(auto v:g[u]){
        if(v!=fa){
            dfs(v,u);
            siz[u]+=siz[v];
            son[u]=max(son[u],siz[v]);
        }
    }
    son[u]=max(son[u],n-siz[u]);
    if(son[u]*2 <= n)   r2=r1, r1=u;
    return ;
}

void solve(){
    cin>>n;
    for(int i=1; i<=n; i++) g[i].clear(), siz[i]=son[i]=0;
    int u, v;
    for(int i=1; i<=n-1; i++){
        cin>>u>>v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    r3=r1=r2=0;
    dfs(1,0);
    if(!r2){
        r3=g[r1][0];
        cout<<r1<<" "<<r3<<endl;
        cout<<r1<<" "<<r3<<endl;
        return ;
    }
    for(auto r3:g[r1]){
        if(r3!=r2){
            cout<<r3<<" "<<r1<<endl;
            cout<<r3<<" "<<r2<<endl;
            break;
        }
    }
    return ;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int T;
    cin>>T;
    while(T--)  solve();
    return 0;
}