Insert Zero and Invert Prefix

题面翻译

你有一个长度为 $n$ 的 01 序列 $a$，以及一个初始为空的序列 $b$。你接下来需要执行 $n$ 次操作，每次操作将会使序列 $b$ 的长度增加 $1$。

在第 $i$ 次操作，你需要选择一个在 $[0,i)$ 之间的整数 $p$。然后在第 $p$ 位之后插入一个数字 $0$，并翻转之前的所有数字。
即，设在第 $i$ 次操作前的 $b$ 为 $b_1,b_2,...,b_{i-1}$。在第 $i$ 次操作选择在 $[0,i)$ 之间的整数 $p$，并使 $b$ 变为 $\overline{b_1}, \overline{b_2}, \ldots, \overline{b_{p}}, 0, b_{p+1}, b_{p+2}, \ldots, b_{i-1}$。其中，$\overline{x}$ 表示二进制翻转操作，即 $\overline{0}=1,\overline{1}=0$。

对给定的数组 $a$，判断是否存在一组操作使得 $b$ 变为 $a$，若存在则输出方案。

多组数据。

题目描述

You have a sequence $ a_1, a_2, \ldots, a_n $ of length $ n $ , each element of which is either $ 0 $ or $ 1 $ , and a sequence $ b $ , which is initially empty.

You are going to perform $ n $ operations. On each of them you will increase the length of $ b $ by $ 1 $ .

On the $ i $ -th operation you choose an integer $ p $ between $ 0 $ and $ i-1 $ . You insert $ 0 $ in the sequence $ b $ on position $ p+1 $ (after the first $ p $ elements), and then you invert the first $ p $ elements of $ b $ .
More formally: let's denote the sequence $ b $ before the $ i $ -th ( $ 1 \le i \le n $ ) operation as $ b_1, b_2, \ldots, b_{i-1} $ . On the $ i $ -th operation you choose an integer $ p $ between $ 0 $ and $ i-1 $ and replace $ b $ with $ \overline{b_1}, \overline{b_2}, \ldots, \overline{b_{p}}, 0, b_{p+1}, b_{p+2}, \ldots, b_{i-1} $ . Here, $ \overline{x} $ denotes the binary inversion. Hence, $ \overline{0} = 1 $ and $ \overline{1} = 0 $ .

You can find examples of operations in the Notes section.

Determine if there exists a sequence of operations that makes $ b $ equal to $ a $ . If such sequence of operations exists, find it.

输入格式

Each test contains multiple test cases. The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases.

The first line of each test case contains one integer $ n $ ( $ 1 \le n \le 10^5 $ ) — the length of the sequence $ a $ .

The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 0 \le a_i \le 1 $ ) — the sequence $ a $ .

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ .

输出格式

For each test case:

output "NO", if it is impossible to make $ b $ equal to $ a $ using the given operations;
otherwise, output "YES" in the first line and $ n $ integers $ p_1, p_2, \ldots, p_n $ ( $ 0 \le p_i \le i-1 $ ) in the second line — the description of sequence of operations that makes $ b $ equal to $ a $ . Here, $ p_i $ should be the integer you choose on the $ i $ -th operation. If there are multiple solutions, you can output any of them.

样例 #1

样例输入 #1

4
5
1 1 0 0 0
1
1
3
0 1 1
6
1 0 0 1 1 0

样例输出 #1

YES
0 0 2 1 3
NO
NO
YES
0 1 0 2 4 2

分析

要我们输出每次插入的位置

我们只能插入0, 所以1一定是靠取反得来的.

把插入0的位置之前的所有数取反, 要得到1, 1的右边一定要有0, 否则不可能, 换句话说就是如果 $a[n]=1$, 肯定无解, 其他情况总能找到答案

那我们就来考虑构造方式, 取反会影响插入位置的左边的所有数, 那我们是不是要优先得到右边的1呢, 因为如果先得到了左边的1, 在去得到右边的1的时候, 肯定要在右边的位置插入, 而插入取反肯定会对已经得到的左边1造成影响

我们可以从右往左遍历, 把一段连续的0和连续的1当作一段来处理, 例如 111000 这样的当作一段, 如果是 001100, 那么最左边 00 是一段, 1100 是另一段, 我们从右往左遍历得到一些段, 然后我们优先处理靠右的段, 我们只需要在处理好的一段的最左边插入0, 就可以不影响已经构造好的段了

对于每一段而言, 我们得到的段肯定是一串连续1和一串连续0, 我们看在这一段中最右边的1出现在哪里, 然后我们就在这个位置右边记为 p 插入0即可, 所以我们完全可以一开始全插入在最左边插入, 然后最后一个0就插入在 p 就可以

不难看出, 总共的时间复杂度是 $O(n)$

代码

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
vector<int> v[N];	//放一段一段的1和0
int a[N];

int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	int t; cin >> t;
	while(t--)
	{
		int n; cin >> n;
		for(int i = 1; i <= n; i++)
			cin >> a[i];
		if(a[n])
		{
			cout << "No\n"; continue;
		}
		cout << "YES\n";
		int last = 0, idx = 0; //idx表示有几段
		for(int i = n; i > 0; i--)
		{
			if(last && !a[i])	//如果上一个是1但是这一个是0, 那说明进入了新的一段 
			{
				idx++; 
			}
			v[idx].push_back(a[i]);
			last = a[i];
		}
		vector<int> ans;
		for(int i = 0; i <= idx; i++)
		{
             //r是最右边的1的位置, 如果没有1那么说明全是0, 那插入就要在最左边插入, 刚好就是0
			int sz = v[i].size(), r = 0;	
            //因为是从右往左遍历塞入v, 所以还要翻转一下
			reverse(v[i].begin(), v[i].end());	
			for(int j = 0; j < sz - 1; j++)
			{
				if(v[i][j] && !v[i][j+1])
				{
					r = j + 1; break;	//找到这一段最右边的那个1的位置 
				}
			}
			//先放进去len-1个0, 插在开头位置 
			for(int j = 0; j < sz - 1; j++)
			{
				ans.push_back(0); 
			}
			ans.push_back(r);
		}
		for(auto &item : ans) cout << item << ' ';
		cout << endl;
		//多例清空 
		for (int i = 0; i <= idx; i++)
			v[i].clear();
	}
}

JZTXT

CF1839C