社区讨论

求问两种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 条回复,欢迎继续交流。

正在加载回复...