Codeforces 1220D. Alex and Julian

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

传送门

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

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

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

设某个奇数为 $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=,f=; char ch=getchar();

    while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }

    while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }

    return x*f;

}

const int N=2e5+;

ll n,a[][N],ans=-,p;

int main()

{

    n=read();

    for(int i=;i<=n;i++) a[][i]=read();

    for(int i=;i<;i++)

    {

        ll res=; bool flag=;

        for(int j=;j<=n;j++)

        {

            if(a[i][j]&) res++;

            if(a[i][j]) flag=;

        }

        if(!flag) break;

        if(res>ans) ans=res,p=i;

        for(int j=;j<=n;j++)

        {

            if(a[i][j]&) a[i+][j]=;

            else a[i+][j]=a[i][j]>>;

        }

    }

    printf("%lld\n",n-ans);

    for(int i=;i<=n;i++)

        if((a[p][i]&)==) printf("%lld ",a[][i]);

    if(n-ans) puts("");

    return ;

}