codeforces 983B XOR-pyramid

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

题意：

定义一个函数f(a):

给出一个数组a，有q个询问，每次询问回答在l到r的区间内，连续子串的f函数的最大值。

思路：

画图，来自codeforces SheepRanger

由此图可知，f(l,r) = f(l,r-1) ^ f(l+1,r)，多画图哇！

所以就变成了区间dp，同时维护f(l,r)与ans(l,r)：

f[l][r] = f[l][r-1] ^ f[l+1][r]

ans[l][r] = max(f[l][r],ans[l][r-1],ans[l+1][r])。

代码：

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = ;
int dp[N][N];
int a[N];
int ans[N][N];
int main()
{
int n;
scanf("%d",&n);
for (int i = ;i < n;i++) scanf("%d",&a[i]);
for (int i = ;i < n;i++) dp[i][i] = ans[i][i] = a[i];
for (int i = ;i < n;i++)
{
for (int j = ;j < n;j++)
{
int l = j,r = j+i;
if (r >= n) break;
//if (l == 0 && r == 5) puts("gg");
dp[l][r] = dp[l][r-] ^ dp[l+][r];
ans[l][r] = max(ans[l][r-],ans[l+][r]);
ans[l][r] = max(ans[l][r],dp[l][r]);
}
}
int q;
scanf("%d",&q);
while (q--)
{
int l,r;
scanf("%d%d",&l,&r);
l--,r--;
printf("%d\n",ans[l][r]);
}
return ;
}