【每日一题】8月25日题目精讲 XOR-pyramid

可以发现,
f([l,r])
迭代到倒数第二层，会变成
f(f([l,r−1]),f([l+1,r]))=f([l,r−1])⊕f([l+1,r])

#include<iostream>
#include<string>
#include<math.h>
#include<algorithm>
#include<vector>
//#include<bits/stdc++.h>
typedef long long ll;
ll gcd(ll a, ll b)
{
    return b ? gcd(b, a % b) : a;
}
ll lcm(ll a, ll b) {
    return a * b / (gcd(a, b));
}
#define PII pair<int,int>
using namespace std;
const int N = 2e6 + 10, mod = 1e9 + 7;
int qmi(int a, int k, int p)        //快速幂模板
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = (ll)res * a % p;
        k >>= 1;
        a = (ll)a * a % p;
    }
    return res;
}
//////////////////////////////////////////////////////////
int n, q, f[5010][5010], ans[5010][5010];  //f[i][j]储存f(ai~aj)的值 
int k, l, r;
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> f[i][i];
        ans[i][i] = f[i][i];
    }
    for (int i = 2; i <= n; ++i) 
        for (int j = 1; j <= n - i + 1; ++j) {  
            k = j + i - 1;  
            f[j][k] = f[j][k - 1] ^ f[j + 1][k];
            ans[j][k] = max(ans[j][k - 1], ans[j + 1][k]);
            if (f[j][k] > ans[j][k]) ans[j][k] = f[j][k];
        }
    cin >> q;
    for (int i = 1; i <= q; i++) {
        cin >> l >> r;
        cout << ans[l][r] << endl;
    }
    return 0;
}

转化成区间dp的问题