Codeforces 950C(模拟)

Codeforces 950C
题意:给定一个$01$字符串$s$,求它的子串,子串满足两个条件
①子串必须的$01010….$相互交换的(只含有$0$,其长度为$1$也是符合的)。
②子串的开头和结尾必须是$0$
如果不存在这样的子串则输出$-1$;否则输出一个$k$($k$为子串的个数,$k$值不必的最值),接下来的k行,输出子串的长度和其在$s$上的序列数

可以转化为接替问题,直接开一排桶扫数组然后将数字扔进去即可,中途判断是否有解即可。

Codeforces Submission

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
48
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<cmath>
#include<set>
#include<iostream>
using namespace std;
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define pr pair<int, int>
#define fir first
#define sec second
#define mp make_pair
char s[200000 + 10];
int n, ze = 0, mx = 0;
vector<int> a[200000 + 10];
void clean() {
}
int solve() {
clean();
n = strlen(s + 1);
for (int i = 1; i <= n; i++) {
if (s[i] == '0') {
a[++ze].push_back(i);
mx = max(mx, ze);
} else {
if (ze == 0) return printf("-1\n"), 0;
a[ze--].push_back(i);
}
}
if (mx != ze) return printf("-1\n"), 0;
printf("%d\n", mx);
for (int i = 1; i <= mx; i++) {
printf("%d ", a[i].size());
for (int j = 0; j < (int)a[i].size(); j++) {
printf("%d ", a[i][j]);
}
printf("\n");
}
return 0;
}
int main() {
scanf("%s", s + 1), solve();
return 0;
}

------ 本文结束 ------