c++ - SUBSEQ spoj 中的错误答案

Question

我正在解决 spoj 中的计数子序列问题，但得到了错误的答案。这是链接 http://www.spoj.com/problems/SUBSEQ/

这是我的代码

 #include<stdio.h>
 #include<cmath>
 #include<algorithm>
 int main(){
int t,n;
scanf("%d",&t);
while(t-->0){
    scanf("%d",&n);
    long arr[n+1];
    for(int i=0;i<n;i++){
        scanf("%ld",&arr[i]);   
    }
    long sum=arr[0];
    int start=0;
    long ans=0;
    for(int i=1;i<=n;i++){
        while(sum>47 && start<i-1){
            sum-=arr[start];
            start++;
        }
        if(sum==47)
            ans+=1;
        if(i<n)
            sum+=arr[i];
    }
    printf("%ld\n",ans);
}

请帮我找出错误..

Answer 1

您的代码将无法通过以下测试用例(至少):

1
4
47 -47 48 -1

你的程序给出的答案是1，而答案应该是3，其中3个序列如下:

<b>47 -47 48 -1</b> [The entire sequence]

<b>47</b> [1st element only]

<b>48 -1</b> [3rd plus 4th elements]

很明显，您遇到了错误。

PS:顺便说一句，你为什么要声明一个包含 n+1 个项目的数组:long arr[n+1];当你永远不会引用 arr[n] ？ (事实上​​该项目甚至不存在)

[编辑]#:为上述用例添加说明

这个怎么样 - 它比你想象的要容易 :-)

1. 连续扫描数字。对于遇到的每个数字，将其添加到目前找到的总和中。

2. 保留总和(到目前为止)已找到次数的映射。

3. 现在，为了使总数达到 47，我们只需要找到一个数字，从目前的总和中减去该数字应该得到数字 47。这是必需的，因为如果我们从找到的总和中减去这个数字，那么到目前为止，它会从一些连续数字序列的总和中得到 47。

以上面的例子为例，<b>47 -47 48 -1</b>

1. 用 count = 0 的数字 0 初始化一个 map (也就是说我们到目前为止没有找到总和恰好一次 - 因为我们在开始阶段)

2. 从头扫描列表，取数字 47，到目前为止的总和，比方说，s = 47。我们做了两件事:

   • map(47) = 1(因为到目前为止我们第一次发现总和 = 47)。
   • 现在，我们需要找到次数，我们可以找到 s-47 = 0(即 1)。所以，到目前为止的答案 = map(0) = 1

3. 取下一个数字，-47。到目前为止的总和，s = 0

   • 到目前为止 map(0) = 1，所以没有 map(0) 变成 = 2
   • 我们需要找出 s-47 = -47 的出现次数。其中 = 0。所以到目前为止的答案 = 到目前为止的答案 + 0(剩余 = 1)

4. 取下一个数字，48，到目前为止的总和，s = 48

   • map (48) = 1
   • 我们需要找出 s-48 = -1 的出现次数。其中 = 0。所以到目前为止的答案 = 到目前为止的答案 + 0(剩余 = 1)

5. 取最后一个数字，-1，到目前为止的总和，s = 47

   • map(47) = 1(在步骤 2.1 中)，所以现在 map(47) 变为 = 2
   • 我们需要找到 s-47 = 0 的出现次数。其中 = 2(在步骤 3.1 中)。所以到目前为止的回答 = 到目前为止的回答 + 2 = 3

所以最终答案 = 3

编写此代码应该相当简单。