#389. Replace and Compress(替换与压缩)

Replace and Compress(替换与压缩)

题目描述

给定一个长度为 nn 的二进制字符串 ss,其中每个字符都是 0 或 1。

你需要恰好执行一次操作。一次操作包括以下两个步骤:

  1. 可选翻转:你可以选择至多一个下标 ii(满足 2≤i≤n−12\le i\le n-1),将 sis_i 翻转:0 变为 1,1 变为 0。也可以不翻转任何字符。首尾两个字符不能修改。
  2. 压缩字符串:将每个由相同字符连续组成的极大连续段替换成一个对应的字符。

这里,“极大连续段”是指不能再向左或向右加入相同字符的连续子串。例如,100111011 压缩后会变为 10101。

请计算,执行上述操作后,能够得到多少种不同的最终字符串。

输入格式

第一行包含一个整数 tt(1≤t≤1041\le t\le 10^4),表示测试用例数。

接下来 tt 行,每行给出一个仅由 0 和 1 组成的字符串 ss(3≤∣s∣≤3×1053\le |s|\le 3\times 10^5)。

保证所有测试用例中字符串长度之和不超过 3×1053\times10^5。

输出格式

对每个测试用例输出一行,包含一个整数,表示可能得到的不同最终字符串的数量。

样例

7
001
000
010
00010
100111011
001011010
1111
1
2
2
3
3
2
2

样例说明

第 1 组: 不翻转时得到 001,翻转第 2 个字符后得到 011。二者压缩后都是 01,因此答案为 11。

第 5 组:

  • 不翻转任何字符:100111011 压缩后为 10101;
  • 翻转第 2 个字符:110111011 压缩后为 10101;
  • 翻转第 5 个字符:100101011 压缩后为 1010101;
  • 翻转第 7 个字符:100111111 压缩后为 101。

所以不同的结果一共有 101、10101、1010101 三种,答案为 33。

数据范围与限制

  • 时间限制:2 秒。
  • 内存限制:512 MiB。
  • 1≤t≤1041\le t\le10^4。
  • 3≤∣s∣≤3×1053\le |s|\le3\times10^5。
  • 每个输入文件的全部字符串长度之和不超过 3×1053\times10^5。