ABC295 D - Three Days Ago

川长思鸟来 2024-03-26 22:15 19阅读 0赞

**没开long long赛后半分钟过题，笑死**

**怎么有人都大二了还会忘记开long long的！**

[D - Three Days Ago (atcoder.jp)][D - Three Days Ago _atcoder.jp]

题意：

![ab57611900e1ff9768271bbd7be37bed.png][]

思路：

考虑状压处理

开一个桶，记录前缀每一个数的出现次数的奇偶性

当出现次数是偶数时，就是0，否则就是1

然后满足条件的区间就用异或前缀和处理就好了，算一算组合数

特殊情况就是全是0的时候，这时候1~i也算，需要额外+1

这道题本来是能过的！真可惜

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    using i64 = long long;
    const int mxn=5e5+10;
    const int mxe=1e8+10;
    const int mod=1e9+7;
    
    
    map<int,int> mp;
    int n,cur=0;
    string s;
    void print(int x){
        for(int j=9;j>=0;j--){
            if((x>>j)&1) cout<<1;
            else cout<<0;
        }
        cout<<'\n';
    }
    void solve(){
        cin>>s;
        n=s.size();
        s=" "+s;
        int ans=0;
        for(int i=1;i<=n;i++){
            int j=s[i]-'0';
            cur^=(1ll<<j);
            //print(cur);
            if(cur==0) ans+=mp[cur]+1ll;
            else ans+=mp[cur];
            mp[cur]++;
        }
        cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[D - Three Days Ago _atcoder.jp]: https://atcoder.jp/contests/abc295/tasks/abc295_d
[ab57611900e1ff9768271bbd7be37bed.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/c3a6b9c0140d49ea95123ca3838b33c3.png

发表评论取消回复

表情：

评论列表（有 0 条评论，19人围观）

还没有评论，来说两句吧...

相关阅读

相关 Atcoder ABC 139D

Atcoder ABC 139D 解法： > 等差数列求和公式，记得开 $ long long $ CODE: include<iostre...

末蓝、/ 2024年04月20日 10:31/ 0 赞/ 40 阅读

相关 ABC295 D - Three Days Ago

没开long long赛后半分钟过题，笑死怎么有人都大二了还会忘记开long long的！ [D - Three Days Ago (atcoder.jp)][D - T

川长思鸟来/ 2024年03月26日 22:15/ 0 赞/ 20 阅读

相关 ABC252 D - Distinct Trio

还有一天就篮球被了，好紧脏.... 我的世界将被摧毁，也许事与愿违是时候放弃一些东西了呢 [D - Distinct Trio (atcoder.jp)][D - Di

小灰灰/ 2024年03月24日 15:45/ 0 赞/ 11 阅读

相关 ABC 238 D - AND and SUM

感觉有点难啊今天做了几道D，感觉除了DP都挺难的.... ![7977e156ab8f4d26b221ecde9ae0728a.png][] 思路：异或和加有一个性

傷城~/ 2024年03月24日 01:29/ 0 赞/ 53 阅读

相关【简单DP】ABC312 D

[D - Count Bracket Sequences][] 题意：括号匹配,需要满足以下两个性质前i个字符中,左括号的数量必须大于等于右括号最后左括号的数量要

朱雀/ 2024年03月23日 18:46/ 0 赞/ 29 阅读

相关【多维BFS】ABC311 D

[D - Grid Ice Floor][] 题意： ![21929a903e384fb5ba0355f5a95a8438.png][] 思路：可以发现，这种魔改BF

Dear 丶/ 2024年03月22日 19:58/ 0 赞/ 45 阅读

相关【多维BFS】ABC308 D

VP的时候居然花了半小时！可恶！ [D - Snuke Maze (atcoder.jp)][D - Snuke Maze _atcoder.jp] 题意： ![79

拼搏现实的明天。/ 2024年03月17日 13:55/ 0 赞/ 17 阅读

相关【枚举】ABC160 D - Line++

[D - Line++][D - Line] 题意： ![c72c5af344f24b1baa82775a0c584ba3.png][] 思路：看数据范围应该是n^2

青旅半醒/ 2024年03月17日 11:13/ 0 赞/ 11 阅读

相关【树上染色】ABC146 D

[D - Coloring Edges on Tree (atcoder.jp)][D - Coloring Edges on Tree _atcoder.jp] 题意：

灰太狼/ 2024年03月16日 14:41/ 0 赞/ 13 阅读

相关 AtCoder ABC 128D equeue

题目链接：[https://atcoder.jp/contests/abc128/tasks/abc128\_d][https_atcoder.jp_contests_abc1

ゝ一世哀愁。/ 2021年11月01日 06:18/ 0 赞/ 199 阅读