Wannafly挑战赛5 A.珂朵莉与宇宙

题目链接 :https://www.nowcoder.com/acm/contest/36/A

题意

给你一个长为n的序列a,有n*(n+1)/2个子区间,问这些子区间里面和为完全平方数的子区间个数

输入描述:

第一行一个数n
第二行n个数表示序列a
n <= 1e5 , 0 <= a[i] <= 10;

思路

前缀和思想,因为区间连续,枚举区间的最后一位(一共n种),
去掉前面的一部分(前缀和)判断是否构成完全平方数。复杂度O(n*sqrt(n*10));

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <vector>
#include <stack>
#include <cctype>
#include <set>
#include <ctype.h>
#include <string.h>
#define inf 999999999
#define eps 0.000001
using namespace std;
typedef long long ll;
const int maxn = 1e6+10;
int cnt[maxn];
int n;
int main(int argc, char const *argv[])
{
while(cin >> n){
int x;
ll ans = 0;
cnt[0] = 1;
int sum = 0;
for(int i = 0 ; i < n ; i ++){
scanf("%d",&x);
sum += x;
for(int j = 0 ; j * j <= sum ; j ++){
ans += cnt[sum - j * j];
}
cnt[sum] ++;
}
cout << ans << endl;
}
return 0;
}