[CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!)] E 补题
题意：
长度为n的数组里面，最后要把n个数分为几个区间，确保每一个数字都在一个区间里面，但是区间的数目是任意的。最后的结果是所有区间的\(MEX\)的异或结果。输出可以达到的最大值。
\(n<=5000\)
思路：
- \(O(n^3)\)做法：
\(dp[i][j]\)表示在前i个数，里面，且以i为结尾的时候最后能否构造出结果为j？
每一个状态\(5000*5000\)再枚举下一个区间末尾的位置\(5000\)个，进行更新，最后是\(n^3\);. - 考虑优化：
- 官方题解里面有这样一句话： $if\ there\ exist\ l2 \ and\ r2 (l≤l2≤r2≤r) \(并且\)MEX(l,r)=MEX(l2,r2)$那么就可以只更新[l2,r2]对答案产生的影响而不去更新[l,r]对答案产生的影响。
- 现在我们再推理一个新的位置的时候往前进行遍历，记录当前往前面延伸到位置为j的时候此时的mex值是否已经出现过\(vis[j][mex]\)，如果已经出现过，之后就不需要进行更新了。
- \(DP\)的转移有两种方式，第一种是从当前状态推理出来之后的状态，第二种是到达现在，然后去看前面的能够推来出来自己的东西存不存在.就比如这和个题目。
代码：
void solve(){
int n; cin>>n;
vector< vector<int> >dp(n+1,vector<int>(n+1));
vector< vector<int> >vis(n+1,vector<int>(n+1));
for(int i=1;i<=n;i++){
cin>>a[i];
}
dp[0][0]=1;
for(int i=1;i<=n;i++){
dp[i]=dp[i-1];
vector<int>v(n+2);
int mex=0;
for(int j=i;j>=1;j--){
v[a[j]]=1;
if(v[mex]){
while(v[mex]) mex++;
if(vis[j][mex]) continue;
vis[j][mex]=1;
for(int k=0;k<=j;k++){
if(dp[j-1][k]) dp[i][k^mex]=1;
}
}
}
}
int ans=0;
for(int i=n;i>=0;i--){
if(dp[n][i]) {
ans=i; break;
}
}
cout<<ans<<"\n";
}