C/C++教程

【题解】CF1438E Yurii Can Do Everything

本文主要是介绍【题解】CF1438E Yurii Can Do Everything,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

我的垃圾做法好像和别人有些不同,分享一下。

题目传送门:luogu,CF。

规定:记序列 \(s\) 表示序列 \(a\) 的前缀和,\(highbit(x)\) 表示数 \(x\) 的最高位,序列 \(a\) 值域为 \(m\)。

首先考虑枚举一个端点找答案,不妨枚举 \(l\),然后寻找枚举 \(r\) 的性质来减少枚举。

考虑左端点 \(l\),不难发现对于一个 \(l\) 之后最小的位置 \(k\) 满足 \(highbit(s_k-s_l)>highbit(a_l)\),\(k\) 之后的所有位置 \(j\) 若要作为右端点 \(r\),因为 \(a_l\) 的第 \(highbit(s_{j-1}-s_l)\) 位必然为 \(0\),所以 \(j\) 必须满足 \(highbit(a_j) \geq highbit(s_{j-1}-s_l)\),这时,对于 \(j\) 后的每一个位置 \(j'\),显然 \(highbit(s_{j'-1}-s_l)\) 大于 \(highbit(s_{j-1}-s_l)\),而 \(highbit\) 至多增大到 \(\log_2 m\),所以 \(k\) 后满足条件的右端点数量最多只有 \(\log m\) 个。根据这个结论,只要对于每个位置预处理它后面第一个 \(highbit(a_j)\) 大于某个位的位置 \(j\),即可将对满足 \(r>k\) 的右端点 \(r\) 的枚举优化到 \(O(n\log_2 m)\) 的复杂度。

然后考虑 \(r\leq k\) 的情况,直接暴力做复杂度就是对的,别的题解里都有这部分的证明,我就不再赘述。

时空复杂度均为 \(O(n\log_2 m)\),代码见下:

#include<bits/stdc++.h>
using namespace std;
#define re register
typedef double db;
typedef long long ll;
inline int win(){
	int x=0,w=0;char c=getchar();
	while(c>'9'||c<'0') w|=c=='-',c=getchar();
	while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return w?-x:x;
}

const int N=202020;
int p[N][31];ll a[N],s[N];

signed main(){
	int n=win(),ans=0;
	for(re int i=1;i<=n;++i) a[i]=win(),s[i]=a[i]+s[i-1];
	for(re int j=0;j<30;++j) p[n][j]=n+1;
	for(re int i=n,l;i>=1;--i){
		l=63-__builtin_clzll(a[i]);
		for(re int j=0;j<=l;++j) p[i-1][j]=i;
		for(re int j=l+1;j<30;++j) p[i-1][j]=p[i][j];
	}
	for(re int i=1,j,lmt;i<=n;++i){
		j=i+1,lmt=64-__builtin_clzll(a[i]);
		for(;j<n&&s[j]-s[i]<(1ll<<lmt);++j) if(s[j]-s[i]==(a[i]^a[j+1])) ++ans;
		if(j<n){
			lmt=63-__builtin_clzll(s[j]-s[i]),j=p[j][lmt];
			for(;j<=n&&lmt<=30;lmt=63-__builtin_clzll(s[j]-s[i]),j=p[j][lmt]) if((a[j]^a[i])==s[j-1]-s[i]) ++ans;
		}
	}
	printf("%d\n",ans);
	return 0;
}

这篇关于【题解】CF1438E Yurii Can Do Everything的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!