牛客寒假算法训练营2-建通道

题目描述

输入描述:

输出描述:

输出一行，一个整数表示答案。

示例1

输入

复制 2 1 2

2
1 2

输出

复制 1

1

说明

思路

　　　对于此题来说，抛去所有附加条件不管，是一个MST问题。

　　 然鹅对于这种数据范围，即使处理了重复的点再去建边跑KRUSKAL也是不科学的（将信将疑

　　 于是乎我们来思考别的解法。

　　 首先，毋庸置疑，肯定是去重，因为异或相同为0嘛，没有花费当然要连咯。

　　 其次，对于最小花费，只要全为奇数或偶数肯定是0嘛。

　　 说到这里肯定有很多小伙伴喷我，然鹅原题面就是这样的，后来经过和出题人一顿BBOX，他才把题面改了。。。

　　  

 　　　从此时起，一切就变了。lowbit的定义变成了最低非0位（一开始写的是最低位），所以我们开始找最低的那个1在哪。

　　  关于这个最低的非0位，需要满足一个条件，就是在这一位上，其他所有点的权值转化为二进制后的这一位，得异或出来一个1。

　　  怎样才能异或出来一个1呢，相信大家大一的时候上大计基课都学过异或的口诀，“相同为0，不同为1”，所以只要所有的点权值转化为二进制后，这一位有0又有1就好啦。

　　  如何找到这一位呢，我们从最基础的角度思考（因为我只会点基础），利用&1的操作就可以辣，所以我们只要当找不到一个位上有0又有1时（gay圈现状），就把权值右移1位，直到找到某一位上有0又有1为止。

　　  如果还有不太清楚的同学可以试试去掉注释，输出过程看看，手动写写就知道了。

CODE

#include <bits/stdc++.h>
#define dbg(x) cout << #x << "=" << x << endl

using namespace std;
typedef long long LL;
const int kmaxn = 3e5 + 7;

int a[kmaxn];
set <int> s[37];
int f[35][2];

template<class T>inline void read(T &res)
{
    char c;T flag=1;
    while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
    while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}

namespace _buff {
    const size_t BUFF = 1 << 19;
    char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
    char getc() {
        if (ib == ie) {
            ib = ibuf;
            ie = ibuf + fread(ibuf, 1, BUFF, stdin);
        }
        return ib == ie ? -1 : *ib++;
    }
}

int qread() {
    using namespace _buff;
    int ret = 0;
    bool pos = true;
    char c = getc();
    for (; (c < '0' || c > '9') && c != '-'; c = getc()) {
        assert(~c);
    }
    if (c == '-') {
        pos = false;
        c = getc();
    }
    for (; c >= '0' && c <= '9'; c = getc()) {
        ret = (ret << 3) + (ret << 1) + (c ^ 48);
    }
    return pos ? ret : -ret;
}

int main()
{
    int n;
    read(n);
    for(int i = 1; i <= n; ++i) {
       int x;
       read(x);
       s[0].insert(x);
       f[0][x&1]++;
    }
    /*
    printf("f[0][0]:%d f[0][1]:%d
",f[0][0],f[0][1]);
    int d = s[0].size();
    for(set<int> ::const_iterator p = s[0].cbegin(); p != s[0].cend(); ++p) {
        cout << *p <<endl;
    }
    */
    LL ans = 0;
    for(int i = 0; i <= 30; ++i) {
        if(f[i][0] && f[i][1]) {
            ans = (s[i].size()-1) * (1 << i);
            break;
        }
        for(auto it : s[i]) {
            s[i+1].insert(it >> 1);
            f[i+1][(it>>1)&1]++;
        }
        /*
        printf("f[%d][0]:%d f[%d][1]:%d
",i,f[i][0],i,f[i][1]);
        int d1 = s[i].size();
        for(set<int> ::const_iterator p = s[i].cbegin(); p != s[i].cend(); ++p) {
            cout << *p <<endl;
        }
        */
    }
    cout << ans << endl;
    return 0;
}