algorithm - SPOJ 数字总和

Question

我正在尝试解决问题 http://www.spoj.com/problems/CPCRC1C/使用方法讨论在
http://goo.gl/YzEwXR

这是我对上述算法的实现

void solve(int i, bool lo, bool hi, char *A, char *B, int n, unsigned long long &sum,int numSum) {

if (i == n) {
    sum+=numSum;
    return;
}

char d = hi ? '0' : A[i];
char end = lo ? '9' : B[i];
for (; d <= end; d++) {

    int nnumSum=numSum ;
    nnumSum += (d-48);
   // cout<<"\nd="<<d<<"  sum="<<nnumSum;
    solve(i + 1, lo || d < B[i], hi || d > A[i], A, B, n, sum,nnumSum);
}
}

你能建议我如何使用内存优化算法吗？

非常感谢您的宝贵时间

Answer 1

CPCRC1C

1) sum of digits from 1 to b, let this count be sum(b)

2) sum of digits from 1 to a-1, let this count be sum(a-1)

返回两个计数之间的差异

如何计算 sum(x)？让我们尝试找出一种模式

什么是 sum(9)？

1 2 3 4 ........... 9
9*10/2 = 45

什么是 sum(19)？sum(9) + 后面数位的和

10 11 12 13 ....... 19
10 + 9*10/2 = 10 + 45 [10 is sum of first digit in all numbers]

什么是 sum(29)？sum(19) + 后面数位的和

20 21 22 23 ........29
20 + 9*10/2 = 20 + 45

什么是 sum(100)？

45 + (10 + 45) + (20 + 45) + (30 + 45) + ..... (90 + 45)
45*10 + (10 + 20 + 30 ... 90)
45*10 + 10(1 + 2 + ... 9)
45*10 + 45*10
45*20

我们可以使用上面的模式来得出一个可以直接计算总和的公式

来源:GeeksforGeeks