现给出构造：
定义
l
o
w
b
i
t
(
x
)
lowbit(x)
lowbit(x) 为
x
x
x 二进制最低位
1
1
1 与后面的
0
0
0 所组成的数。
首先，把所有的
0
0
0 改成
1
1
1 。
令
m
x
mx
mx 为
max
i
=
1
n
l
o
w
b
i
t
(
a
i
)
max_{i=1}^{n}{lowbit(a_i)}
maxi=1nlowbit(ai) 。
若
a
a
a 中仅存在一个数
x
x
x 使得
l
o
w
b
i
t
(
x
)
=
m
x
lowbit(x) = mx
lowbit(x)=mx ，则将
x
x
x 更改为
x
−
1
x - 1
x−1 ，
x
−
1
x - 1
x−1 的二进制最低
log
2
l
o
w
b
i
t
(
x
)
log_2{lowbit(x)}
log2lowbit(x) 位均为
1
1
1 ，此时由于其他数的
l
o
w
b
i
t
lowbit
lowbit 取值均小于
x
x
x ，因此，
x
−
1
x - 1
x−1 和其他节点均有连边。
若
a
a
a 中存在至少两个数
x
,
y
x,y
x,y 使得
l
o
w
b
i
t
(
x
)
,
l
o
w
b
i
t
(
y
)
=
m
x
lowbit(x),lowbit(y) = mx
lowbit(x),lowbit(y)=mx ，将
x
x
x 变为
x
−
1
x - 1
x−1 ，
y
y
y 变为
y
+
1
y + 1
y+1 ，此时显然
y
+
1
y + 1
y+1 与其他
l
o
w
b
i
t
(
t
)
=
m
x
lowbit(t) = mx
lowbit(t)=mx 的
t
t
t 有连边，
x
−
1
x - 1
x−1 与 所有
l
o
w
b
i
t
(
s
)
<
m
x
lowbit(s) < mx
lowbit(s)
#include#include #define MAXN 3005 using namespace std; #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") char buf[1<<21],*p1,*p2,ch; #define getc() p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++; template inline void read(T & s){ s=0; char ch=getc(); bool f=false; while(!std :: isdigit(ch)) (ch=='-'?f=true:0),ch=getc(); while(std :: isdigit(ch)) s=(s<<3)+(s<<1)+(ch^48),ch=getc(); (f?s=-s:0); } template inline void write(T x){ if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10+48); } int n,a[MAXN]; int fa[MAXN]; int Find(int x) { return x==fa[x]?x:fa[x]=Find(fa[x]); } void merge(int x,int y){ x=Find(x); y=Find(y); fa[x]=y; } bool vis[MAXN]; vector edge[MAXN]; void dfs(int x){ if(vis[x]) return; vis[x]=true; for(int i : edge[x]) dfs(i); } bool checkinit(){ for(int i=1;i<=n;i++) vis[i]=false,edge[i].clear(),fa[i]=i; for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){ if(a[i]&a[j]){ if(Find(i)==Find(j)) continue; merge(i,j); edge[i].push_back(j); edge[j].push_back(i); } } } dfs(1); for(int i=1;i<=n;i++) if(!vis[i]) return false; return true; } int lowbit(int x) { return x&(-x); } bool check(int x){ for(int i=1;i<=n;i++) vis[i]=false; vis[x]=true; for(int i=1;i<=n;i++) if(a[x]&a[i]) dfs(i); for(int i=1;i<=n;i++) if(!vis[i]) return false; return true; } void solve(){ read(n); int ans=0; for(int i=1;i<=n;i++) read(a[i]); for(int i=1;i<=n;i++) if(!a[i]) ans+=++a[i]; if(checkinit()){ write(ans); putchar('n'); for(int i=1;i<=n;i++) write(a[i]),putchar(" n"[i==n]); return; } for(int i=1;i<=n;i++){ a[i]--; if(check(i)){ write(ans+1); putchar('n'); for(int i=1;i<=n;i++) write(a[i]),putchar(" n"[i==n]); return; } a[i]++; } for(int i=1;i<=n;i++){ a[i]++; if(check(i)){ write(ans+1); putchar('n'); for(int i=1;i<=n;i++) write(a[i]),putchar(" n"[i==n]); return; } a[i]--; } int tmp=0; for(int i=1;i<=n;i++) tmp=max(tmp,lowbit(a[i])); for(int i=1;i<=n;i++){ if(lowbit(a[i])==tmp){ a[i]--; break; } } for(int i=n;i>=1;i--){ if(lowbit(a[i])==tmp){ a[i]++; break; } } write(ans+2); putchar('n'); for(int i=1;i<=n;i++) write(a[i]),putchar(" n"[i==n]); } int main(){ int T; read(T); while(T--) solve(); return 0; }
