HLG 1005 Counting Subsequences-白红宇

HLG 1005 Counting Subsequences

阅读量：6909 次

发布时间：2019-06-27

本文共 2196 字，大约阅读时间需要 7 分钟。

Description

"47 is the quintessential random number," states the 47 society. And there might be a grain of truth in that.

For example, the first ten digits of the Euler's constant are:

2 7 1 8 2 8 1 8 2 8

And what's their sum? Of course, it is 47.

You are given a sequence S of integers we saw somewhere in the nature. Your task will be to compute how strongly does this sequence support the above claims.

We will call a continuous subsequence of S interesting if the sum of its terms is equal to 47.

E.g., consider the sequence S = (24, 17, 23, 24, 5, 47). Here we have two interesting continuous subsequences: the sequence (23, 24) and the sequence (47).

Given a sequence S, find the count of its interesting subsequences.

Input

The first line of the input file contains an integer T(T <= 10) specifying the number of test cases. Each test case is preceded by a blank line.

The first line of each test case contains the length of a sequence N(N <= 500000). The second line contains N space-separated integers – the elements of the sequence. Sum of any continuous subsequences will fit in 32 bit signed integers.

Output

For each test case output a single line containing a single integer – the count of interesting subsequences of the given sentence.

Sample Input

2 7 1 8 2 8 1 8 2 8 4 5 9

2 47 10047 47 1047 47 47

Sample Output

总结： hash or map 保存前面数的和

code1： <map>

View Code

#include
      
        #include
        using namespace std; int t,n,tot,x; map
        
          v; int main() {
      scanf("%d",&t); while(t--)   {
        scanf("%d",&n);     v.clear(); long long res=0,sum=0;     v[0] = 1; while(n--){
          scanf("%d",&x);       sum+=x;       tot+=v[sum-47];       v[sum]++;     }     printf("%d\n",tot);   } }

code:hash

View Code

#include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            using namespace std; int sum,now,n,ans; multiset 
           
             hash; void solve() { hash.clear(); scanf("%d",&n); sum=ans=0; hash.insert(0); for(int i=0;i

转载于:https://www.cnblogs.com/dream-wind/archive/2012/03/16/2400013.html

你可能感兴趣的文章

android TDD平台插入双卡时，查看允许返回发送报告的选项，去掉勾选，不起作用...