Codeforces Round #670 (Div. 2)A-C

Codeforces Round #670 (Div. 2)

A. Subset Mex

問題分析：

給你n個數字要求你 分成2組

然後按照 從1開始的自然序列 最先沒有出現的數字作為 規則值（mex（））

然後求 2組 規則值和 的最大值

要想 和最大，就盡量吧其中一組的mex() 調成最大的

統計–優先組成 第一組，，統計–，然後求出第一組最大的

然後第二組，，，

AC代碼：

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<sstream>
#include<algorithm>
using namespace std;
#define ll long long
#define mem(a,b) memset((a),(b),sizeof(a));
const ll inf=0x3f3f3f3f;//1061109567,2*未超int，allinf=mem(a,0x3f,sizeof(a));
const int N=2e5+10;
int a[105],b[105];
int main(){
       // #define io
#ifdef io
        freopen("in.txt","r",stdin);
#endif
        cin.tie(0);
        int t;
        cin>>t;
        while(t--){
                int n ;
                cin>>n;
                memset(a,0,sizeof(a));
                for(int i=0;i<n;i++){
                        int x;
                        cin>>x;
                        a[x]++;
                }
                int q,w;
                q=w=0;
                for(int i=0;i<101;i++){
                        if(a[i]){
                                a[i]--;
                        }else{
                                q=i;
                                break;
                        }
                }
                for(int i=0;i<101;i++){
                        if(a[i]){
                                a[i]--;
                        }else{
                                w=i;
                                break;
                        }
                }
                cout<<q+w<<endl;
        }
        return 0;
}
           

B. Maximum Product

問題分析：

給定五個數，求其乘積最大值

之前見過一個藍橋杯的題是 求k個數字

當時 是 k分奇偶性

1）當k為偶數時候 就是 先把數組排序 然後兩頭依次掃倆個比較大小

然後标記 反複這個操作，，

2）當K為奇數的 時候 最開始的時候直接取最大的數

因為不管 正數還是 負數 都一定要乘以這個最大的數。。。

然後進行偶數的操作

為啥每次取2個 因為 --得正，最小的2個負數的乘積emmm

具體看代碼

AC代碼：

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<sstream>
#include<algorithm>
using namespace std;
#define ll long long
#define mem(a,b) memset((a),(b),sizeof(a));
#define lowbit(a) ((a)&-(a))
const ll inf=0x3f3f3f3f;//1061109567,2*未超int，allinf=mem(a,0x3f,sizeof(a));
const int N=2e5+10;
ll a[100005];
ll sum;
int main(){
       // #define io
#ifdef io
        freopen("in.txt","r",stdin);
#endif
        cin.tie(0);
        int t;
cin>>t;
while(t--) {
 
int n;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
sort(a,a+n);
sum=a[n-1]*a[0]*a[1]*a[2]*a[3];
sum=max(sum,a[n-1]*a[0]*a[1]*a[n-2]*a[n-3]);
sum=max(sum,a[n-1]*a[n-2]*a[n-3]*a[n-4]*a[n-5]);
cout<<sum<<endl;
}
        return 0;
}
           

C. Link Cut Centroids

問題分析：

給定n，個幾點 ，以及n-1條邊

要求 删除一條邊 并增加一條邊 最終是重心唯一

其中 重心：樹中的某個節點，将其删除後，使得節點最多連通分量的節點數最少

重心的性質：一棵樹最多有兩個重心，2個的話一定重心相鄰

為什麼不能有三個重心呢

如果有三個 重心 呢麼根據性質隻能 成環但是呢就不是樹了

現在就是判斷 重心的個數，用dfs掃一下 ，當重心為2時

需要處理 假設其中重心為 x，y呢他們子樹節點個數一定是n/2

這是 将 y子樹的一個子節點 删掉 并加到x上

這樣 x的就成為 唯一的 重心

這是 x的 最大連通分量為 n/2+1

而 y的 為n/2-1

AC代碼：

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<sstream>
#include<algorithm>
using namespace std;
#define ll long long
#define mem(a,b) memset((a),(b),sizeof(a));
#define lowbit(a) ((a)&-(a))
const ll inf=0x3f3f3f3f;//1061109567,2*未超int，allinf=mem(a,0x3f,sizeof(a));
const int N=1e5+10;
vector<int> v[N];
int n,flag,xx,yy;
int s[N];
int dfs(int x,int y){
    s[x]=1;
    for(int i=0;i<v[x].size();i++){
        if(y!=v[x][i]){
            dfs(v[x][i],x);
            s[x]+=s[v[x][i]];
        }
    }
    if(s[x]==n/2){
        xx=x;
        yy=y;
        flag=1;
    }
    return 0;
}
int main(){
       // #define io
#ifdef io
        freopen("in.txt","r",stdin);
#endif
        cin.tie(0);
        int t;
        scanf("%d",&t);
        while(t--){
            scanf("%d",&n);
            flag=0;
            for(int i=0;i<N;i++){
                v[i].clear();
                s[i]=0;
            }
            int a,b;
            for(int i=1;i<n;i++){
                scanf("%d%d",&a,&b);
                v[a].push_back(b);
                v[b].push_back(a);
            }
            dfs(1,0);
            if(!flag){
                cout<<a<<" "<<b<<endl;
                cout<<a<<" "<<b<<endl;
            }else{
                for(int i=0;i<v[yy].size();i++){
                    if(v[yy][i]!=xx){
                        cout<<v[yy][i]<<" "<<yy<<endl;
                        cout<<v[yy][i]<<" "<<xx<<endl;
                        break;
                    }
                }
            }
        }
        return 0;
}