自动搬运

查看原文

来自洛谷，原作者为

	Spark_King 15岁添柴少年

搬运于2025-08-24 22:52:43，当前版本为作者最后更新于2024-01-10 20:16:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P9887 题解

初步分析

这道题大概率就是一道推理题。

首先，题目中 $s$ 和 $t$ 是 $01$ 字符串，所以对于同一个位置 $i$，只存在相同和不相同两种状态，并且在对区间进行了取反操作后上述状态会改变为相反状态。

于是，我们可以将这两种状态转化为另一个 $01$ 字符串 $a$。
如图： 其中，在 $a$ 字符串中，$1$ 表示相同，$0$ 表示不同。

这样一来，我们就可以愉快地进行下一步了。

深入思考

题目要求我们对两个字符串分别进行区间取反操作，也就是将上述 $a$ 的两个区间进行先后取反以至于 $a$ 中所有字符都为 $1$ 。那么我们可以进行以下分类讨论。
（这里我们先定义整型变量 $k$ 表示 $a$ 中全为字符 $0$ 的子串个数）

1. $k>2$ 时，由于只能修改两个区间，并且修改时不能影响其他正确的部分，所以不存在合法的取反操作。

2. $k=2$ 时，此时两个区间都必须分别包含在修改区间内（不能同时修改，否则会变回 $0$）。值得注意的是，在这两个区间中间还有一个全为 $1$ 的子串，所以可以通过先后将该区间取反两次的方式得到。此时有 $6$ 种操作，这里不一一列举。

3. $k=1$ 时，此时可以将要修改区间分为两部分分别取反，也可以在第一次取反时取反整个要修改区间并加上两边为 $1$ 的部分，然后第二次对原为 $1$ 的部分再次取反，经计算有 $2\times(n-1)$ 种。

4. $k=0$ 时，此时只要先后修改同一区间即可，共有 $n\times(n+1)\div 2$ 种。

此时，我们就可以正式开始敲代码了。

代码实现

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll T;
ll n;
string s, t;
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);//快读
	cin >> T;
	while (T--) {
		cin >> n >> s >> t;
		ll k = 0;//用于记录上述不相等的子串的个数
		bool flag = 0;
		for (ll i = 0; i < n; i++) {
			if (s[i] != t[i] && flag == 0) k++, flag = 1;
			else if (s[i] == t[i]) flag = 0;
		}//遍历字符串
		if (k > 2) cout << "0\n";
		else if (k == 2) cout << "6\n";
		else if (k == 1) cout << 2 * (n - 1) << "\n";
		else cout << n*(n + 1) / 2 << "\n";
		//按照上一板块的分类输出答案
	}
	return 0;//结束程序
}