专栏文章
题解：AT_abc418_d [ABC418D] XNOR Operation
AT_abc418_d题解参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性，并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @mioafgbx
- 此快照首次捕获于
- 2025/12/02 15:59 3 个月前
- 此快照最后确认于
- 2025/12/02 15:59 3 个月前
题目不难。
解题过程
首先要发现的是，对于一个字符串，只有当这个字符串里 的个数是偶数时才是美丽字符串。
为什么？我们把每相近的两个 分成一组，单独考虑特殊字符串：两边是 ，中间是若干个 ，那么中间的若干个 合成一个 ，然后随便一个 和 合成 ，最后两个 可以合成一个 。
为什么？我们把每相近的两个 分成一组，单独考虑特殊字符串：两边是 ，中间是若干个 ，那么中间的若干个 合成一个 ，然后随便一个 和 合成 ，最后两个 可以合成一个 。
现在确定了这种特殊字符串可以合成 ，那么多组这种类型的字符串拼接而成也一定能合成 ，每个特殊字符串都有两个 ，所以最后的字符串 的个数一定是偶数。
于是问题变成了：一个字符串中有多少子串 的个数是偶数？该如何解决这个问题呢？
首先可以对 的个数求前缀和，定义 表示字符串的第 到 个字符有多少个 。那么固定右端点，如果区间左端点为 ，算一段区间 的个数就是：。所以要让这个式子的得数为偶数，这说明什么？其实就是 和 的奇偶性相同，所以分别记录奇数和偶数的数量即可。
首先可以对 的个数求前缀和，定义 表示字符串的第 到 个字符有多少个 。那么固定右端点，如果区间左端点为 ，算一段区间 的个数就是：。所以要让这个式子的得数为偶数，这说明什么？其实就是 和 的奇偶性相同，所以分别记录奇数和偶数的数量即可。
可能有点啰嗦，见谅。
代码
你没看错，就这么短。
CPP#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;
}
相关推荐
评论
共 0 条评论，欢迎与作者交流。
正在加载评论...