Binary String To Subsequences
题意：给一个01串，要从里面摘出来01相间的子序列，问在满足条件的情况下最少子序列的数目是多少？思路：遍历01串，如果是0就加到结尾字符是1的子序列末尾；如果是1就加到结尾字符是0的子序列末尾。这里就只需要记录一下最新的结尾是0或1的子序列的标号，以及该标号下的上一个结尾是0或1的子序列的标号，类似链式前向星的意思。遍历过程中更新最新的标号和上一个标号即可，同时记录答案即可。
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
typedef long long ll
;
using namespace std
;
const int maxN
= 200005;
int read() {
int x
= 0, f
= 1; char ch
= getchar();
while(ch
< '0' || ch
> '9') { if(ch
== '-') f
= -f
; ch
= getchar(); }
while(ch
>= '0' && ch
<= '9') { x
= x
* 10 + ch
- '0'; ch
= getchar(); }
return x
* f
;
}
int ans
[maxN
];
int lst_zero
[maxN
];
int lst_one
[maxN
];
void init(int n
) {
for(int i
= 0; i
<= n
; ++ i
) {
lst_zero
[i
] = lst_one
[i
] = ans
[i
] = 0;
}
}
int main() {
int t
; t
= read();
while(t
-- ) {
int n
; n
= read(); init(n
);
string s
; cin
>> s
;
int top
= 0;
int one
= 0, zero
= 0;
for(int i
= 0; i
< n
; ++ i
) {
if(s
[i
] == '0') {
if(one
) {
ans
[i
] = one
;
lst_zero
[one
] = zero
;
zero
= one
;
} else {
ans
[i
] = ++ top
;
lst_zero
[top
] = zero
;
zero
= top
;
}
one
= lst_one
[one
];
} else {
if(zero
) {
ans
[i
] = zero
;
lst_one
[zero
] = one
;
one
= zero
;
} else {
ans
[i
] = ++ top
;
lst_one
[top
] = one
;
one
= top
;
}
zero
= lst_zero
[zero
];
}
}
cout
<< top
<< endl
;
for(int i
= 0; i
< n
; ++ i
) {
cout
<< ans
[i
] << ' ';
}
cout
<< endl
;
}
return 0;
}
