#389. Replace and Compress(替换与压缩)
Replace and Compress(替换与压缩)
题目描述
给定一个长度为 的二进制字符串 ,其中每个字符都是 0 或 1。
你需要恰好执行一次操作。一次操作包括以下两个步骤:
- 可选翻转:你可以选择至多一个下标 (满足 ),将 翻转:
0变为1,1变为0。也可以不翻转任何字符。首尾两个字符不能修改。 - 压缩字符串:将每个由相同字符连续组成的极大连续段替换成一个对应的字符。
这里,“极大连续段”是指不能再向左或向右加入相同字符的连续子串。例如,100111011 压缩后会变为 10101。
请计算,执行上述操作后,能够得到多少种不同的最终字符串。
输入格式
第一行包含一个整数 (),表示测试用例数。
接下来 行,每行给出一个仅由 0 和 1 组成的字符串 ()。
保证所有测试用例中字符串长度之和不超过 。
输出格式
对每个测试用例输出一行,包含一个整数,表示可能得到的不同最终字符串的数量。
样例
7
001
000
010
00010
100111011
001011010
1111
1
2
2
3
3
2
2
样例说明
第 1 组: 不翻转时得到 001,翻转第 2 个字符后得到 011。二者压缩后都是 01,因此答案为 。
第 5 组:
- 不翻转任何字符:
100111011压缩后为10101; - 翻转第 2 个字符:
110111011压缩后为10101; - 翻转第 5 个字符:
100101011压缩后为1010101; - 翻转第 7 个字符:
100111111压缩后为101。
所以不同的结果一共有 101、10101、1010101 三种,答案为 。
数据范围与限制
- 时间限制:2 秒。
- 内存限制:512 MiB。
- 。
- 。
- 每个输入文件的全部字符串长度之和不超过 。