CodeForces - 1220D Alex and Julian 二分图性质

题目链接：https://vjudge.net/problem/CodeForces-1220D

题意：n个数，如果节点 i 和 j 满足 |i - j | 属于B，则i和j有一条边，问B集合最少删除多少边，使得得到的图是个二分图

题解：根据二分图的性质，不能存在奇数环，也就是和a不能共存的数有，a*2,a*4......，假设a和b能共存，那么a和b的2的幂数是一样的，也就是2的因子数目一样。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200100;
ll a[N];
int num[N];
int sum[N];
int n;
int main() {
ll x, y;
int cnt;
int maxx = 0, id;
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%lld", &x);
a[i] = x;
cnt = 0;
while(x % 2 == 0) {
cnt++;
x = x / 2;
}
num[i] = cnt;
sum[cnt]++;
if(sum[cnt] > maxx) {
maxx = sum[cnt];
id = cnt;
}
}
printf("%dn", n - maxx);
for(int i = 1; i <= n; i++)
if(num[i] != id)
printf("%lld ", a[i]);
return 0;
} 

最后

以上就是安静身影为你收集整理的CodeForces - 1220D Alex and Julian 二分图性质的全部内容，希望文章能够帮你解决CodeForces - 1220D Alex and Julian 二分图性质所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。