计算字符串中 101 的个数

Question

问题是:我们需要统计一个仅由 0 和 1 组成的字符串中 101 的个数。 101 是字符串的任意子序列。

Ex: 10101 has 4 101 in it.

我很确定我正确地解决了这个问题。对于每个零，我预先计算它之前和之后的 1 的数量，然后将答案相乘，然后将结果添加到 res。

对于由长度为 1000000 的字符串组成的测试用例，代码给出了错误的答案。

我想知道我的代码问题出在哪里？

测试用例的输入:https://he-s3.s3.amazonaws.com/media/hackathon/nitcencode03/problems/p1-6/d434839c-d-input-d4340a6.txt?Signature=IXEy0YlTGPX%2FkjsGoc%2FRxCC8bG8%3D&Expires=1427265583&AWSAccessKeyId=AKIAJLE6MUHDYS3HN6YQ

输出应为18446708952791232852，但我的代码给出22531786

这是我的代码:

char s[1000005];

unsigned long long ans, res, a[1000005];

int main()
{   
    int n;

    scanf("%s", s);
    n = strlen(s);

    a[0] = 0; res = 0;
    for(int i = 1;i <= n;++i)
        a[i] = a[i - 1] + (s[i - 1] == '1');

    for(int i = 1;i <= n;++i)
        if(s[i - 1] == '0') {
            ans = a[n] - a[i];
            ans *= a[i - 1];
            res += ans;
            //if(ans < 0 || res < 0) printf("%lld %lld\n", ans, res);
        }

    printf("%llu\n", res);


    return 0;
}

Answer 1

在花了一些时间解决了围绕足够的存储类型、gcc 代码/内存模型以及提升/溢出问题的各种问题之后，我想我已经找到了一个令我满意的解决这个问题的方法。

随着数据的大小，默认的代码/内存模型就可以了。 a 数组中存储的值完全属于 unsigned 类型，允许 a[1000000] 的静态声明正常工作，而不会导致段错误。 (4M存储要求)

结果值适合 unsigned long (x86_64) 或 unsigned long long (x86)。但是，如果结果计算未转换为 unsigned long，则会出现一个微妙的问题，因为总和的任何一个分量都不会导致提升。

因此，我想我会将这种方法发布到解决方案中，以防其他人好奇:

#include <stdio.h>

#define LMAX 868800

int main (int argc, char **argv) {

    if (argc < 2 ) {
        fprintf (stderr, "Error: insufficient input, usage: %s <filename>\n", argv[0]);
        return 1;
    }

    char s[LMAX] = {0};
    char *p = s;
    unsigned a[LMAX] = {0};
    unsigned long res = 0;
    unsigned n1s = 0;
    unsigned n0s = 0;
    size_t len = 0;
    size_t i = 1;
    FILE *fp = NULL;

    if (!(fp = fopen (argv[1], "r"))) {
        fprintf (stderr, "error: file open failed.\n");
        return 1;
    }

    if (!(fgets (s, LMAX - 1, fp))) {
        fprintf (stderr, "error: failed to read line from file.\n");
        return 1;
    }
    fclose (fp);

    /* fill a[i] with number of 1's before i in s   */
    while (*p && *p != '\n')
    {
        a[i] = a[i-1] + *p - '0';
        if (*p == '1') n1s += 1; else n0s +=1;
        p++; i++;
    }
    len = p - s;

    p = s;
    i = 1;
    /* for each '0' in s, multiply 1's before i with 1's after i
    and add product to result (i.e. the # of 101's for that 0) */
    while (*p && *p != '\n')
    {
        if (*p == '0')
            res += (unsigned long)a[i - 1] * (a[len] - a[i]);
        p++; i++;
    }

    printf ("\n num 1's  : %u\n num 0's  : %u\n length   : %zu\n results  : %lu\n\n",
            n1s, n0s, len, res);

    return 0;
}

回答

$ ./bin/num101s d434839c-d-input-d4340a6.txt

 num 1's  : 434105
 num 0's  : 434684
 length   : 868789
 results  : 13653596984029524

自解决方案发布之日起，此解决方案的数据文件可在此处获取:Input Data

转储到汇编程序后，与 Linux/x86_64 上的原始比较相比，以下内容似乎提供了一条指令优势:

    a[i] = a[i-1] + *p - '0';

原文:

    a[i] = a[i-1] + (*p == '1');