2023 蓝桥杯热身赛

Problem P12. 异世界的人偶训练(20分)

在果冻的指示下,贤者禾枫创造了大量魔法人偶辅助魔法师工作。为了训练魔法人偶的思考能力,她打算让人偶两两之间进行一种游戏,具体规则如下:

给定一个只包含 01 的字符串 s ,其长度为 n ,两个人偶轮流在以下两种操作中选择一种执行:

  1. 将字符串反转,即从后往前重新书写字符串。如 00001 反转后变为 10000 。这个操作不耗费魔力。
  2. 将字符串中的 10 改为 1 。耗费 1 点魔力。

当字符串中的每个字符都变为 1 时游戏结束。此时,耗费魔力更少的那个人偶获得胜利。若两个人偶所耗费的魔力相同,则游戏平局。

为了让游戏更加有趣,禾枫添加了一个限制:

操作 1 只能在当前字符串不是回文串,且前一次操作不是操作 1 时执行。

其中,回文串是指从后往前读和从前往后读都相同的字符串,即:记下标从 1 开始,长为 n 的回文串 s 满足对任意 i ( 1\le i \le n ), s[i]=s[n-i+1]

在先手的第一次操作的情况下,不存在“前一次操作”,此时只需要满足字符串不是回文串的条件即可执行操作 1

举个例子,当第一个人偶执行了操作 1 后,即使此时的字符串不是回文串,按照限制,第二个人偶仍然无法执行操作 1 。反之亦然。

现在已知一个字符串,并且两个人偶都会以最优策略进行游戏,禾枫想要知道游戏的结果。

输入

输入一个整数 T ( 1 \le T \le 10^3 ),代表接下来有 T 个测试用例。

对于每个测试用例:

输入一行一个整数 n

接下来一行输入一个长度为 n ,并且只包含 01 的字符串。

对于 20\% 分数的数据,1\le n\le5\sum n \le 10 且保证输入的字符串是回文串。

对于 60\% 分数的数据,1\le n\le10^3\sum n \le 10^3 且保证输入的字符串是回文串。

对于 100\% 分数的数据, 1\le n\le10^3\sum n \le 10^5 且保证输入的字符串中至少有 10

输出

对于每个测试用例,第一行输出一个整数。若先手胜利,输出 1 ;若后手胜利,输出 -1 ;若游戏平局,输出 0

样例

标准输入 复制文本
2
1
0
2
00
标准输出 复制文本
-1
-1

提示

对于样例 1 中的测试用例 1 :

字符串已经是回文串,先手只能执行操作 2 ,之后字符串变为 1 ,游戏结束。

此时先手耗费 1 点魔力,后手耗费 0 点魔力,后手获得胜利。

对于样例 1 中的测试用例 2 :

字符串已经是回文串,先手只能执行操作 2 ,然后后手会执行操作 1 ,由于限制的存在,先手只能继续执行操作 2 ,游戏结束。

此时先手耗费 2 点魔力,后手耗费 0 点魔力,后手获得胜利。

登录以提交代码。
单点时限 1 秒
内存限制 128 MB
提交 16
通过 2