计算子序列和是定值的子序列个数-白红宇

计算子序列和是定值的子序列个数

阅读量：7229 次

发布时间：2019-06-29

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

题目如下：

Counting Subsequences

Time Limit: 5000 MSMemory Limit: 65536 K

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
 
13
2 7 1 8 2 8 1 8 2 8 4 5 9
 
7
2 47 10047 47 1047 47 47

Sample Output

3
4

这道题的意思就是给你一个整形的序列，让你计算满足和是47的子序列的个数。序列中的值可能有负数。

所以最直观的方法就是计算所有子序列的和，然后判断是否与47相等。算法的时间复杂度为O(N³)，代码如下：

#include
    
     #include
     
      #include
      #define N 47using namespace std;template
       
        int countSubseq(const vector
        
          &data){	int count = 0;	for(size_t i = 0; i < data.size(); ++i)	{		int sum = 0;		for(int j = 0; j <= i; ++j)		{			int sum = 0;			for(int k = j; k <= i; ++k)			{				sum += data[k];			}			if(sum == N)			{				++count;			}		}	}	return count;}int main(){	int nCase;	cin >> nCase;	for(int i = 0; i < nCase; ++i)	{		int n, d;		cin >> n;		vector
         
           data(n, 0); for(int j = 0; j < n; ++j) { cin >> d; data[j] = d; } cout << countSubseq(data) << endl; } return 0;}

通过分析可以看出程序存在许多重复计算，上一个sum可以进行一次加法运算得到下一个sum。经过再次优化使其时间复杂度变为O(N²)，代码如下：

template
    
     int countSubseq(const vector
     
       &data){	int count = 0;	for(size_t i = 0; i < data.size(); ++i)	{		int sum = 0;		for(int j = i; j < data.size(); ++j)		{						sum += data[j];			if(sum == N)			{				++count;			}		}	}	return count;}

但是程序依然超时，所以要设计出复杂度更低的算法才行。

设SUM[i,j] = A[i] + A[i+1] + ... + A[j] (0 <= i <= j < N)，所以SUM[i, j] = SUM[0, j] - SUM[,0, i-1]，也就是说只要求出所有的SUM[0, K] (K∈[0,N))就能计算出任意SUM[i, j].那么我们每次计算K的一种取值得到的SUM时，查找之前计算的SUM是否有与当前SUM差是47的K的个数，可以使用map来降低查找的复杂度，这样时间复杂度降为O(N)，代码如下：

template
    
     int countSubseq(const vector
     
       &data){	int count = 0, sum = 0;	map
      
        sumToSeqCnt;//存储和是sum的序列K的个数	sumToSeqCnt[0] = 1;	for(size_t i = 0; i < data.size(); ++i)	{		sum += data[i];		sumToSeqCnt[sum]++;//计算和是sum的序列K的个数		count += sumToSeqCnt[sum - N];	}	return count;}

转载于:https://my.oschina.net/u/1404847/blog/291301

你可能感兴趣的文章