【CF#469Div2-C】Zebras

来源和评测点

Codeforces Round #469 (Div.2)
CF#469Div2-C

题目

【题目大意】
Zebra:0和1交替出现,开头结尾都是0。
给出字符串,分割成子序列(不一定连续),必须每一个都是Zebra
【输入格式】
只有一行,01字符串
无解输出-1
【约束条件】
长度不超过200000
【输出格式】
有spj
第一行子序列个数
每行开头,当前子序列长度,然后是由哪些位置组成
以上按照从小到大排序
【输入样例】
0010100
【输出样例】
3
3 1 3 4
3 2 5 6
1 7

刷题记录

1h
1WA
1TLE
比完赛后
1RE
1AC

分析

我打了个很丑的暴力,然后是一个个子序列寻找的,超慢
然后根本没考虑过可以跑一遍过
重点是STL的妙用,确保正确性,同时动态空间

代码

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
//Zory-2018
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
//*******************全局常量*******************
//*******************全局定义*******************
char s[200010];
vector<int> f[200010];
set<int> s0,s1;
int n,m;
//*******************实现*******************
bool solve()
{
for(int i=1;i<=n;i++)
{
if(s[i]=='0')
{
if(s1.empty())
{
f[++m].push_back(i);
s0.insert(m);
}
else
{
int x=*s1.begin();
f[x].push_back(i);
s1.erase(x);
s0.insert(x);
}
}
else
{
if(s0.empty()) return 0;
int x=*s0.begin();
f[x].push_back(i);
s0.erase(x);
s1.insert(x);
}
}
if(!s1.empty()) return 0;
return 1;
}
void output()
{
printf("%d\n",m);
for(int i=1;i<=m;i++)
{
printf("%d ",f[i].size());
for(int j=0;j<=f[i].size()-1;j++) printf("%d ",f[i][j]);
printf("\n");
}
}
//*******************主函数*******************
int main()
{
scanf("%s",s+1);
n=strlen(s+1);m=0;
if(solve()) output();
else printf("-1\n");
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/8404.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%