题解：AT_abc418_d [ABC418D] XNOR Operation

· · 题解

题目不难。

解题过程

首先要发现的是，对于一个字符串，只有当这个字符串里 0 的个数是偶数时才是美丽字符串。
为什么？我们把每相近的两个 0 分成一组，单独考虑特殊字符串：两边是 0，中间是若干个 1，那么中间的若干个 1 合成一个 1，然后随便一个 0 和 1 合成 0，最后两个 0 可以合成一个 1。

现在确定了这种特殊字符串可以合成 1，那么多组这种类型的字符串拼接而成也一定能合成 1，每个特殊字符串都有两个 0，所以最后的字符串 0 的个数一定是偶数。

于是问题变成了：一个字符串中有多少子串 0 的个数是偶数？该如何解决这个问题呢？
首先可以对 0 的个数求前缀和，定义 sum_i 表示字符串的第 1 到 i 个字符有多少个 0。那么固定右端点，如果区间左端点为 l，算一段区间 0 的个数就是：sum_i - sum_{l-1}。所以要让这个式子的得数为偶数，这说明什么？其实就是 sum_i 和 sum_{l-1} 的奇偶性相同，所以分别记录奇数和偶数的数量即可。

可能有点啰嗦，见谅。

代码

你没看错，就这么短。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 5;
int n, sum, jsl, osl = 1;
ll ans;
string s;
int main(){
    cin >> n >> s;
    s = ' ' + s;
  //前缀和数组可以省略，用一个变量记录，表示字符串第1到i个字符有多少个0
    for(int i = 1;i <= n;i++){
        sum += (s[i] == '0');
        if(sum & 1) ans += jsl++;//更新答案和奇数数量
        else ans += osl++;//更新答案和偶数数量
    }
    cout << ans;
    return 0;
}