#P9684. 「ROI2019」花环

    ID: 6305 传统题 2000ms 512MiB 尝试: 1 已通过: 1 难度: 6 上传者: 标签>CF2000提高暴力枚举贪心保持领先一维前缀和预处理下一出现位置ROI2019

「ROI2019」花环

题目描述

对于一个 0101 串,如果它可以被表示为 A1A1A……1AA1A1A……1A 的形式,其中

  • A 是若干个 00 或空串,且
  • 每个 A 包含的 00 数量相等,且
  • 首尾都是 A,中间有至少一个 11

则称这是一个「美丽的」0101 串。

给一个 0101 串,请删除尽量少的数字,使得剩下的数字形成一个美丽的 0101 串。

输入格式

第一行一个整数 nn。第二行一个长度为 nn 的二进制字符串,保证至少有一个 1。

输出格式

第一行一个mm, 第二行一个长度为mm的字符串。

样例

10
0100100000
7
0001000
3
111
3
111
7
0100101
5
01010

数据范围与提示

对于所有数据,1⩽n⩽5000001 ⩽ n ⩽ 500000。

设 kk 表示输入的 01 串中 1 的个数。

子任务 # 分值 n⩽n ⩽ k⩽k ⩽
1 2020 1515
2 10001000 22
3 1515
4 1616
5 1010 100000100000 5050
6 1414 500000500000

原赛题面