2019西北工业大学程序设计创新实践基地春季选拔赛(重现赛)-G（DP）
题目链接：https://ac.nowcoder.com/acm/contest/553/G
题意：给定n,k，(1<=n<=5e5)然后给出n个数ai(1<=ai<=1e5)，问按顺序从1..n分组，最多能有多少个组的异或和为k。
思路：自然的，我们用dp[i]表示到第i个人的时候最多有多少个组的异或和为k。计算dp[i]时，有两种情况，要么在第i个人后面分出一组，要么不分。不分的话dp[i]=dp[i-1]就可以了; 如果分得话，就要找到上一个组的终点下标，我们可以计算到第i个人时的异或和sum，显然可由此得到上一个组终点处的sum‘，sum’=sum^k，所以我们用一个数组pre[j]表示sum为j时的最后一个下标（初始化为-1），最后的dp[n]即为所求。
AC代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 const int maxn=500005; 5 int n,k,dp[maxn],sum,pre[maxn]; 6 7 int main(){ 8 memset(pre,-1,sizeof(pre)); 9 pre[0]=0; 10 scanf("%d%d",&n,&k); 11 int tmp; 12 for(int i=1;i<=n;++i){ 13 scanf("%d",&tmp); 14 sum^=tmp; 15 if(pre[sum^k]!=-1) 16 dp[i]=max(dp[i-1],dp[pre[sum^k]]+1); 17 else 18 dp[i]=dp[i-1]; 19 pre[sum]=i; 20 } 21 printf("%d ",dp[n]); 22 return 0; 23 }