竞赛讨论区 > 2020牛客寒假算法基础集训营2 I题题解
头像
Ximilu
发布于 2020-02-07 17:53
+ 关注

2020牛客寒假算法基础集训营2 I题题解

首先我们可以发现权值一样的点可以互相无代价连接,因此可以看做一个点。
去重后找到一个lowbit最小的点,设此点lowbit为min,设有m个点的lowbit==min,当m<n时不难发现只需要让m外的点和m内的点相连即是最小,若m==n,则说明所有点的最低位都相同,只需要让所有点右移一位即可。注意所有点==0时特判。
#include<bits/stdc++.h>
#include <hash_map>
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl '\n'
#define for1(I, A, B) for (int I = (A); I < (B); ++I)
#define forn(I, A, B) for (int I = (A); I <= (B); ++I)
#define Mod(a,b) a<b?a:a%b+b
#define rep(ii,a,b) for(int ii=a;ii<=b;++ii)
#define show(x) cout<<#x<<"="<<x<<endl
#define showa(a,b) cout<<#a<<'['<<b<<"]="<<a[b]<<endl
#define show2(x,y) cout<<#x<<"="<<x<<" "<<#y<<"="<<y<<endl
#define show3(x,y,z) cout<<#x<<"="<<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<endl
#define show4(w,x,y,z) cout<<#w<<"="<<w<<" "<<#x<<"="<<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<endl
#define show5(v,w,x,y,z) cout<<#v<<"="<<v<<" "<<#w<<"="<<w<<" "<<#x<<"="<<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<endl
#define showmm(x,a,b) rep(i,0,a) rep(j,0,b) cout<<#x<<'['<<i<<']'<<'['<<j<<"]="<<x[i][j]<<(" \n"[j==b])
#define showm(x,a,b) rep(i,0,a) rep(j,0,b) cout<<x[i][j]<<(" \n"[j==b])
#define showa1(x,a,b) cout<<#x<<":\n";rep(i,a,b) showa(x,i);cout<<endl
#define showa2(x,a,b) cout<<#x<<": ";rep(i,a,b) cout<<x[i]<<' ';cout<<endl
#define pb emplace_back
using namespace std;
using namespace __gnu_cxx;
typedef long long ll;
typedef vector<int> vi;
typedef set<int> si;
typedef double db;
const db eps=1e-8;
const db pi=acos(-1);
const ll inf=0x3f3f3f3f3f3f3f3f;
const ll inf2=8e18+5;
const int INF=0x3f3f3f3f;
const int INF2=2e9+5;
const int MAX=2e5+10;
const ll mod2=1e9+7;
const ll mod=998244353;
const ll p=116195171;
vector<ll> A;
map<ll,int> mp;
int main()
{
    int n;
    cin>>n;
    forn(i,1,n)
    {
        ll x;
        cin>>x;
        if(!mp[x])
            A.pb(x);
        mp[x]=1;
    }
    ll mi=inf;
    ll sum=A.size();
    ll xx=1;
    while(sum==A.size())
    {
        mi=inf;
        sum=0;
        for(auto now:A)
        {
            ll x=now/xx;
            if(x==0)
            {
                continue;
            }
            int t=1;
            while(x%2==0)
            {
                t*=2;
                x/=2;
            }
            if(t<mi)
            {
                mi=t;
                sum=1;
            }
            else if(t==mi)
            {
                sum++;
            }
        }
        if(mi==inf)return cout<<0<<endl,0;
        xx*=2;
    }
        cout<<xx/2*mi*((A.size()-1)*1ll)<<endl;
}



全部评论

(1) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐