首先考虑无解的情况，很明显 \(a_n\) 必须为 \(0\)，否则没有解，因为如果最后一位为 \(1\) 那么必须有 \(n\) 这个数存在于 \(b\) 序列中，而这种情况时不符合题意的。
然后考虑如何求解，先考虑一种比较特殊的情况，就是若干个 \(1\) 后面接着一个 \(0\)，这里假设 \(1\) 的数量有 \(k\) 个，这种情况很明显可以先插入 \(k\) 个位置为 \(0\)，然后再插入一个数 \(k\)，令前面 \(k\) 个 \(0\) 全部取反。
然后就是正解，通过上面的特殊的情况，我们可以从后往前扫，如果遇到了当前位为 \(0\) 且前一位也为 \(0\)，那么就输出 \(0\)，因为这时我们可以多加一个 \(0\) 且不会取反，注意到是从后往前扫，因此这个数最后会跑到相应的位置上去。如果遇到了当前位为 \(0\) 但前一位为 \(1\) 的情况，就是上面特殊的情况，我们可以继续往前扫，每遇到一个 \(1\) 就输出一个 \(0\)，最后在输出我们统计的 \(1\) 的数量。这样子就可以构造出合法的序列。
时间复杂度 \(O(n)\)。
#include <cstdio>
int t,n;
int a[100005];
int main() {
scanf("%d",&t);
while(t--) {
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d",&a[i]);
}
if(a[n]) {
printf("No\n");
continue;
}
printf("Yes\n");
int f=0;
for(int i=n;i>=1;i--) {
if(!a[i]&&!a[i-1]) printf("0 ");
else if(!a[i]) f=0;
else if(a[i]) {
f++;
printf("0 ");
if(!a[i-1]) printf("%d ",f);
}
}
printf("\n");
}
return 0;
}