codeforces 1058E (思维)

迈不过友情╰ 2022-05-10 12:56 330阅读 0赞

[传送][Link 1]

题意：给n个数，每个数的二进制1都可以随意的换位置，问区间异或为0的有多少个

思路：该问题可以转化为他的充要条件：

1.区间1的个数为偶数

2.区间最大值不超过区间和的一半；

偶数区间个数可以用cnt\[i\]\[2\]记录以1开始，1~i中偶数和奇数区间个数，

那么偶数区间就是假如现在前缀是偶数，那就加cnt偶数，反之加奇数。

因为偶数=偶-偶/奇减奇

对于不符合的，因为数是60位左右，所以最大值不超过60，假如有一个数是60那么其他数至少为1，这样往前 遍历60来次

就足矣。

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N=3e5+10;
    int cnt[N][2], num[N];
    
    int main(){
        int n;
        //cout<<__builtin_popcount(1000000000000ll)<<endl;
        scanf("%d", &n);
    
        for(int i=1; i<=n; i++){
            ll t;
            scanf("%I64d", &t);
            //num[i]=__builtin_popcount(t);
            while(t){
                if(t&1) num[i]++;
                t>>=1;
            }
            //printf("%d ", num[i]);
        }
        //puts("");
        cnt[0][0]=1;
        ll ans=0, sum=0;
        for(int i=1; i<=n; i++){
            int s=0, mx=0;
            sum+=num[i];
            if(sum&1)
                ans+=cnt[i-1][1];
            else
                ans+=cnt[i-1][0];
            cnt[i][1]=cnt[i-1][1]+(sum&1);
            cnt[i][0]=cnt[i-1][0]+(sum%2==0);
            for(int j=i; j>0&&i-j+1<=63; j--){
                s+=num[j];
                mx=max(mx, num[j]);
                if(s%2==0 && mx>s-mx) ans--;
            }
        }
        printf("%I64d\n", ans);
    
        return 0;
    }

[Link 1]: http://codeforces.com/contest/1058/problem/E

发表评论取消回复

表情：

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

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

相关阅读

相关 codeforces 1178E-Archaeology

传送门：[QAQQAQ][] 题意：给你一个字符串，保证字符串中只包含有$ABC$三种字符，且两相邻字符不相同，求任意一个回文串，使回文串长度大于字符串长度一半（向下取整），

ゞ浴缸里的玫瑰/ 2023年06月05日 12:44/ 0 赞/ 99 阅读

相关 CodeForces1154E

[CodeForces1154E][] 题意就是有两个教练,每个教练轮流操作,每次操作会选取所有未被选取的学生中能力值最高的那一个并把这个学生向左向右各\\(k\\)个学生

落日映苍穹つ/ 2023年06月02日 11:58/ 0 赞/ 127 阅读

相关 @codeforces - 590E@ Birthday

目录 @description@ @solution@ @accepted code@ @details@ --------------------

今天药忘吃喽~/ 2023年06月01日 12:58/ 0 赞/ 141 阅读

相关 CodeForces 194E(math）

问题描述: Hamming distance between strings a and b of equal length (denoted by h(a, b)) is

偏执的太偏执、/ 2022年06月02日 05:12/ 0 赞/ 291 阅读

相关 codeforces 1058E (思维)

[传送][Link 1] 题意：给n个数，每个数的二进制1都可以随意的换位置，问区间异或为0的有多少个思路：该问题可以转化为他的充要条件： 1.区间1的个数为偶数 2

迈不过友情╰/ 2022年05月10日 12:56/ 0 赞/ 331 阅读

相关 codeforces1187E

题目链接：[http://codeforces.com/problemset/problem/1187/E][http_codeforces.com_problemset_pr

川长思鸟来/ 2021年12月13日 03:21/ 0 赞/ 286 阅读

相关 Codeforces 353E 贪心

题意：给你一张有向图，第i条边连接i号点和(i + 1) % n号点，问最多可以选择多少个点，使得这些点互相不可达。思路：容易发现，如果某个边的集合点的数目大于等于2，那么

妖狐艹你老母/ 2021年12月12日 02:04/ 0 赞/ 360 阅读

相关 CodeForces 926E Merge Equal Elements（思维模拟）

题意：开始有 n个数，然后如果最左边有相同的连续的数x我们要合并，合并之后之前两个数删除然后插入x+1，然后直到不能再合并，下标是左边那个的下标，输出最后结果。分析：

╰半夏微凉°/ 2021年10月18日 08:36/ 0 赞/ 363 阅读

相关 Codeforces1141E(E题）Superhero Battle

A superhero fights with a monster. The battle consists of rounds, each of which lasts ex

冷不防/ 2021年10月15日 04:25/ 0 赞/ 385 阅读

相关 CodeForces 1213A 【思维】题解

目录 1.0题目 2.0代码 1.0题目 zls有n个薯条，第i个薯条的位置在xi,一些薯条可能放在相同的位

快来打我*/ 2021年07月24日 18:53/ 0 赞/ 496 阅读