首页 > 代码库 > Codeforces Round #400 C. Molly's Chemicals

Codeforces Round #400 C. Molly's Chemicals

2024-09-05 23:10:43   220人阅读

题目链接：Codeforces Round #400 C. Molly‘s Chemicals

题意:

给你n个数，和一个数k，现在问你有多少个区间和等于k的r次方，r从0到无穷。

题解：

由于有负数的存在，不能用双指针，我们先把前缀和sum求出来。

现在就转换为要求有多少个sum[r]-sum[l]=pow(k,r)，其中r>l。

因为从数据范围来看，r最大只有lg(1e14)，所以我们可以将式子变为sum[r]-pow(k,r)=sum[l]。

然后将sum[l]放进map里，一次for就可以求出所有满足条件的sum[l]。

复杂度为O(n*logk*logn)。

技术分享 
 1 #include<bits/stdc++.h>
 2 #define F(i,a,b) for(int i=a;i<=b;++i)
 3 using namespace std;
 4 typedef long long ll;
 5 
 6 const int N=1e5+7;
 7 int n;
 8 ll sum[N],k,ans,inf=1e14;
 9 map<ll,ll>a;
10 set<ll>b;
11 set<ll>::iterator it;
12 
13 int main(){
14     scanf("%d%I64d",&n,&k);
15     F(i,1,n)scanf("%I64d",sum+i),sum[i]+=sum[i-1];
16     ll tmp=k;
17     b.insert(1);
18     F(i,1,60)
19     {
20         if(tmp>inf)break;
21         b.insert(tmp);
22         tmp*=k;
23     }
24     ans=0,a[0]=1;
25     F(i,1,n)
26     {
27         for(it=b.begin();it!=b.end();it++)ans+=a[sum[i]-*it];
28         a[sum[i]]++;
29     }
30     printf("%I64d\n",ans);
31     return 0;
32 }
View Code

 

Codeforces Round #400 C. Molly's Chemicals


联系
我们