P9887题解

Spark_King · 2024-01-10 20:16:14 · 题解

P9887 题解

初步分析

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

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

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

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

深入思考

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

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

代码实现

#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;//结束程序
}