[原创]华中农业大学第五届程序设计大赛 H MathematicalGame [01字典树]【字典树】
[原创]华中农业大学第五届程序设计大赛 H MathematicalGame [01字典树]【字典树】
2017-05-26 21:55:54 Tabris_ 阅读数:467
博客爬取于2020-06-14 22:40:31
以下为正文
版权声明:本文为Tabris原创文章,未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/72773955
题目链接:http://acm.hzau.edu.cn/problem.php?id=1206
——————————————————————————————————————
1206: MathematicalGame
Time Limit: 2 Sec Memory Limit: 1280 MB
Submit: 170 Solved: 26
[Submit][Status][Web Board]
Description
Xiao Ming likes to play mathematical games very much. One day, he gets a sequence of n positive integers. XOR (l , r) is defined as the XOR and of all numbers in a continuous interval. Now, Xiao Ming wants to know the intervals which make the XOR (l , r) become largest.
Require l, r.
Input
There is an integer T at the first line, indicate the case of data.
In each case, there is an integer N at the first line, indicate the length of the sequence. And there are N integers, a1, a2, … , an, at the second line. (N <= 1,000,000)
Output
In each case, the first line is “Case #k:”, k is the number of test cases, the next line includes two integers l and r, which separated by a space.
l, r output in lexicographic order if there are multiple results.
Sample Input
1
5
1 2 3 4 5
Sample Output
Case #1:
3 4
————————————————————————————————————————
题目大意:
问你区间异或值最大的区间是多少,如果值有多个,输出字典序最小的那个
解题思路:
相信大家都会 区间内选两个值,异或最大
那么这个也一样,只要维护的是前缀异或和就好了,这样就变成了经典问题。
然后维护结果就好了
附本题代码
——————————————————————————————————
1 | # include <bits/stdc++.h> |