TOJ4114(活用树状数组)

TOJ指天津大学onlinejudge

题意:给你由N个数组成的数列,算出它们的所有连续和的异或和,比如:数列{1,2},则answer = 1 ^ 2 ^ (1 + 2) = 0。

这道题有几个关键点:

1.这道题要将十进制数换成二进制数,并且对这些二进制数按位计算,比如说上面的式子,我们将它列成竖式:

01

10

11

可以发现,对于第一位来说,一共有2个1,是偶数,异或值为0。answer += 0 * (1<<0)。对于第二位来说,一共有2个1,异或值为0,answer += 0 * (1<<1)。最终answer = 0;

2.Sum(i~j) = S[j] - S[i - 1]。     (S[0] = 0)      所以我们算式可以看成(S[1] - S[0]) ^ (S[2] - S[1]) ^ (S[2] - S[0]) ^ (S[3] - S[0]) ^ (S[3] - S[1]) ^ (S[3] - S[2]) ^ ..........

所以我们可以按块来看这些算式中的项,每一块就S[i]与S[i - 1]......S[0]做差得到的。

综上,我们计算异或和时,我们只需要预处理一下,算出每一个S[i],然后从头到尾扫n次,每一次计算出这些二进制数某一位一共有多少个1(就像上面所举例子一样),看看是偶数还是奇数,

如果是奇数,就answer += 1 * (1<<i)。

现在来说扫描时候的具体操作,假设我们现在已经计算完了S[1]....S[i]这些组成异或和的各项在某一位k的1的个数,在扫到S[i + 1]时,相当于又多了(S[i +1] - S[0]) ^ .......^ (S[i + 1] - S[i])这 i 项来统计,

我就只需要计算出S[i + 1]与前面各项S[ j ] (j属于[ 0 , i ]) 的差在这一位产生了多少个1,对于S[i + 1]与某一个S[ j ]来说,这取决于S[i + 1]和S[ j ]在这一位的值和S[i + 1]与S[ j ]在更低诸位上的大小关系。

在这里,我将S[i + 1]在这一位的值记为A1,更低的诸位统一记为B1,S[ j ]在这一位的值记为A2,更低诸位的统一记为B2。

1.当A1 == 1时,有两种情况可以产出一个1:

情况Ⅰ:A2 == 0,且B1 >= B2。

情况Ⅱ:A2 == 1,且B1 < B2(可以从前面借位来产生1,就像10 - 9 = 1这样)

2.当A1 == 0时,有两种情况可以产出一个1:

情况Ⅰ:A2 == 0,且B1< B2

情况Ⅱ:A2 == 1,且B1 >= B2。

由此可以看出,对于S[i + 1]与前面诸前缀和之差在某一位能产生多少个1,我只要知道S[ j ]比这一位低的诸位与S[i + 1]比这一位低的诸位之大小关系即可。

这个可以用树状数组来保存,树状数组的下标表示的是值域,BIT[ Bi ]中存的比这一位低的诸位B小于等于Bi的S[ k ]的个数,由于我们扫这一遍S[ i ]的目的就是为了计算特定的一位,

所以我们有多少位就扫多少次,扫完一次就清空一次树状数组。由于还跟S[ j ]在这一位的值有关,所以我们开两个树状数组,一个记录在这一位为1的S[i],一个则记录在这一位为0的S[j]。

对于每一个S[i]我们边算边存,如果S[i]在这一位为1,则存在BIT_1中;如果为0,则存在BIT_0中。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#define maxn 100005
#define maxn2 1000005
using namespace std;
int BIT_0[maxn2],BIT_1[maxn2];
int S[maxn];
int lowbit(int k)
{
    return (k & (-k));
}
void add(int v,int pos,int mmax,int a[])
{
    while(pos <= mmax){
        a[pos] += v;
        pos += lowbit(pos);
    }
}
int sum(int pos,int a[])
{
    int ret = 0;
    while(pos > 0){
        ret += a[pos];
        pos -= lowbit(pos);
    }
    return ret;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        memset(S,0,sizeof(S));
        int n;
        scanf("%d",&n);
        for(int i = 1;i <= n;++i){
            scanf("%d",&S[i]);
            S[i] += S[i - 1];
        }
        int temp = S[n];
        int len = 0;
        while(temp > 0){
            temp = temp>>1;
            ++len;
        }
        int answer = 0;
        for(int i = 0;i < len;++i){
            int cnt = 0;
            int cnt_0 = 0,cnt_1 = 0,mmax = (1<<i);
            for(int j = 0;j <= n;++j){
                int tail = S[j] % (1<<i);
                ++tail;
                int t_cnt = 0;
                if(S[j] & (1<<i)){
                    t_cnt += sum(tail,BIT_0);
                    t_cnt += (cnt_1 - sum(tail,BIT_1));
                    add(1,tail,mmax,BIT_1);
                    ++cnt_1;
                }
                else{
                    t_cnt += sum(tail,BIT_1);
                    t_cnt += (cnt_0 - sum(tail,BIT_0));
                    add(1,tail,mmax,BIT_0);
                    ++cnt_0;
                }
                cnt += t_cnt;
            }
            if(cnt & 1) answer += (1<<i);
            memset(BIT_0,0,sizeof(BIT_0));
            memset(BIT_1,0,sizeof(BIT_1));
        }
        printf("%d\n",answer);
    }
    return 0;
}

这里有一个小技巧,由于lowbit( )不好处理0,所以我把每一个tail都加1,(tail的取值最小就是0),这样sum(x)其实算的是tail在[0,x-1]之间的S[j]

本题启发:树状数组的下标用来表示值域

时间: 07-07

TOJ4114(活用树状数组)的相关文章

UVA_11525 树状数组的活用 二分

我们知道1——k有K!种排列,现在给定k和n,要你按字典序输出 第n种排列的数列 而且题目给的 n是 n=S1(k-1)!+S2(k-2)!+...+Sk-1*1!+Sk*0!(0=<Si<=k-i), k最大为50000,直接算出来不可能,我发现这个n的表达式很有意思,明显(k-1)!就是表示第一次除第一个以外,剩下k-1个数的排列个数,乘一个S1就说明之前用了多少次这种排列了,根据这个 再手算了一下,发现就是,每次找第Sk个数,输出,当然已经访问过的数就要T出去 这很明显就是树状数组 (或

BZOJ_5055_膜法师_树状数组+离散化

Description 在经历过1e9次大型战争后的宇宙中现在还剩下n个完美维度, 现在来自多元宇宙的膜法师,想偷取其中的三个维度为伟大的长者续秒, 显然,他能为长者所续的时间,为这三个维度上能量的乘积, 但目前的宇宙很不乐观,胡乱偷取可能造成维度的崩溃, 所以,他必须按逆序偷取这些维度,且在偷取中, 每次偷取的维度的能量必须严格小于他上次偷取的能量, 由于膜法师生活在多元宇宙,所以他可以让所有可能的偷取方案全部发生 题目描述 但他数学不好,所以找到了你帮他求出能为长者续几秒, 你要做的,就是在

HDU 5542 The Battle of Chibi dp+树状数组

题目:http://acm.hdu.edu.cn/showproblem.php?pid=5542 题意:给你n个数,求其中上升子序列长度为m的个数 可以考虑用dp[i][j]表示以a[i]结尾的长度为j的上升子序列有多少 裸的dp是o(n2m) 所以需要优化 我们可以发现dp的第3维是找比它小的数,那么就可以用树状数组来找 这样就可以降低复杂度 #include<iostream> #include<cstdio> #include<cstring> #include

(POJ 3067) Japan (慢慢熟悉的树状数组)

Japan Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 29295   Accepted: 7902 Description Japan plans to welcome the ACM ICPC World Finals and a lot of roads must be built for the venue. Japan is tall island with N cities on the East coas

【二维树状数组】See you~

https://www.bnuoj.com/v3/contest_show.php?cid=9148#problem/F [题意] 给定一个矩阵,每个格子的初始值为1.现在可以对矩阵有四种操作: A x y n1 :给格点(x,y)的值加n1 D x y n1: 给格点(x,y)的值减n1,如果现在格点的值不够n1,把格点置0 M x1 y1 x2 y2:(x1,y1)移动给(x2,y2)n1个 S x1 y1 x2 y2 查询子矩阵的和 [思路] 当然是二维树状数组 但是一定要注意:lowbi

Vijos P1066 弱弱的战壕【多解,线段树,暴力,树状数组】

弱弱的战壕 描述 永恒和mx正在玩一个即时战略游戏,名字嘛~~~~~~恕本人记性不好,忘了-_-b. mx在他的基地附近建立了n个战壕,每个战壕都是一个独立的作战单位,射程可以达到无限(“mx不赢定了?!?”永恒[email protected][email protected]). 但是,战壕有一个弱点,就是只能攻击它的左下方,说白了就是横纵坐标都不大于它的点(mx:“我的战壕为什么这么菜”ToT).这样,永恒就可以从别的地方进攻摧毁战壕,从而消灭mx的部队. 战壕都有一个保护范围,同它的攻击

CF 313 DIV2 B 树状数组

http://codeforces.com/contest/313/problem/B 题目大意 给一个区间,问你这个区间里面有几个连续相同的字符. 思路: 表示个人用树状数组来写的...了解了树状数组的本质就行了. 当然用sum[r]-sum[l]也是可以的

Hdu5032 极角排序+树状数组

题目链接 思路:参考了题解.对询问进行极角排序,然后用树状数组维护一下前缀和即可. /* ID: onlyazh1 LANG: C++ TASK: test */ #include<bits/stdc++.h> using namespace std; #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 typedef long long ll; const int maxn=1010; const int maxm=10

Curious Robin Hood(树状数组+线段树)

1112 - Curious Robin Hood    PDF (English) Statistics Forum Time Limit: 1 second(s) Memory Limit: 64 MB Robin Hood likes to loot rich people since he helps the poor people with this money. Instead of keeping all the money together he does another tri