Codeforces 1399 D-Binary String To Subsequences(思考)
D. Binary String To Subsequences time limit per test2 seconds memory limit per test256 megabytes input standard input output standard output You are given a binary string s consisting of n zeros and ones.
Your task is to divide the given string into the minimum number of subsequences in such a way that each character of the string belongs to exactly one subsequence and each subsequence looks like “010101 …” or “101010 …” (i.e. the subsequence should not contain two adjacent zeros or ones).
Recall that a subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements. For example, subsequences of “1011101” are “0”, “1”, “11111”, “0111”, “101”, “1001”, but not “000”, “101010” and “11100”.
You have to answer t independent test cases.
Input
The first line of the input contains one integer t (1≤t≤2⋅104) — the number of test cases. Then t test cases follow.
The first line of the test case contains one integer n (1≤n≤2⋅105) — the length of s. The second line of the test case contains n characters ‘0’ and ‘1’ — the string s.
It is guaranteed that the sum of n does not exceed 2⋅105 (∑n≤2⋅105).
Output
For each test case, print the answer: in the first line print one integer k (1≤k≤n) — the minimum number of subsequences you can divide the string s to. In the second line print n integers a1,a2,…,an (1≤ai≤k), where ai is the number of subsequence the i-th character of s belongs to.
If there are several answers, you can print any.
Example 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
テーマ:
まずtを入力してtグループのテスト例を表し、各グループにnを入力して長さを表し、次に長さnの01列を入力し、そのサブシーケンス(不連続であってもよい)をグループ化する必要があります.各グループは0101...|10101...のように連続的な0または1しか現れません.その後、分割されたグループ数を出力し、各文字に対応するどのグループを出力する必要がありますか.
問題解決の考え方:
2つのvectorで0と1のグループを格納(コードに説明がある)、0はそのグループの先頭または1の後に続くのみであり、1も同様である.0を例にとると、1のベクトルが空であるか否かを判断するたびに、空であればこの0を改組する頭文字としてpos=(pos 1.size()+pos 0とする.size()は、0がどのグループになったかを表します.空でない場合は、1が存在するベクトルの末尾を削除し、pos 1の末尾の番号を0が存在するベクトルの末尾に格納します.
Code:
Your task is to divide the given string into the minimum number of subsequences in such a way that each character of the string belongs to exactly one subsequence and each subsequence looks like “010101 …” or “101010 …” (i.e. the subsequence should not contain two adjacent zeros or ones).
Recall that a subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements. For example, subsequences of “1011101” are “0”, “1”, “11111”, “0111”, “101”, “1001”, but not “000”, “101010” and “11100”.
You have to answer t independent test cases.
Input
The first line of the input contains one integer t (1≤t≤2⋅104) — the number of test cases. Then t test cases follow.
The first line of the test case contains one integer n (1≤n≤2⋅105) — the length of s. The second line of the test case contains n characters ‘0’ and ‘1’ — the string s.
It is guaranteed that the sum of n does not exceed 2⋅105 (∑n≤2⋅105).
Output
For each test case, print the answer: in the first line print one integer k (1≤k≤n) — the minimum number of subsequences you can divide the string s to. In the second line print n integers a1,a2,…,an (1≤ai≤k), where ai is the number of subsequence the i-th character of s belongs to.
If there are several answers, you can print any.
Example 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
テーマ:
まずtを入力してtグループのテスト例を表し、各グループにnを入力して長さを表し、次に長さnの01列を入力し、そのサブシーケンス(不連続であってもよい)をグループ化する必要があります.各グループは0101...|10101...のように連続的な0または1しか現れません.その後、分割されたグループ数を出力し、各文字に対応するどのグループを出力する必要がありますか.
問題解決の考え方:
2つのvectorで0と1のグループを格納(コードに説明がある)、0はそのグループの先頭または1の後に続くのみであり、1も同様である.0を例にとると、1のベクトルが空であるか否かを判断するたびに、空であればこの0を改組する頭文字としてpos=(pos 1.size()+pos 0とする.size()は、0がどのグループになったかを表します.空でない場合は、1が存在するベクトルの末尾を削除し、pos 1の末尾の番号を0が存在するベクトルの末尾に格納します.
Code:
#pragma GCC optimize(2)
#include