Codechef Chef and Easy Problem(智商)
2018-07-11 03:30:46来源:博客园 阅读 ()
Read problems statements in Mandarin chinese, Russian 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
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$
#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); } }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- C++ rand函数 2020-06-10
- Android P HIDL demo代码编写 (原创) 2020-05-07
- C++ STL框架 2020-03-29
- AtCoder Grand Contest 043--A - Range Flip Find Route 2020-03-22
- 在Android平台使用SNPE应链接libc++库 2020-03-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash