1399D - Binary String To Subsequences（队列）

╰+攻爆jí腚メ 2021-07-16 19:15 281阅读 0赞

[题目][Link 1]

思路：看数据大小1e5可以知道我们需用O(n)或O(nlogn)的算法。故开两个队列，q0,q1，一个表示存储以0结尾一个存储以1结尾，当队列空时另增加一个新的子序列，不为空时将转变一个序列从q0->q1（当遇到1且q0中还剩下xxxx0的字序列时，不剩则再增加一个子序列），细节见代码。

Code:

#include<iostream>
    #include<string>
    #include<map>
    #include<algorithm>
    #include<memory.h>
    #include<cmath>
    #include<vector>
    #include<queue>
    #define pii pair<int,int>
    #define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
    using namespace std;
    typedef long long ll;
    const int Max = 1e6 + 5;
    int lst[Max], ls[Max];
    int b[Max];
    
    int main()
    { 
    	FAST;
    	int t;cin >> t;
    	while (t--)
    	{ 
    		int n;cin >> n;
    		for (int i = 1;i <= n;i++)
    		{ 
    			char a;cin >> a;lst[i] = a - '0';
    		}
    		queue<int> q0, q1;int x = 0;
    		for (int i = 1;i <= n;i++)
    		{ 
    			if (lst[i] == 0)
    			{ 
    				if (q1.size() == 0)
    				{ 
    					q0.push(++x);
    					b[i] = x;
    				}
    				else
    				{ 
    					q0.push(q1.front());
    					b[i] = q1.front();
    					q1.pop();
    				}
    			}
    			else
    			{ 
    				if (q0.size() == 0)
    				{ 
    					q1.push(++x);
    					b[i] = x;
    				}
    				else
    				{ 
    					q1.push(q0.front());
    					b[i] = q0.front();
    					q0.pop();
    				}
    			}
    		}
    		cout << x << endl;
    		for (int i = 1;i <= n;i++)cout << b[i] << " ";
    		cout << endl;
    	}
    
    		
    }

[Link 1]: https://codeforces.ml/problemset/problem/1399/D