传送门

首先考虑怎样的集合一定是合法的

发现全部是奇数的集合一定合法,因为每次都是奇数连偶数,偶数连奇数

然后考虑如果集合同时有奇数和偶数是否一定不合法,结论是一定不合法,证明如下:

设某个奇数为 $2x+1$ ,某个偶数为 $2y$,那么 $0$ 到 $(2x+1)*(2y)$ 就有两种路线,$2x+1$ 步和 $2y$ 步的,

这两条路线刚好构成一个奇环,所以一定不是二分图

所以一种合法方案就是全留奇数,但是还不够,因为可能删掉一些奇数和偶数以后只剩下偶数也是合法的,比如 $2,6$ 就是合法的

发现如果只剩下偶数,那么我们可以把所有偶数同时除以 $2$,这样并不影响集合的性质,证明的话可以这样考虑:

所有数都是偶数的情况下,编号为偶数的点只会连向编号为偶数的点,奇数点也只能连奇数点,那么我们可以把这两种点分开来

然后重新按原编号大小编号为 $0,1,...$,其实就是偶数点的编号全部除以 $2$,奇数点的编号全部 $-1$ 再除以 $2$

发现这样新的两个图其实是一样的并且就是原集合的数都除以 $2$ 以后构成的图,所以证明完毕

然后除以二以后发现又有些奇数有些偶数了,继续递归地考虑即可

所以,可能的方案应该是这样的:

1. 全留奇数
2. 把1.奇数都扔了,然后全留/2后是奇数的数
3. 把1.2.的奇数都扔了,全留/4后是奇数的数
...

然后直接模拟即可,复杂度 $O(n \log 10^{18})$

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
inline ll read()
{
    ll x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
    return x*f;
}
const int N=2e5+7;
ll n,a[100][N],ans=-1,p;
int main()
{
    n=read();
    for(int i=1;i<=n;i++) a[0][i]=read();
    for(int i=0;i<100;i++)
    {
        ll res=0; bool flag=0;
        for(int j=1;j<=n;j++)
        {
            if(a[i][j]&1) res++;
            if(a[i][j]) flag=1;
        }
        if(!flag) break;
        if(res>ans) ans=res,p=i;
        for(int j=1;j<=n;j++)
        {
            if(a[i][j]&1) a[i+1][j]=0;
            else a[i+1][j]=a[i][j]>>1;
        }
    }
    printf("%lld\n",n-ans);
    for(int i=1;i<=n;i++)
        if((a[p][i]&1)==0) printf("%lld ",a[0][i]);
    if(n-ans) puts("");
    return 0;
}
02-01 10:47