前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >CodeForces 626 DIV.2 D Present

CodeForces 626 DIV.2 D Present

作者头像
ShenduCC
发布2020-03-23 17:22:55
3160
发布2020-03-23 17:22:55
举报
文章被收录于专栏:算法修养

题目

题解: 现场想到了从结果的二进制的每一位考虑,每一位都是由比它低的低位决定的,但是规律没找好。 举个例子,结果的二进制的第3位(从0位开始)上是否为1,是由0 到 2^4-1 之间的数决定,就是 0000 - 1111 之间所有数两两相加决定的,所以数组要先对2^4取余。 而相加的结果,只有在1000 到 1111 ,也就是8~15之间,才会让第3位为1,统计为1的结果若是奇数,则最终结果的第三位上就是1,否则为0 对 0 来说,和1000-1111 任意的数字相加,都会让第3位为1 对 0001 来说,和0111- 1110之间的任意数字相加,也满足条件 0010 ~ 0110-1101 ... 1111 ~ 0000-0000 和 1001~1111 总的来说,考虑第3位,对任意的x(x在0~2^4-1之间), 就是看看在[2^3-x ~ 2^4-x]和[2^4-1+2^3-x,2^4-1]两个区间里有多少个数字。求区间和,可以用树状数组。 考虑第k为,对于任意的x(x在0~2^(k+1)-1 之间),统计[2^k-x,2^(k+1)-x] 和 [2^(k+1)+2^k -x-1,2^(k+1)-1] 这两个区间的和. 因为数组里数字的范围是10^7,任意两个数字之和最大是2*10^7,所以我最多考虑到第24位,2^24。

代码语言:javascript
复制
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <math.h>

using namespace std;

#define MAX (int)4e5+5
#define MAX2 (1<<25)
int a[MAX];
int c[MAX2+5];
int lowbit(int x)
{
    return x&(-x);
}
void Add(int pos,int len,int x)
{
    while(pos<=len)
    {
        c[pos]+=x;
        pos+=lowbit(pos);
    }
}
int sum(int pos)
{
    if(pos<=0)
        return 0;
    int res=0;
    while(pos>0)
    {
        res+=c[pos];
        pos-=lowbit(pos);
    }
    return res;
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }

    int ans=0;
    int num=1;
    for(int i=0;i<25;i++)
    {
        num<<=1;
        memset(c,0,num*sizeof(int));
        int res=0;
        for(int j=0;j<n;j++)
        {
            int x = a[j]%num;
            int xx = sum((num-1)-x+1);
            int yy = sum((num>>1)-x);

            res+= xx-yy;

            if(x>num>>1) {

                xx = sum(num);
                yy = sum(num-(x-(num>>1)));
                res+=xx-yy;
            }

            if(res&1)
            {
                res=1;
            }
            else
                res=0;

            Add(x+1,num,1);
        }

        if(res&1)
            ans |= (1<<i);
    }

    printf("%d\n",ans);

    return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020-03-21 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档