[CF1399D] Binary String To Subsequences

[CF1399D] Binary String To Subsequences - 构造

Description

把一个 01 串划分成若干个 01 交替的子序列，求最小划分数量并给出任意一组合法划分

Solution

考虑一个贪心的划分过程

维护两个无序集合，一个表示当前划分出的，末尾是 0 的序列，一个表示末尾是 1 的序列，存编号

每次遇到一个 0，就从末尾是 1 的里面取出一个，标记，然后扔进末尾是 0 的那个集合里面

反之亦然

如果不够，就开一个新的

#include <bits/stdc++.h>
using namespace std;

#define int long long

void solve()
{
    int n;
    cin >> n;

    string str;
    cin >> str;
    str = " " + str;

    vector<int> v[2];
    int ind = 0;

    vector<int> ans(n + 2);

    for (int i = 1; i <= n; i++)
    {
        int cur = str[i] == '1';
        if (v[cur].size() == 0)
            v[cur].push_back(++ind);
        int p = v[cur].back();
        v[cur].pop_back();
        v[cur ^ 1].push_back(p);
        ans[i] = p;
    }

    cout << ind << endl;
    for (int i = 1; i <= n; i++)
        cout << ans[i] << " ";
    cout << endl;
}

signed main()
{
    ios::sync_with_stdio(false);

    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
}