P3767.第2题-强迫症
题目内容
在小红书App首页的两列Plog中，小红薯独爱第一列。她将第一列每条Plog的点赞状态从上到下用一个二进制字符串s=(s1,s2,...sn)表示，其中:
- 字符si='1'表示用户已点赞第i条Plog;
- 字符si='0'表示用户未点赞第i条Plog。
小红薯定义一轮点赞行为如下:
- 选择索引对1≤l≤r≤n;
- 从第l条Plog 开始，到第r条Plog结束，进行一次重复点赞行为。这会使得原本未点赞的Plog变为已点赞，原本已点赞的Plog变为未点赞。
小红薯希望使得这一列Plog 的点赞状态调整为一个回文串，即第一条和最后一条Plog的点赞状态相同，第二条和倒数第二条Plog的点赞状态相同，以此类推。
请计算她最少需要进行的点赞行为轮数。
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数T(1≤T≤104)代表数据组数，每组测试数据描述如下:
第一行输入一个整数n(1≤n≤2∗105)，表示Plog数量;
第二行输入一个长度为n、由字符'0'和'1'构成的字符串s，表示点赞状态。
除此之外，保证单个测试文件的n之和不超过2∗105。
输出描述
对于每一组测试数据，新起一行，输出一个整数，代表使字符串s成为回文串所需的最少点赞行为轮数。
样例1
输入
2
2
01
3
010
输出
1
0
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
