https://codeforces.com/contest/1399/problem/D
题目大意:
长度为n的字符串s只由0和1组成。
我们要把s分成最小数量的子序列,使得每一个子序列看起来像“010101 ...”或者“101010……”(即子序列不应包含两个相邻的0或1)。
先输出总共划分成了多少个子序列,再分别输出所属的子序列的编号。
input
4
4
0011
6
111111
5
10101
8
01010000
output
2
1 2 2 1
6
1 2 3 4 5 6
1
1 1 1 1 1
4
1 1 1 1 1 2 3 4
参考了这位佬的写法,强推:
https://www.cnblogs.com/pixel-Teee/p/13444081.html
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18,INF=1e9;
const LL N=5e5+10,M=4002;
#define endl '\n'
LL ans[N];
int main()
{
//cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
LL T=1;
cin>>T;
while(T--)
{
LL n;
cin>>n;
string s;
cin>>s;
s=" "+s;
queue<LL> q0,q1;
LL idx=0;
for(int i=1;i<=n;i++)
{
if(s[i]=='0')
{
if(q1.size()!=0)
{
LL t=q1.front();
//队列是先进先出,用了立即改变0 1状态
q1.pop();
ans[i]=ans[t];
q0.push(i);
}
else
{
ans[i]=++idx;
q0.push(i);
}
}
else
{
if(q0.size()!=0)
{
LL t=q0.front();
q0.pop();
ans[i]=ans[t];
q1.push(i);
}
else
{
ans[i]=++idx;
q1.push(i);
}
}
}
cout<<idx<<endl;
for(int i=1;i<=n;i++)
cout<<ans[i]<<" ";
cout<<endl;
}
return 0;
}
标签:Binary,typedef,String,LL,cin,661,Codeforces,序列
From: https://www.cnblogs.com/Vivian-0918/p/17067446.html