Molly‘s Chemicals (前缀和+map用法,直接对应答案)

题意:

找到一个区间,使得这个区间和为k的次方倍

题解:

很容易想到用前缀和

然后求满足这个条件的式子,满足一次,答案增加一次

presum[i]-presum[j]=k^x;

但是如果我们直接去枚举,怎么可能不超时?

所以直接pass掉

但我们可以把这个式子改一下,改成这样

presum[i]=k^x+presum[j];

先把这个题拆分成几个部分,第一个,求k^x,这个可以直接打表:

	for(int i=1;i<=64;i++){
		excel[0]=1;
		if(excel[i-1]<inf) excel[i]=excel[i-1]*k;

第二个部分就是求它的对应

k^x+presum[j]有多少个

这个部分可以把presume[i-1]+excel[j]就是每一个i-1对应的所有j的和存到map里面,如果后面presum[i]有的话,就直接存进去了,然后再后面查就好了,如果是-1/1就没必要遍历那么多次,每次一存直接跑路就好

for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		for(int j=0;j<=64&&excel[j]<inf;j++){
			if(k==1||k==-1){
				if(k==-1) mp[presum[i-1]-1]++;
				mp[presum[i-1]+1]++;
				break;
			}
			else{
				mp[presum[i-1]+excel[j]]++;
			}
		}
		presum[i]=presum[i-1]+a[i];
		ans += mp[presum[i]];
	}

-1的情况要特判一下吗?

为啥直接存presum[i-1]-1和presum[i-1]+1???

因为就这两种情况,后面搜索都有就行了(j有64次呢)

ac代码:

#include <iostream>
#include <algorithm>
#include <cmath>
#include <map>
#include <string.h>
typedef long long ll;
using namespace std;
const int maxn = 1e5+10;
const ll inf = 1e15 + 10;
ll presum[maxn],a[maxn];
ll excel[maxn];
/*
首先用前缀和存数组,然后再
presum[j]-presum[i]=k^n;
k^n我打算用快速幂打表存储
presum[j]-presum[i]就看
需要用map,哪一部分???
*/
//unmap<ll ll>mp;
map<ll,ll>mp;

ll ksm(ll a,ll b){
	ll ans = 1;
	for(;b>0;b /=2 , a*= a){
		if(b % 2 != 0){
			ans *= a;
		}
	}
	return ans;
}

int main() {
	int n,k;
	ll ans=0;
	mp.clear();
	memset(excel, 0, sizeof(excel));
	memset(presum, 0, sizeof(presum));
	memset(a, 0, sizeof(a));
	scanf("%d%d",&n,&k);
	for(int i=1;i<=64;i++){
		if(excel[i-1]<inf) excel[i]=ksm(k,i);
	}
	
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		for(int j=0;j<=64&&excel[j]<inf;j++){
			if(k==1||k==-1){
				if(k==-1) mp[presum[i-1]-1]++;
				mp[presum[i-1]+1]++;
				break;
			}
			else{
				mp[presum[i-1]+excel[j]]++;
			}
		}
		presum[i]=presum[i-1]+a[i];
		ans += mp[presum[i]];
	}
	printf("%lld",ans);
	return 0;
}

如果题解让你的思路清晰一些的话别忘了点个关注再走喔!

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>