[数据结构与算法]Binary String To Subsequences（子序列问题）

传送门

思路

不能有两个1挨着 ，也不能有两个0挨着，用两个容器存子序列的最后一个元素是第几个子序列里的，每当遇到一个0 尝试把它放到一个以1结尾的子序列末尾去，如果不行，就单独的为它开辟一个新的子序列，遇到1也是如此

code

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int i,j,k,m,n,t;
	string a;
	std::ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>t;
	while(t--)
	{
		cin>>n;
		cin>>a;
		vector<int>ans(n);
		vector<int>pos,pos1;
		for(i=0;i<a.size();i++)
		{
			int p=pos.size()+pos1.size();
			if(a[i]=='0')
			{
				if(pos1.size()==0)//如果没有以1结尾的子序列
				{
					pos.push_back(p);//开一个新的以0结尾的子序列
				}
				else
				{
					p=pos1.back();//以1结尾的子序列的末尾元素属于第几个子序列
					pos1.pop_back();
					pos.push_back(p);
				}
			}
			else
			{
				if(pos.size()==0)
				{
					pos1.push_back(p);
				}
				else
				{
					p=pos.back();
					pos.pop_back();
					pos1.push_back(p);
				}
			}
			ans[i]=p;
		 }
		 cout<<pos.size()+pos1.size()<<endl;
		 for(auto it:ans)
		 cout<<it+1<<" ";
		 cout<<endl;
	}
 } 

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖