• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

CodeForces – 1438E Yurii Can Do Everything(暴力)

互联网 diligentman 1周前 (11-21) 7次浏览

题目链接:点击查看

题目大意:给出一个长度为 n 的序列,求出满足下列条件的区间个数:

  1. l + 1 <= r – 1 ,即区间长度大于等于 3
  2. a[ l ] ^ a[ r ] = a[ l + 1 ] + … + a[ r – 1 ]

题目分析:首先一个结论是,这样的区间并不是很多,所以暴力去查找即可,假设确定了左端点 l 后,假设其最高位为 highbit ,那么区间和的大小只要是小于等于 ( 1 << highbit + 1 ) 的都是有可能满足条件的区间,枚举左端点扫一遍,再枚举右端点扫一遍,记得去重

下面简单论证一下时间复杂度,对于每个点作为右端点来说,其最多被两个 最高位为 k 的左端点所扫到,因为如果有三个及以上的,最高位为 k 的左端点扫到的话,那么 3 * 2^k > 2^(k+1),已经不满足上一段的约束条件了,所以该做法的时间复杂度为 nlog(max(a[ i ]))

代码:
 

//#pragma GCC optimize(2)
//#pragma GCC optimize("Ofast","inline","-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
using namespace std;
 
typedef long long LL;
 
typedef unsigned long long ull;

const int inf=0x3f3f3f3f;

const int N=2e5+100;

LL a[N];

set<pair<int,int>>st;

int highbit(int x)
{
	int cnt=0;
	while(x)
	{
		cnt++;
		x>>=1;
	}
	return cnt+1;
}

int main()
{
#ifndef ONLINE_JUDGE
//  freopen("data.in.txt","r",stdin);
//  freopen("data.out.txt","w",stdout);
#endif
//  ios::sync_with_stdio(false);
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%lld",a+i);
	int ans=0;
	for(int l=1;l<=n;l++)
	{
		int r=l+1;
		LL sum=0,limit=(1LL<<highbit(a[l]));
		while(r+1<=n&&sum<=limit)
		{
			sum+=a[r++];
			if((a[l]^a[r])==sum)
			{
				ans++;
				st.emplace(l,r);
			}
		}
	}
	for(int r=n;r>=1;r--)
	{
		int l=r-1;
		LL sum=0,limit=(1LL<<highbit(a[r]));
		while(l-1>=1&&sum<=limit)
		{
			sum+=a[l--];
			if((a[l]^a[r])==sum&&!st.count(make_pair(l,r)))
				ans++;
		}
	}
	printf("%dn",ans);









    return 0;
}

 


喜欢 (0)