毒瘤xor-------前缀和+贪心

毒瘤xor

https://ac.nowcoder.com/acm/problem/18979

对于一个区间[L,R],对于X二进制下的每一位,如果第i位1,那么对总和的贡献就是[L,R]中的元素第i位是0的元素个数,反之,所以对于X的每一位i的取值依赖于[L,R]中所有元素该位中0,1的数量,如果1居多,那我们就设置0,得到的总和就会大一点,否则就设置1,前缀和预处理一下即可。

#include <cctype>
#include <cfloat>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <istream>
#include <iterator>
#include <list>
#include <map>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#define ll long long
#define pll pair<long long, long long>
#define P pair<int, int>
#define PP pair<P, P>
#define eps 1e-10
#define PI 3.1415926535898
#define It set<node>::iterator
using namespace std;
inline ll Read() {
    ll num=0;
    char ch=getchar();
    while (!isdigit(ch)) ch=getchar();
    while (isdigit(ch)) {
        num=num*10+ch-'0';
        ch=getchar();
    }
    return num;
}
const int maxn=1e5+10;
int val[maxn][31];
int main() {
    int n=Read();
    for (int j=1; j<=n; j++) {
        ll num=Read();
        for (int i=0; i<=30; i++) {
            val[j][i]=val[j-1][i];
            if ((num>>i)&1) val[j][i]++;
        }
    }
    int m=Read();
    while (m--) {
        int l=Read();
        int r=Read();
        if (l>r) swap(l,r);
        ll ans=0;
        int sum=r-l+1;
        for (int i=0; i<=30; i++) {
            int cnt=val[r][i]-val[l-1][i];
            if (cnt*2>=sum) continue;
            ans|=(1ll<<i);
        }
        printf("%lld\n",ans);
    }
    return 0;
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-24 12:26
点赞 评论 收藏
分享
Lorn的意义:你这种岗位在中国现在要么牛马天天加班,要么关系户进去好吃好喝,8年时间,真的天翻地覆了,对于资本来说你就说一头体力更好的牛马,哎,退伍没有包分配你真的亏了。
点赞 评论 收藏
分享
07-09 20:50
门头沟学院 Java
码农索隆:1.教育背景和荣誉证书合二为一。 2.获奖项目理一遍,你做了什么,对你求职的岗位有什么帮助,没有就删掉。 3.技能特长和教育背景交换位置。 4.技能特长写的太差,上网上找简历参考。都不用问你别的,一个redis就能把你问住,写写你具体会redis哪些方面的知识。
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-21 13:38
8月实习会变多吗现在还没找到实习该怎么办...回复的hr好少
码农索隆:3-4月就要开始找,基本上6月份就发offer,7月初已经开始暑期实习了。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务