526互联

练习记录- AtCoder Beginner Contest 295（D）

发布时间 2023-04-09 17:03:06作者: xishuiw

vp的 觉得我的D很聪明所以来写一下（乐

D - Three Days Ago

题意就是 求所有字符出现次数均为偶数的字串数量

太笨了所以想了很久

我把 存在奇数个1 当作第2位是 2 那么 当经过了两次1  2^2 这个2 就变成了0

2 就是第二位 就是4 ...以此类推 

所以我遍历一遍字符串 求出当前的异或 并记录到map里面 

为了让整串为0的可以被算到 mp[0]初始值为1

例如 20230322

读入第1个的时候 mp[4]=1；

读入第2个的时候 mp[5]=1；

读入第6个的时候 mp[0]=2; 此时为2 ans+1;

读入第7个的时候 mp[4]=2;ans+1;

读入第8个的时候 mp[0]=3; 说明前面有2种匹配方法 ans+2

这样就得出答案了

#include<bits/stdc++.h>
#define close     std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN = 5e5+7;
const ll mod =1e9+7;
const ll inf =0x3f3f3f3f;
const ll INF =0x3f3f3f3f3f3f3f3f;
#define int long long 
int dp[2][1024],p[20];
int pre[1024];
int lowbit(int x){ return x&-x; }
int gcd(int x,int y){int k=0; if(x<y){k=x;x=y;y=k;}while(x%y!=0){k=x%y;x=y;y=k;}return y;}
ll _power(ll a,int b){ll ans=1,res=a;while(b){if(b&1) ans=ans*res%mod;res=res*res%mod;b>>=1;}return ans%mod;}
void solve(){
    string s;cin>>s;
    int pp=1,bz=0;
    for(int i=0;i<=9;i++){
        p[i]=pp;
        pp*=2;
    }
    int n=s.length();
    int ans=0;
    pre[0]++;
    for(int i=0;i<n;i++){
        int m=s[i]-'0';
        bz=bz^p[m];
        if(bz==0||pre[bz]!=0) ans+=pre[bz];
        pre[bz]++;
    }
    cout<<ans;
}
signed main(){
    solve();
}
View Code

虽然大家应该都是这样写的但我还是要发一下