CF1220D 【Alex and Julian】

发表于 | 更新于 | 分类于 ，

$\Large\mathcal{Description}$

给定一个正整数集合$B$。

让所有整数都为一张无向图中的顶点。$i, j$之间有边，当且仅当$\left| i - j\right| \in B$。

现在要从B中删去最少的元素，使得这张无向图变成二分图。

$\Large\mathcal{Solution}$

首先，根据二分图的性质可知，判断这张图是不是二分图，只需判断是否存在奇环

我们先考虑只有两个数的情况

则若存在奇环，当且仅当存在正整数$a,b$, 使得 $ax = by$ 且 $(a + b) \bmod 2 = 1$。即

于是就可以开始快乐地分类讨论了。

  • $x, y$ 都为奇数。那么 $\operatorname{lcm}(x, y)$ 肯定是奇数，所以不满足。
  • $x, y$ 为一奇一偶。那么 $\operatorname{lcm}(x, y)$ 为偶数，所以满足。
  • $x, y$ 都为偶数。可以转化为前面两种情况。

然后，归纳一下就可以得到$:$

​ 这张图为二分图，即不存在奇环，当且仅当集合B中所有数在二进制下末尾有相同位数的零

拓展到多个数

假设我们现在找含 $i$ 种单位长度的奇环(即用集合B中 $i$ 个数)，且不存在含 $i$ 种以下单位长度的奇环。

即 $a_1x_1 + a_2x_2 + a_3x_3 + … a_{i-1}x_{i-1} = 0$ 且 $(a_1+a_2+a_3+…a_{i-1}) \bmod 2 = 0$

现在我们在这个式子中加入 $x_i$。

根据假设，我们还可以得到 $A_1x_1 + B_1x_i = 0, A_2x_2 + B_2x_i = 0 … A_{i - 1}x_{i-1} + B_{i-1}x_i = 0$ 且 $(A_j + B_j) \bmod 2 = 0$

将这些式子中的一些加入到原式中，均可实现在环中加入 $x_i$ 这个长度，但 $a$ 之和始终为偶数。

因此，我们只需要判断两个数的情况就行了

$\Large\mathcal{Code}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <cstdio>
#include <algorithm>

#define int long long

template <typename Tp>
inline void read(Tp &x) {
    x = 0;
    bool f = true; char ch = getchar();
    for ( ; ch < '0' || ch > '9'; ch = getchar()) f ^= ch == '-';
    for ( ; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + (ch ^ 48);
    x = f ? x : -x;
}

const int M = 105, N = 2e5 + 7;

int tot[N], a[N], c[M];

signed main() {
    int n;
    read(n);
    int maxx = 0, pos = 0;
    for (int i = 1; i <= n; ++i) {
        read(a[i]);
        int x = a[i], cnt = 0;
        for ( ; !(x & 1); x >>= 1, ++cnt);
        tot[i] = cnt;
        ++c[cnt];
        if (c[cnt] > maxx) maxx = c[cnt], pos = cnt;
    }
    printf("%lld\n", n - maxx);
    for (int i = 1; i <= n; ++i) if (tot[i] != pos) printf("%lld ", a[i]);
    return 0;
}