Codeforce Round #400 C签到题

    xiaoxiao2021-03-26  3

    题目链接:点击打开链接

    题目大意:

    一个区间的价值【L,R】表示区间内所有元素的价值和。

    问你一共有多少个区间的价值,是K的非负整数次幂(0,1,2,3,4,5............)。

    题解:计算前缀和,并将已计算的前缀和放入map中储存,对于每个新的前缀和,只需去map中查找是否有满足条件的前缀和即可。

    Code:

    #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <map> #define ll long long using namespace std; const int maxn = 1e5 + 10; const ll INF = 1e14 + 20; int n,k; ll a[maxn],ans = 0; ll nums[51],ncnt; map<ll,int> map1; int main() { scanf("%d%d",&n,&k); for(int i = 1;i <= n;i++) scanf("%I64d",&a[i]); if(k == 1) {ncnt = 1;nums[1] = 1;} else if(k == -1) {ncnt = 2;nums[1] = -1;nums[2] = 1;} else { ll temp = 1; for(ncnt = 1;temp <= INF;ncnt++){ nums[ncnt] = temp; temp *= k; }ncnt--; } ll sum = 0;ans = 0; map1[0] = 1; for(int i = 1;i <= n;i++){ sum += a[i]; for(int j = 1;j <= ncnt;j++){ if(map1.count(sum - nums[j])) ans += map1[sum - nums[j]]; } map1[sum]++; } printf("%I64d\n",ans); return 0; }

    转载请注明原文地址: https://ju.6miu.com/read-500162.html

    最新回复(0)