計數字符串中的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');