Codeforces 1220D 思维 数学 二分图基础
题意
-
我们有一个含多个正整数的集合B,然后我们将所有的整数,也就是Z集合内所有元素,都当做顶点
-
两个整数 \(i , j\) 能建立无向边,当且仅当 \(|i – j|\) 这个数属于B集合
-
要求我们从B中删去最少的数,来使得Z集合上建立的图为二分图
思路
-
首先要知道离散数学的基础知识,一个简单图是二分图,当且仅当其中没有奇环。
-
我们先假设B中只有一个数x,那么显然在Z中,0与x可以建边,然后x又可以和x * 2建边,以此类推。这是一条链
-
那么如果B中还有一个y呢,那显然还会生成一条链也就是 \(y * n(n \in N)\) 还会出现 \(nx + my\) 等,那环在哪呢,其实我们显然能知道的一个就是 \(0 – lcm(x, y) – 0\) : 0加上n个x之后到达\(lcm(x, y)\),然后减去m个y之后到达0.
-
1.我们可以发现,如果x,y一奇一偶的话,那么n和m必然一奇一偶,那么这个环就是奇环。所以,B中不能同时存在奇数与偶数
-
2.我们还能发现,如果x,y都是奇数,那么就不可能出现奇环,因为从一个奇数到达另一个奇数必然相差为偶数,而要凑够这个偶数,而且我们手里只有奇数,那就需要偶数个奇数,这样一来,环的长度只能是偶数
-
3.我们还能发现,如果把上面的 \(x,y\) 换成 \(nx,ny (n \in N)\),那么最终形成的图的形状是一样的。
-
前两个发现是很重要的,而第三个发现是将特殊情况扩展到一般情况的理论基础:
-
这样我们对于两个偶数x , y怎么判断有没有奇环?
-
我们不断地同时给x,y除以2,由发现3可知,操作后x,y形成的图形状不变。
-
那么最终x,y会变成“一奇一偶”或者”两个奇数“的情况,这样就可以判断了
-
这样我们就得到了性质4:x,y的质因子中,2的幂次相同的话,x,y就能变成”两个奇数“,不会形成奇环,反之则会
-
-
我们发现,性质4就是一般情况下的理论,囊括了对发现1 2 3的解释。我们可以马上根据性质4来写出代码,也就是计算B中每个数的2因子的幂次,分为m个集合,每个集合内元素的2因子的幂次相同,然后我们保留其中最大的那个集合,然后删除其他数字即可。
AC代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 200000;
int n;
long long bb[N + 5];
int col[N + 5] = {0};
vector<int> q2[105];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
{
scanf("%lld", &bb[i]);
}
int mx = 0, mi = 0;
for (int i = 1; i <= n; ++i)
{
long long p = bb[i];
while (p % 2 == 0)
{
++col[i];
p /= 2;
}
q2[col[i]].push_back(i);
}
for (int i = 0; i <= 64; ++i)
{
if (q2[i].size() > mx)
{
mx = q2[i].size();
mi = i;
}
}
printf("%d\n", n - mx);
for (int i = 1; i <= n; ++i)
{
if (col[i] != mi)
{
printf("%lld ", bb[i]);
}
}
return 0;
}