2019西北工业大学程序设计创新实践基地春季选拔赛(重现赛)-G（DP）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了2019西北工业大学程序设计创新实践基地春季选拔赛(重现赛)-G（DP），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1035字，纯文字阅读大概需要2分钟。

内容图文

题目链接：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\n",dp[n]);
22     return 0;
23 }

 

内容总结

以上是互联网集市为您收集整理的2019西北工业大学程序设计创新实践基地春季选拔赛(重现赛)-G（DP）全部内容，希望文章能够帮你解决2019西北工业大学程序设计创新实践基地春季选拔赛(重现赛)-G（DP）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---