首页 > 代码库 > Codeforces Round #400 C. Molly's Chemicals
Codeforces Round #400 C. Molly's Chemicals
题目链接: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 }
Codeforces Round #400 C. Molly's Chemicals
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。