codeforces 1058E (思维)

迈不过友情╰ 2022-05-10 12:56 157阅读 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 条评论，157人围观）

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

相关阅读

相关 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 赞/ 111 阅读

相关 CodeForces - 612E （置换群）

E. Square Root of Permutation time limit per test 2 seconds memory limit per test 25

本是古典何须时尚/ 2022年05月29日 12:10/ 0 赞/ 162 阅读

相关 Codeforces 976E 题解报告

一、题目 [http://codeforces.com/contest/976/problem/E][http_codeforces.com_contest_976_pr

朱雀/ 2022年05月25日 00:47/ 0 赞/ 160 阅读

相关 codeforces 1058E (思维)

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

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

相关 codeforces1187E

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

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

相关 Codeforces 353E 贪心

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

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

相关 Parking Lot CodeForces - 480E

大意: 给定01矩阵, 单点赋值为1, 求最大全0正方形. 将询问倒序处理, 那么答案一定是递增的, 最多增长$O(n)$次, 对于每次操作暴力判断答案是否增长即可, 也就是

r囧r小猫/ 2021年11月05日 22:50/ 0 赞/ 188 阅读

相关 Codeforces 1141E Superhero Battle

题目大意: 给出长度为\\(n\\)的序列\\(d\_i\\)和生命值\\(H\\),每次到达该位置后生命值更新为\\(H+d\_i\\),求\\(H\\)首次为

Bertha 。/ 2021年10月29日 10:12/ 0 赞/ 157 阅读

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

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

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

相关 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 赞/ 240 阅读