CF1220D Alex and Julian 题解

GreenDay · 2019-09-21 12:18:06 · 题解

说句闲话 : 因为蒟蒻题意理解错误，卡了一节自习课（逃

题目大意：

现有一个大小为n (1 \le n \le 2 * 10^5 )集合B , B里的元素 1 \le b_i \le 10^{18} 。对于任意 i , j \in Z （这两个数不一定在集合B里） ， 若 abs(i - j) \in B , 则整数i， j之间连一条无向边。

问：至少在B中删掉多少个元素 ， 才能使得连出的边构成一个二分图？输出最小值并构造一种方案

前置知识：二分图的判定

没奇环。。。。。

做法

考虑从0开始 ，lcm(a , b) (a , b \in B )$ 构成的环： 因为集合B中的两个点构成了奇数大小的环 ， 则有

即为

显然 ， 当且仅当a ， b中2的质因子数相等时 ， a ， b无法构成奇数环（这种情况下 \frac {a}{gcd(a , b) } 和 \frac {b}{gcd(a , b) } 都是奇数 ，否则二者必然一奇一偶 , 构成奇环)。

换句话说：保留的数，必然含有相同个数的2的质因子。

所以我们只需要把B集合元素按2进制下末尾0的个数分组，最后只保留某一个大小最大的组，其他的都删掉，就是最优化的。

code:

//没有头文件，防抄袭
int n;
vector<long long> group[60]; 

inline int calc(long long x)
{
    int res = 0;
    while(!(x & 1)) x >>= 1 , res ++;
    return res;
}

int main()
{
    cin >> n;
    for(int i = 1 ; i <= n ; i ++)
    {
        long long num ;
        cin >> num;
        group[calc(num)].push_back(num);
    }
    int save = 0;
    for(int i = 0 ; i < 60 ; i ++)
        if(group[i].size() > group[save].size())
            save = i;

    cout << n - group[save].size() << endl;
    for(int i = 0 ; i < 60 ; i ++)
    {
        if(i == save) continue;
        for(int j = 0 ; j < (int)group[i].size() ; j ++)
            cout << group[i][j] << ' ';
    }
}