首页 > 代码库 > Codeforces Round #400 C 前缀和,思维
Codeforces Round #400 C 前缀和,思维
ICM Technex 2017 and Codeforces Round #400 (Div. 1 + Div. 2, combined)
C. Molly‘s Chemicals
题意：n个数，问有多少个区间的和是k的次方数，即sum([l, r])=k^x， x>=0。 abs(k)<=10。
tags：一开始O(n^2)统计，果然炸了。。 这题要在统计到第 i 个数时，看s[i]-k^x是否在前面出现过。因为k指数增长很快，这样就是O(n)。
// #400#include<bits/stdc++.h>using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define rep(i,a,b) for (int i=a;i<=b;i++)#define per(i,b,a) for (int i=b;i>=a;i--)#define mes(a,b) memset(a,b,sizeof(a))#define INF 0x3f3f3f3ftypedef long long ll;const int N = 2e5+10;map<ll ,ll >A, vis;int main(){ int n, k, a; ll s=0, ans=0; scanf("%d %d", &n, &k); A[0]++; rep(i,1,n) { scanf("%d", &a); A[s+=a]++; vis.clear(); for(ll j=1; abs(j)<=1e15 && vis[j]==0; j*=k) { //坑点，因为a[i]<=1e9，但j在这里是指和，所以不是<=1e9 vis[j]=1; if(A.find(s-j)!=A.end()) ans+=A[s-j]; } } printf("%lld\n", ans); return 0;}
Codeforces Round #400 C 前缀和,思维
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。