【每日一题】8月25日题目精讲 XOR-pyramid
@[toc]
题目描述：
链接：https://ac.nowcoder.com/acm/problem/112798
来源：牛客网
输入描述:
输出描述:
Print q lines — the answers for the queries.
示例1
输入
复制
3 8 4 1 2 2 3 1 2
输出
复制
5 12
示例2
输入
复制
6 1 2 4 8 16 32 4 1 6 2 5 3 4 1 2
输出
复制
60 30 12 3
备注:
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 $$
$
$
$
$
$
$
$$.
题解：
我们要先摸索出f的规律
f(i,j)=f(i,j-1) xor f(i+1,j)
dp[l][r]为区间[l,r]的最大值
dp[l][r]=max(f(l,r),dp[l][r−1],dp[l+1][r])
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5030;
ll a[maxn];
ll dp[maxn][maxn];
ll res[maxn][maxn];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
res[i][i]=dp[i][i]=a[i];
}
int q;
cin>>q;
for (int len = 2; len <= n; len++) {
for (int l = 1; l + len - 1 <= n; l++) {
int r = l + len - 1;
dp[l][r] = dp[l + 1][r] ^ dp[l][r - 1];
res[l][r] = max({dp[l][r], res[l + 1][r], res[l][r - 1]});
}
}
for(int i=1;i<=q;i++)
{
int l,r;
cin>>l>>r;
printf("%d\n",res[l][r]);
}
return 0;
}
/*
1 2 4 8
f(1,4)=f(1,3) xor f(2,4)
f(1,3)=f(1,2) xor f(2,3)
1 2 4
f(1 xor 2, 2 xor 4)
f(1,2)=f(1,1) xor f(2,2)
*/
//f(i,j) = f(i, j-1) xor f(i+1,j) 
