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

一时失言乱红尘 2022-06-02 02:16 158阅读 0赞

Wannafly挑战赛5 A.珂朵莉与宇宙 题目描述
    
    星神是来自宇宙的 
    
    所以珂朵莉也是吧 
    
    所以我就出了个题 
    
    给你一个长为n的序列a，有n*(n+1)/2个子区间，问这些子区间里面和为完全平方数的子区间个数 
    
    输入描述:
    第一行一个数n
    第二行n个数表示序列a
    
    输出描述:
    输出一个数表示答案
     
    
    示例1 
    
    
    输入
    
    6
    0 1 0 9 1 0
    
     
    
     #include<cstdio>
    using namespace std;
    int sum[100010];
    int a[1000100];
    int main ()
    { 
        int n;
        long long ans=0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
         scanf("%d",&sum[i]);
         sum[i]+=sum[i-1];
         //a[sum[i]]++;先把a数组算出来是不对的
        }
        /*分为两种情况：
        1是第一个数是完全平方数
        2是第一个数不是完全平方数
        所以a[0]=1就是为了处理第一种情况的
        如果是第二种情况就没必要让a[0]=1了*/
        a[0]=1;
        for(int i=1;i<=n;i++){
         for(int j=0;j*j<=sum[i];j++){
          ans+=a[sum[i]-j*j];
         }
         //a[sum[i]]++表示某个前缀和出现的次数,且不能先把a数组给算出来，
        a[sum[i]]++;
        }
        printf("%lld\n", ans);
        return 0;
    }
    
     
     前缀和a[j]肯定是大于等于可能满足的平方数的，所以前面用求得的n个前缀和   依次去 减去 一个平方数  得到的数   就是要截去的数目（也即一个前缀和），因为区间是连续的，所以只能是减掉某一个前缀和，所以就转化成求某些前缀和的总个数了
     
     由题意也可得：sum[m]  -  sum[n]  =  j  *   j   ,并且 m>=n  
     j  就是那个平方数 ，并且 j 在 闭区间[n，m] 内。由此可以看出求  j 的个数 就等价于就  sum[n]  的个数了  ( 有点逆向思维的味道)