计数字符串中的101个数

Question

下面是一个问题：我们只需要计算由0和1组成的字符串中的101个数。 101是字符串的任何子序列。

例如：10101其中有4个101。

我很确定我正确地解决了它。对于每个零，我预先计算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

输出768,16是，但我的代码是给

这里是我的代码：

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'; 

原：由``的scanf使用

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