#P17985. Strategic Stones

Strategic Stones

Strategic Stones

题目描述

给定一个只包含 0、1、? 的字符串。两名玩家轮流操作,先手先行动,直到所有问号被替换:

  • 先手每次选择一个问号,将其替换为 0;
  • 后手每次选择一个问号,将其替换为 1。

已确定的字符不能再改变。游戏结束时,得分为字符串中最长连续 0 段的长度;没有 0 时得分为 00。

先手希望得分尽可能大,后手希望得分尽可能小。双方均采用最优策略,求最终得分。

输入格式

第一行一个整数 TT。接下来 TT 行,每行一个字符串 ss,其长度记为 nn。

输出格式

每个用例输出一行一个整数,表示最终得分。

数据范围

1≤T≤1041\le T\le10^4,1≤n≤1051\le n\le10^5,所有用例的 nn 之和不超过 10610^6。

样例

6
??
000
111
0??0??0
0?0?0?0
00?00?100?0
1
3
0
3
5
5