[CF983B]XOR-pyramid

题面传送门

离线做,预处理$ans[i][j]$表示$(i,j)$之间的答案。

可能只有我这个蒟蒻看题看了半天

(找规律大法好)

我们直接设$f[i][j]$为$ (i,j) $这一段的f函数的值。

因为我们显然发现这个大区间是由小区间贡献而来的。

直接枚举一个长度,然后做区间DP;

f[i][j]转移怎么做呢?

画图或者严谨这么都可以,懒得写了。(最关键的)(雾

$f[i][j]=f[i][j-1]$ xor $f[i+1][j];$

然后统计答案就是按照区间DP的正常操作:

$ans[i][j]=max(ans[i][j-1],ans[i+1][j]),f[i][j]);$

code

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<queue>
#include<set>
#define ri register int
using namespace std;
template <class T> void in(T &x) {
    x=0;
    bool flag=0;
    char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-')
            flag=1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=(x<<3)+(x<<1)+(c^48);
        c=getchar();
    }
    if(flag)
        x=-x;
}
int n,q,l,r;
int ans[6000][6000];
int f[6000][6000];
int main() {
    in(n);
    for(ri i=1; i<=n; ++i)
        in(f[i][i]),ans[i][i]=f[i][i];
    for(ri l=1; l<=n; ++l)
        for(ri i=1; i<=n; ++i) {
            int j=i+l;
            if(j>n) continue;
            f[i][j]=f[i][j-1]^f[i+1][j];
            ans[i][j]=max(max(ans[i][j-1],ans[i+1][j]),f[i][j]);
        }
    in(q);
    for(ri i=1; i<=q; ++i) {
        in(l),in(r);
        printf("%d\n",ans[l][r]);
    }
    return 0;
}

发表于 2018-09-20 15:47:50 in 题目