題意：
找到一個區間，使得這個區間和為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;
}如果題解讓你的思路清晰一些的話別忘了點個關注再走喔！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/385510.html
標籤：其他