【题目描述】
有一个长度为 n 的自然数序列 a，要求将这个序列恰好分成至少 m 个连续子
段。 每个子段的价值为该子段的所有数的按位异或。要使所有子段的价值按位与
的结果最大，输出这个最大值。
【输入描述】
第一行一个正整数 q，表示询问组数。
接下来 q 组输入，每组输入两行：
第一行两个正整数 n,m。
第二行 n 个正整数，描述序列 a。
【输出描述】
一行一个正整数，表示答案。
【输入样例】
1
5 3
1 2 3 4 5
【输出样例】
1
【数据范围】
20%的数据：n<=20
40%的数据：n<=100,ai<256
60%的数据：n<=100
100%的数据：1<=q<=12,1<=m<=n<=1000,0<=ai<2^30
题意：
q组数据。
给你一个长为n的非负数序列a。
定义一个区间的权值为区间的异或和。
定义一个划分的权值为分出的区间的权值的按位与的值。
要求至少把序列分成m个非空字段,求满足条件的划分的最大权值。
题解：
因为异或运算具有交换律且（x异或x = 0）,所以区间异或和可以由两个前缀异或和异或得到。
考虑从高位到低位确定答案的二进制位,然后考虑判断是否能分成至少m段。
如何判断是否能分成至少m段?
"能分成至少m段"与"最多能分成的段数>=m"等价。
令dp[i] = "a[1..i]这一段数最多能分成多少段"
转移就是直接枚举上一段的末尾j,如果[j+1,i]可以组成一段,那么就把dp[i] = max(dp[i],dp[j] + 1);
这样DP的复杂度是O(n^2)。
总复杂度就是O(q * log(值域) * DP) = O(30qn^2) ≈ 3.6 * 10^8,因为常数较小可以过。
值得一提的是,直接O(N^3)DP是错误的。因为它不满足最优子结构。
代码：
#include<bits/stdc++.h> using namespace std; typedef long long LL; int q,n,m,ans,x,s[1005],f[1005]; int rd(){ int re=0,f=1;char c=getchar(); while ((c<'0')||(c>'9')) {if (c=='-') f=-f;c=getchar();} while ((c>='0')&&(c<='9')) {re=re*10+c-'0';c=getchar();} return re*f; } int Max(int x,int y){ return ((x>y)?x:y); } int main(){ freopen("b.in","r",stdin); freopen("b.out","w",stdout); q=rd(); for (;q>0;--q){ n=rd();m=rd(); s[0]=0; for (int i=1;i<=n;++i){ x=rd();s[i]=s[i-1]^x; } ans=0; for (int i=29;i>=0;--i){ memset(f,0,sizeof(f)); f[0]=1; for (int j=1;j<=n;++j){ for (int k=0;k<j;++k) if (f[k]>0){ x=s[j]^s[k]; if (((ans&x)>=ans)&&((x&(1<<i))>0)) f[j]=Max(f[k]+1,f[j]); } } if (f[n]>m) ans|=(1<<i); } cout<<ans<<'\n'; } return 0; }