首先我们可以发现权值一样的点可以互相无代价连接,因此可以看做一个点。
去重后找到一个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) 回帖