社区讨论
求问两种DP写法有什么区别?
P14359[CSP-J 2025] 异或和参与者 2已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @mhqm5z0m
- 此快照首次捕获于
- 2025/11/09 02:24 3 个月前
- 此快照最后确认于
- 2025/11/16 14:07 3 个月前
100 pts
CPP#include<bits/stdc++.h>
using namespace std;
int n,k;
int dp[500010];
int a[500010];
int mxr[(1<<20)+10];
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
}
int s=0;
int mx=0;
memset(mxr,-1,sizeof mxr);
mxr[0]=0;
for(int i=1;i<=n;i++){
s^=a[i];
dp[i]=dp[i-1];
if(mxr[s^k]!=-1){
dp[i]=max(dp[i],dp[mxr[s^k]]+1);
}
mxr[s]=i;
}
cout<<dp[n]<<'\n';
return 0;
}
15pts
CPP#include<bits/stdc++.h>
using namespace std;
int n,k;
int dp[500010];
int a[500010];
int mxr[(1<<20)+10];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
}
int s=0;
int mx=0;
memset(mxr,-1,sizeof mxr);
mxr[0]=0;
for(int i=1;i<=n;i++){
s^=a[i];
if(mxr[s^k]!=-1){
dp[i]=max(dp[i],dp[mxr[s^k]]+1);
}
mxr[s]=i;
mx=max(mx,dp[i]);
}
cout<<mx<<'\n';
return 0;
}
回复
共 1 条回复,欢迎继续交流。
正在加载回复...