题解 CF1689E

dead_X · 2022-06-27 22:28:21 · 题解

思路

首先先把所有 0 变成 1。

然后我们发现答案不大于 2，一种具体方式如下：

• 考虑所有 \text{lowbit} 最高的数。

• 如果只有一个，将它 -1。

• 如果不止一个，随便找一个 +1，随便找一个 -1。

于是枚举所有一步操作的情况一一检验即可，时间复杂度 Soft O(n^2)，具体看实现。

代码

// Problem: E. ANDfinity
// Contest: Codeforces - Codeforces Round #798 (Div. 2)
// URL: https://codeforces.com/problemset/problem/1689/E
// Memory Limit: 256 MB
// Time Limit: 4000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//回家？我没有家可以回，我没有退路。
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
using namespace std;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
int a[2003],n,ans,x,s;
bool vis[2003];
int fa[2003];
void dfs(int x)
{
    vis[x]=1,++s;
    for(int i=1; i<=n; ++i) 
        if((a[i]&a[x])&&!vis[i])
            dfs(i);
    return ;
}
int L(int x){return x&(-x);}
int find(int x){return fa[x]==x?x:(fa[x]=find(fa[x]));}
bool chk()
{
    for(int i=1; i<=n; ++i) fa[i]=i;
    for(int s=1; s<=536870912; s<<=1)
    {
        int fir=n;
        for(int i=1; fir==n&&i<n; ++i) if(a[i]&s) fir=i;
        int A=find(fir);
        for(int i=fir+1; i<=n; ++i) if(a[i]&s) fa[find(i)]=A;
    }
    for(int i=2; i<=n; ++i) if(find(i)!=find(1)) return 0;
    return 1;
}
signed main()
{
    for(int T=read();T--;)
    {
        n=read(),ans=x=s=0;
        for(int i=1; i<=n; ++i) vis[i]=0;
        for(int i=1; i<=n; ++i)
            (!(a[i]=read()))&&(++ans,a[i]=1),
            x=max(x,L(a[i]));
        dfs(1);
        if(s==n) 
        {
            printf("%d\n",ans);
            for(int i=1; i<=n; ++i) printf("%d ",a[i]);
            puts("");
        }
        else
        {
            int ovo=1;
            for(int i=1; i<=n; ++i)
            {
                //check: --a[i]
                --a[i];
                if(chk()){ovo=0;break;}
                //check: ++a[i]
                ++a[i],++a[i];
                if(chk()){ovo=0;break;}
                --a[i];
            }
            if(!ovo)
            {
                printf("%d\n",ans+1);
                for(int i=1; i<=n; ++i) printf("%d ",a[i]);
                puts("");
                continue;
            }
            for(int i=1; i<=n; ++i) 
                if(L(a[i])==x)
                {
                    if(ovo) 
                        --a[i],ovo=0;
                    else
                    {
                        ++a[i];
                        break;
                    }
                }
            printf("%d\n",ans+2);
            for(int i=1; i<=n; ++i) printf("%d ",a[i]);
            puts("");
        }
    }
    return 0;
}