前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Codechef Chef and Easy Problem(智商)

Codechef Chef and Easy Problem(智商)

作者头像
attack
发布2018-07-27 15:16:01
2650
发布2018-07-27 15:16:01
举报
文章被收录于专栏:数据结构与算法

Read problems statements in Mandarin chineseRussian and Vietnamese as well.

You are given a sequence A1, A2, ..., AN and Q queries. In each query, you are given two parameters L and R; you have to find the smallest integer X such that 0 ≤ X < 231and the value of (AL xor X) + (AL+1 xor X) + ... + (AR xor X) is maximum possible.

Note: xor denotes the bitwise xor operation.

Input

  • The first line of the input contains two space-separated integers N and Q denoting the number of elements in A and the number of queries respectively.
  • The second line contains N space-separated integers A1, A2, ..., AN.
  • Each of the next Q lines contains two space-separated integers L and R describing one query.

Output

For each query, print a single line containing one integer — the minimum value of X.

Constraints

  • 1 ≤ N ≤ 105
  • 1 ≤ Q ≤ 105
  • 0 ≤ Ai < 231 for each valid i

Subtasks

Subtask #1 (18 points):

  • 1 ≤ N ≤ 103
  • 1 ≤ Q ≤ 103
  • 0 ≤ Ai < 210 for each valid i

Subtask #2 (82 points): original constraints

Example

代码语言:javascript
复制
Input:

5 3
20 11 18 2 13
1 3
3 5
2 4

Output:

2147483629
2147483645
2147483645

感觉codechef easy里面的都是智商题啊qwq。。

这题我们可以按位考虑。

如果当前为二进制下第$i$位,区间$(l, r)$中元素第$i$位含有$1$的有$x$个

很显然,当$x <= \frac{r - l + 1}{2}$时$0$的个数多,那么答案的第$i$位应为$1$,否则为$0$

代码语言:javascript
复制
#include<cstdio>
#define int long long 
using namespace std;
const int MAXN = 1e5 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, Q;
int a[MAXN], sum[32][MAXN];
 main() {
    N = read(); Q = read();
    for(int i = 1; i <= N; i++) a[i] = read();
    for(int j = 0; j <= 30; j++) 
        for(int i = 1; i <= N; i++) 
            sum[j][i] = sum[j][i - 1] + ((a[i] & (1 << j)) != 0);
    while(Q--) {
        int l = read(), r = read(), ans = 0;
        for(int i = 0; i <= 30; i++) 
            if(2 * (sum[i][r] - sum[i][l - 1]) < (r - l + 1))
                ans |= (1 << i);
        printf("%lld\n", ans);
    }
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018-07-10 ,如有侵权请联系 cloudcommunity@tencent.com 删除

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

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

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

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
  • Input
  • Output
  • Constraints
  • Subtasks
  • Example
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档