CF 983B XOR

CF 983B XOR-pyramid（区间dp，异或）

若有一个长度为m的数组b，定义函数f为:

$f(b) = \begin{cases} b[1] & \quad \text{if } m = 1, \ f(b[1] \oplus b[2],b[2] \oplus b[3],\dots,b[m-1] \oplus b[m]) & \quad \text{otherwise} \end{cases}$

现在给出长度为n(n<=5000)的数组a，询问q(q<=100000)次，每次询问区间$[li,ri]$的子区间中，f的最大值。

可以发现,$f([l,r])$迭代到倒数第二层，会变成$f(f([l,r-1]),f([l+1, r]))=f([l, r-1])\oplus f([l+1, r])$。因此这个就变成区间dp水题了。

1#include <cstdio> 
2#include <algorithm>
3using namespace std;
4
5const int maxn=5005;
6int n, q, f[maxn][maxn], maxm[maxn][maxn];  //f[i][j]储存f(ai~aj)的值 
7
8int main(){
9	scanf("%d", &n); int k;
10	for (int i=1; i<=n; ++i){
11		scanf("%d", &f[i][i]); 
12		maxm[i][i]=f[i][i];
13	}
14	for (int i=2; i<=n; ++i)  //区间长度 
15		for (int j=1; j<=n-i+1; ++j){  //区间起点 
16			k=j+i-1;  //区间终点 
17			f[j][k]=f[j][k-1]^f[j+1][k];
18			maxm[j][k]=max(maxm[j][k-1], maxm[j+1][k]);
19			if (f[j][k]>maxm[j][k]) maxm[j][k]=f[j][k];
20		}
21	scanf("%d", &q); int l, r; 
22	for (int i=0; i<q; ++i){
23		scanf("%d%d", &l, &r);
24		printf("%d\n", maxm[l][r]);
25	}
26	return 0;
27}