题目内容

在一场盛大的光影展览中，有一条由 $n$ 盏灯组成的灯带，灯按顺序排列，编号为 $1$ 至 $n$。每盏灯的状态只可能是「亮」(用字符 '1' 表示) 或「灭」(用字符 '0' 表示)。艺术总监希望这条灯带形成中心对称的视觉效果，即对于任意位置 $i$，第 $i$ 盏灯的状态与倒数第 $i$ 盏灯（第 $n-i+1$ 盏）相同。

灯光师拥有一台特殊的控制面板：每次操作，她可以选定一个连续区间的灯 $[l, r]$（$1 \le l \le r \le n$），并按下翻转按钮。翻转操作会将区间内所有灯的状态取反——灭变亮，亮变灭。

给定灯带的初始状态序列，灯光师想知道最少需要多少次这样的翻转操作，才能使得整条灯带成为中心对称（即状态序列成为回文序列）。

请编写程序，对于每组给定的初始状态，输出最少操作次数。

约束条件：

• 测试数据组数 $T$ 满足 $1 \le T \le 10^4$。
• 每组数据中灯的数量 $n$ 满足 $1 \le n \le 2 \times 10^5$。
• 所有测试数据的 $n$ 之和不超过 $2 \times 10^5$。
• 初始状态字符串 $s$ 仅包含字符 '0' 和 '1'。

输入描述

输入的第一行包含一个整数 $T$ $(1 \le T \le 10^4)$，表示测试数据的组数。

每组测试数据包含两行：

• 第一行包含一个整数 $n$ $(1 \le n \le 2 \times 10^5)$，表示灯的数量。
• 第二行包含一个长度为 $n$ 的字符串 $s$，由字符 '0' 和 '1' 组成，按顺序表示每盏灯的初始状态（'1' 表示亮，'0' 表示灭）。

保证所有测试数据的 $n$ 之和不超过 $2 \times 10^5$。

输出描述

对于每组测试数据，输出一行一个整数，表示使得灯带成为中心对称所需的最少翻转操作次数。

样例1

输入

2
4
1100
6
101000

输出

1
2

说明

输入包含 $T=2$ 组测试数据。

第一组 $n=4$，初始状态 1100。为了让灯带中心对称，检查前 $\lfloor n/2 \rfloor = 2$ 对：位置 $1$ 与 $4$（字符 1 与 0 不同），位置 $2$ 与 $3$（字符 1 与 0 不同）。这两处不对称是连续的，因此可以在一次操作内翻转区间 $[2,3]$（或 $[1,3]$ 等）将它们同时修正，最少操作次数为 1。

第二组 $n=6$，初始状态 101000。检查前 $3$ 对：$(1,6)$ 字符 1 与 0 不同，$(2,5)$ 字符 0 与 0 相同，$(3,4)$ 字符 1 与 0 不同。不对称位置出现在第 $1$ 对和第 $3$ 对，它们被对称的对 $(2,5)$ 隔开，形成两个不连续的段。因此至少需要两次翻转操作，例如先翻转 $[1,2]$ 等，后翻转 $[3,3]$，最少操作次数为 2。

样例2

输入

1
1
0

输出

0

说明

只有一盏灯，$n=1$，初始状态 0。单个灯天然满足中心对称，不需要任何操作。答案为 0。

样例3

输入

2
8
11000110
5
11111

输出

2
0

说明

输入包含 $T=2$ 组测试数据。

第一组 $n=8$，初始状态 11000110。检查前 $4$ 对：$(1,8)$ 字符 1 与 0 不同，$(2,7)$ 字符 1 与 1 相同，$(3,6)$ 字符 0 与 1 不同，$(4,5)$ 字符 0 与 0 相同。不对称对出现在 $(1,8)$ 和 $(3,6)$，中间被对称对隔开，形成两个不连续的段，最少需要 2 次翻转。

第二组 $n=5$，初始状态 11111。所有灯状态相同，已经完全中心对称，最少操作次数为 0。

开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写