time limit per test
2 seconds
memory limit per test
- 512 megabytes
- input
- standard input
- output
- standard output
- For an array
- b
- b of length
- m
m we define the function
- ff as
- f(b)={b[1]if m=1f(b[1]b[2],b[2]b[3],...,b[m1]b[m])otherwise,f(b)={b[1]if m=1f(b[1]b[2],b[2]b[3],...,b[m1]b[m])otherwise,
- where
- is bitwise exclusive OR https://en.wikipedia.org/wiki/Bitwise_operation#XOR .
- For example, f(1,2,4,8)=f(12,24,48)=f(3,6,12)=f(36,612)=f(5,10)=f(510)=f(15)=15f(1,2,4,8)=f(12,24,48)=f(3,6,12)=f(36,612)=f(5,10)=f(510)=f(15)=15
You are given an array aa and a few queries. Each query is represented as two integers ll and rr. The answer is the maximum value of
f
fon all continuous subsegments of the array
- a
- l
- ,
- a
- l
- +
- 1
- ,
- ...
- ,
aral,al+1,...,ar.
Input
The first line contains a single integer
- n
- n (
- 1
- n
- 5000
- 1n5000) - the length of
aa.
- The second line contains
- n
- n integers
- a
- 1
- ,
- a
- 2
- ,
- ...
- ,
- a
- n
- a1,a2,...,an (
- 0
- a
- i
- 2
- 30
10ai2301) - the elements of the array.
The third line contains a single integer
q
q (
1
q
1000001q100000) - the number of queries.
- Each of the next
- q
q lines contains a query represented as two integers
- l
- l,
- r
- r (
- 1
- l
- r
n1lrn).
Output
qq lines - the answers for the queries.
- Examples
- input
- Copy
- 3
- 8 4 1
- 2
- 2 3
- 1 2
- output
- Copy
- 5
- 12
- input
- Copy
- 6
- 1 2 4 8 16 32
- 4
- 1 6
- 2 5
- 3 4
- 1 2
- output
- Copy
- 60
- 30
- 12
- 3
- Note
- In first sample in both queries the maximum value of the function is reached on the subsegment that is equal to the whole segment.
- In second sample, optimal segment for first query are [3,6][3,6], for second query - [2,5][2,5], for third - [3,4][3,4], for fourth -
- [
- 1
- ,
- 2][1,2].
这题就是在异或操作下的区间最大值.
n=5000 可以用区间 DP 做.
dp[i][j] 表示长度为 i 起始点是 j 的区间最大值.
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long LL ;
- const int maxn = 5e3 + 7;
- int dp[maxn][maxn];
- int main() {
- int n;
- scanf("%d", &n );
- for (int i = 1 ; i <= n ; i++)
- scanf("%d", &dp[1][i]);
- for (int i = 2 ; i <= n ; i++ )
- for (int j = 1 ; j <= n - i + 1 ; j++)
- dp[i][j] = dp[i - 1][j] ^ dp[i - 1][j + 1];
- for (int i = 2 ; i <= n ; i++)
- for (int j = 1 ; j <= n - i + 1 ; j++)
- dp[i][j] = max(dp[i][j], max(dp[i - 1][j], dp[i - 1][j + 1]));
- int q;
- scanf("%d", &q);
- while(q--) {
- int x, y;
- scanf("%d%d", &x, &y);
- int len = y - x + 1;
- printf("%d\n", dp[len][x]);
- }
- return 0;
- }
来源: https://www.cnblogs.com/qldabiaoge/p/9049908.html