D. Binary String To Subsequences
题意
给出一个01串要求取出尽量少的子序列使得每个子序列都形如01010…或1010…
输出最少分出几个子序列,并输出原来每个字符属于哪个子序列
题解
单纯的实现模拟
具体的用两个栈zero,one存 以0 or 1结尾的子序列最后一个字符的原下标
每次遇到一个1 先看栈zero里面有没有以0为结尾的子序列有就取出一个以0为结尾的子序列 更新最后一个字符的
下标并塞入以1为结尾的栈one中 若没有以0为结尾的子序列那么就新开一个子序列以当前的1为结尾压入栈one中
同理遇到一个0也如此操作 最后最少需要分割为zero.size()+one.size()个子序列
每个子序列都形如01010…或1010…
对于每个字符属于哪个子序列 此处设置了一个belong数组
譬如当前拿到一个1 存在以0为结尾的子序列( 它在原串的下标为zero.top() )
那么belong[i]=zero.top() 若不存在以0为结尾的那么
就新开一个以1为结尾的子序列belong[i]=i压入栈one中 最后用belong数组倒着回溯即可分组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const ll Max=2e5+5;
const double PI=acos(-1);
int belong[Max],ans[Max];
bool vis[Max];
int main() {
Turnoff;
int t;cin>>t;
while(t--){
int n;cin>>n;
string s;cin>>s;
stack<int>zero,one;int temp;
for(int i=0;i<n;i++){
vis[i]=0;
if(s[i]=='1'){
if(zero.empty())one.push(i),belong[i]=i;
else {
belong[i]=zero.top();
zero.pop();one.push(i);
}
}
else{
if(one.empty())zero.push(i),belong[i]=i;
else{
belong[i]=one.top();
one.pop();zero.push(i);
}
}
}
int cnt=0;
cout<<one.size()+zero.size()<<endl;
for(int i=n-1;i>=0;i--){
if(vis[i])continue;
int temp=i;
while(belong[temp]!=temp)ans[temp]=cnt,temp=belong[temp],vis[temp]=1;
ans[temp]=cnt;cnt++;vis[temp]=1;
}
for(int i=0;i<n;i++)cout<<ans[i]+1<<" ";
cout<<endl;
}
}
|
或者发现每次取得的字符1 or 0 若要重新开一个子序列它都属于 第zero.size()+one.size()个子序列
否则他就接入 zero.top() or one.top() 后 压入栈的信息为以0 or 1 为结尾的子序列是第几组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| #include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
#endif
int t;
cin >> t;
while (t--) {
int n;
string s;
cin >> n >> s;
vector<int> ans(n);
vector<int> pos0, pos1;
for (int i = 0; i < n; ++i) {
int newpos = pos0.size() + pos1.size();
if (s[i] == '0') {
if (pos1.empty()) {
pos0.push_back(newpos);
} else {
newpos = pos1.back();
pos1.pop_back();
pos0.push_back(newpos);
}
} else {
if (pos0.empty()) {
pos1.push_back(newpos);
} else {
newpos = pos0.back();
pos0.pop_back();
pos1.push_back(newpos);
}
}
ans[i] = newpos;
}
cout << pos0.size() + pos1.size() << endl;
for (auto it : ans) cout << it + 1 << " ";
cout << endl;
}
return 0;
}
|