由特殊情况推广到一般情况

原题链接

题意

  • 我们有一个含多个正整数的集合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;
}

版权声明:本文为int-me-X原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://www.cnblogs.com/int-me-X/p/14355947.html