Codeforces 1399D: Binary String to Subsequences

Codeforces 1399D C++ 一解.

分析

本题本身的思路是很清晰的, 但考虑到一些极端数据, 需要额外添加一些数据结构.

可以确定的是, 给定的字符串的每个字符都要纳入某一个子序列中. 同时可以注意到, 如果已经存在一些子序列, 对于源串的某个字符, 只要其能接在某个子序列之后, 就不会增加现有子序列的数量; 若这个字符无法接在任何现有子序列之后, 拆开其中一部分子序列使其能够纳入也不会使子序列数量减少. 因此这种策略是最优的.

本题给定的数据规模 $\sum n\leq2\times10^5$. 若每次尝试添加字符到子序列时都顺序搜索现有子序列, 部分测试点无法通过 (例如:

1
200000
111111111111... (200000 个 1)

). 因此可以设置两个栈结构用于存储现有的 “尾数” 为 0 和 1 的子序列的序号. 因为只需要构造出一种可行的组合子序列的方案即可, 只需要对栈作入栈, 出栈操作, 其时间开销可以接受.

代码

#include <cstring>
#include <iostream>
#include <vector>

using namespace std;

char change_bit(char x)
{
    return x == '1' ? '0' : '1';
}

int change_bit(int x)
{
    return x ? 0 : 1;
}

int get_bit(char x)
{
    return x - '0';
}

void solve_and_print(string s)
{
    int n = s.length(), total = 0;
    vector<int> ans(n, 0), stack[2];

    for (int i = 0; i < n; ++i)
    {
        char c = change_bit(s[i]);
        int x = get_bit(c), y = get_bit(s[i]);
        if (stack[x].empty())
        {
            ++total;
            ans[i] = total;
            stack[y].push_back(total - 1);
        }
        else
        {
            int j = stack[x].back();
            stack[x].pop_back();
            stack[y].push_back(j);
            ans[i] = j + 1;
        }
    }

    cout << total << endl;
    for (int i = 0; i < n; ++i)
    {
        cout << ans[i] << ' ';
    }
    cout << endl;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int t, n;
    string s;

    cin >> t;

    while (t--)
    {
        cin >> n >> s;
        solve_and_print(s);
    }

    return 0;
}