首页 > 代码库 > 计算子序列和是定值的子序列个数
计算子序列和是定值的子序列个数
题目如下:
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
7 |
Sample Output |
3 4 |
这道题的意思就是给你一个整形的序列,让你计算满足和是47的子序列的个数。序列中的值可能有负数。
所以最直观的方法就是计算所有子序列的和,然后判断是否与47相等。算法的时间复杂度为O(N³),代码如下:
#include<iostream> #include<vector> #include<map> #define N 47 using namespace std; template<class type> int countSubseq(const vector<type> &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<int> 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<class type> int countSubseq(const vector<type> &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<class type> int countSubseq(const vector<type> &data) { int count = 0, sum = 0; map<int, int> 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; }