本章对标:D - Three Days Ago
问题非常简单,也就是求出所有连续区间且这个区间内的数字都出现了偶数次的总合法区间数
那么很明显有中 \(O(n^2)\) 的算法,但复杂度不够,那么枚举区间不行,从别的方面入手,考虑到每个字符只能是数字,那么我们此时可以将其转化为一个二进制串,表示的含义就是,某个数字出现了偶数次还是奇数次,举个例子:12234445,那么其二进制串为:1011100000,因为我们的次数一定是递增的,也就是如果我们从 000000000 转化到 000000000,那么很明显这段区间就符合偶数次,也就是说只要出现了两次同样的,那么这段区间就符合,这样我们就可以用 \(map\) 来储存次数
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,mod=1e9+7;
signed main()
{
std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
string s; cin>>s;
int n=s.size();
s=" "+s;
map<string,int>mp;
int res=0;
string now="0000000000";
mp[now]++;
for(int i=1;i<=n;i++){
if(now[s[i]-'0']=='1'){
now[s[i]-'0']='0';
}
else now[s[i]-'0']='1';
res+=mp[now],mp[now]++;
}
cout<<res;
return 0;
}
标签:那么,数字串,数字,某段,int,偶数,区间,string
From: https://www.cnblogs.com/o-Sakurajimamai-o/p/18246445