A12820 | Kirk and a Binary String (easy version)
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
The only difference between easy and hard versions is the length of the string. You can hack this problem only if you solve both problems.
Kirk has a binary string $s$ (a string which consists of zeroes and ones) of length $n$ and he is asking you to find a binary string $t$ of the same length which satisfies the following conditions:
- For any $l$ and $r$ ( $1 \leq l \leq r \leq n$ ) the length of the longest non-decreasing subsequence of the substring $s_{l}s_{l+1} \ldots s_{r}$ is equal to the length of the longest non-decreasing subsequence of the substring $t_{l}t_{l+1} \ldots t_{r}$ ;
- The number of zeroes in $t$ is the maximum possible.
A non-decreasing subsequence of a string $p$ is a sequence of indices $i_1, i_2, \ldots, i_k$ such that $i_1 < i_2 < \ldots < i_k$ and $p_{i_1} \leq p_{i_2} \leq \ldots \leq p_{i_k}$ . The length of the subsequence is $k$ .
If there are multiple substrings which satisfy the conditions, output any.
Kirk has a binary string $s$ (a string which consists of zeroes and ones) of length $n$ and he is asking you to find a binary string $t$ of the same length which satisfies the following conditions:
- For any $l$ and $r$ ( $1 \leq l \leq r \leq n$ ) the length of the longest non-decreasing subsequence of the substring $s_{l}s_{l+1} \ldots s_{r}$ is equal to the length of the longest non-decreasing subsequence of the substring $t_{l}t_{l+1} \ldots t_{r}$ ;
- The number of zeroes in $t$ is the maximum possible.
A non-decreasing subsequence of a string $p$ is a sequence of indices $i_1, i_2, \ldots, i_k$ such that $i_1 < i_2 < \ldots < i_k$ and $p_{i_1} \leq p_{i_2} \leq \ldots \leq p_{i_k}$ . The length of the subsequence is $k$ .
If there are multiple substrings which satisfy the conditions, output any.
输入格式
The first line contains a binary string of length not more than $2\: 000$ .
输出格式
Output a binary string which satisfied the above conditions. If there are many such strings, output any of them.
输入输出样例
输入 #1
110
输出 #1
010
输入 #2
010
输出 #2
010
输入 #3
0001111
输出 #3
0000000
输入 #4
0111001100111011101000
输出 #4
0011001100001011101000
In the first example:
- For the substrings of the length $1$ the length of the longest non-decreasing subsequnce is $1$ ;
- For $l = 1, r = 2$ the longest non-decreasing subsequnce of the substring $s_{1}s_{2}$ is $11$ and the longest non-decreasing subsequnce of the substring $t_{1}t_{2}$ is $01$ ;
- For $l = 1, r = 3$ the longest non-decreasing subsequnce of the substring $s_{1}s_{3}$ is $11$ and the longest non-decreasing subsequnce of the substring $t_{1}t_{3}$ is $00$ ;
- For $l = 2, r = 3$ the longest non-decreasing subsequnce of the substring $s_{2}s_{3}$ is $1$ and the longest non-decreasing subsequnce of the substring $t_{2}t_{3}$ is $1$ ;
The second example is similar to the first one.
- For the substrings of the length $1$ the length of the longest non-decreasing subsequnce is $1$ ;
- For $l = 1, r = 2$ the longest non-decreasing subsequnce of the substring $s_{1}s_{2}$ is $11$ and the longest non-decreasing subsequnce of the substring $t_{1}t_{2}$ is $01$ ;
- For $l = 1, r = 3$ the longest non-decreasing subsequnce of the substring $s_{1}s_{3}$ is $11$ and the longest non-decreasing subsequnce of the substring $t_{1}t_{3}$ is $00$ ;
- For $l = 2, r = 3$ the longest non-decreasing subsequnce of the substring $s_{2}s_{3}$ is $1$ and the longest non-decreasing subsequnce of the substring $t_{2}t_{3}$ is $1$ ;
The second example is similar to the first one.
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted