Question

一条很简单的C语言题，但是我超时了，求大神解答？只有神知道的世界

在天地人三界之中，二次元空间已是家喻户晓。但是，存在于神秘国度的三次元空间却鲜为人知，因为那是只有神知道的世界。
传说中，要进入三次元空间必须通过守门大将的考核。
这是一个很简单的题目。
对于任意一个非负数N，我们定义D(N) 为N上奇数数字的和加上两倍偶数数字的和。举个例子：D(567) = 5 + 6 * 2 + 7 = 24, D(314159) = 3 + 1 + 2 * 4 + 1 + 5 + 9 = 27.
令F(N)表示D(N)的最后一位数字。例如：F(567) = 4, F(314159) = 7。
你的问题是，给你两个数A, B，你要计算出∑F(i), i ∈ [A, B]
对于聪明的你这太简单了，赶紧解决去观摩只有神知道的世界吧~
（出题人Troy）

输入格式
第一行输入一个整数T，表述有T组case。(T <=1000)
接下来T行，每行输入两个数字A, B （0 <= A <= B <= 400,000,000）

输出格式
每一行输出一个整数，表示题目所要求的和。

输入样例
3
1 8
28 138
314159 314159

输出样例
36
495
7

#include <stdio.h>
int add(long C)
{
int result=0,n;
while(C>0)
{
n=C%10;
if(n%2!=0)
result+=n;
else
result+=n*2;
C/=10;
}
return result;
}
int main()
{
int t,i,j;
static int sum[1000];
long A,B,C;
scanf("%d",&t);
for(i=0;i<t;i++)
{
scanf("%ld%ld",&A,&B);
for(C=A;C<=B;C++)
{
sum[i]+=add(C)%10;
}
}
for(i=0;i<t;i++)
printf("%d\n",sum[i]);
return 0;
}

Answer 1

直接硬算肯定TLE。话说那个add(C)后面%10干嘛。
这类题类似于：从数字A到数字B，连在一起写（比如15到25，就是1516171819202122232425），0~9各数字各出现了几次。这是可以直接计算而不必遍历的。
05年ICPC上海交大赛区就有这个变种。
思路是这样的：计算个十百千万等各位数字上0到9分别出现了几次。出现的次数是更高位的次数 * 低位的遍历。
比如0~12345，那么千位数上出线0的次数是1000次（从10000~10999），出现1的次数是2000次（1000~1999和11000~11999），出现2的次数是1346次（2000~2999,12000~12345），出现3~9都是1000次（X000~X999）。

追问

我大概明白你的意思了，但是他需要求每个数字的奇数和2倍偶数的和的末尾喔，如果像你这样不遍历，有可能实现的了求末尾么？按你这种说法，具体操作是怎样呢？

追答

哦，没注意到“末尾”。
不过我的算法没问题。

比如a0个0，a1个1，a2个2……a9个9

答案就是 1 * a1 + 3 * a3 + 5 * a5 + 7 * a7 + 9 * a9 + 2 * (2 * a2 + 4 * a4 + 6 * a6 + 8 * a8)。
模10运算，求和后求余数，和拆开后求余数再求和，结果是一样的。
这题基本上就是两个嵌套的for循环，外层循环从个位、十位……到最高位；内层循环从0~9。接下来就是计算特定位置上特定数出现的次数了。

PS：为了简便计算，先求出0~(A - 1)中各个数字出现的次数，再计算0~B中各个数字出现的次数，然后减一下就行。这样比直接计算A~B各数字出现次数容易一些。

PS2：这道题相对上海那题，容易之处在于，0出现几次是无所谓的（因为0最后求和时还是0）。所以对于0~12345，可以视为00000~12345。这样可以很轻松的解决问题了吧。

给个具体的例子：对于0~123456，计算千位上的各数出现的次数。0~9分成3档：小，中，大。
【小】计算0~2出现的次数：看千位上数字是3（123456的千位），0~2比3小，所以0~2出现的次数是比千位更高的数字的遍历（这里就是00~12，一共13次） * 比千位低的遍历（000~999共1000次），所以是13000次。

【中】计算3出现的次数：千位刚好是3，所以出现的次数是比千位更高的数字的遍历（00~11，注意不是12而是11） * 1000，然后千位以上是12时，123000~123456，千位上的3出现的次数再多了456 + 1 = 457个。所以结果是12000 + 457 = 12457。

【大】计算4~9出现的次数，由于4~9都比3大，所以出现的次数是比千位更高的数字的遍历（00~11，这里还是11而不是12） * 1000，所以出现了12000次。

追问

首先对于这句话答案就是
模10运算，求和后求余数，和拆开后求余数再求和，结果是一样的。
显然不对，求和后再模10答案只是个位数，而拆开求余后求和显然大于前者。
然后你的算法我也大概看懂了，可是对于这道题，回答了上面的问题后，还能应用么？能具体点分析么，我很笨。。。而且你的算法的运算量不也是挺大的么？如何判断运算量多少才会超时？

追答

“显然不对，求和后再模10答案只是个位数，而拆开求余后求和显然大于前者。”
拆开求余再求和，然后还要再对10求一次余数啊。这样就和求和再模10的结果一样了。

证明：影响最后结果的只有各个数字的个位，什么进位、十百千万位是多少都不影响结果的。而求余运算不影响数字的个位，所以无论什么时候求余，求几次，都不影响答案。

关于我的算法的运算量，一般ACM的算法题，除了模拟题（就是不用高级算法，只是代码繁杂），其他题一般都有高级算法（DP、分治之类）和普通算法（硬算、暴力搜索之类）。特别是那种数据规模比较大的，像你这道题，4亿规模，肯定考察的就是算法。

我的算法的运算量很小，对于4亿规模，也只要O(logN)的复杂度。因为是看位数的，9位数也只要算9次（外循环）。

而你的算法运算量达到了O(N）规模。一般ACM题，这个规模是足够小的。具体到某些题，比如你这道，如果考察的就是算法，那肯定会用超巨量的case数来耗尽时间。

对于一般的ACM题，O(N^2)通常不会TLE，O(N^3)有些时候也OK（比如Floyd算法之类）。

追问

这道题求余后相加后不用再求余了。。。。你先认真看看题先，大神帮我看看怎么做这题？

追答

汗，我又看错题了。
嗯，按照题目要求，我的方法是无法解决问题的。

算法有点复杂，超过字数了。我贴到我空间去了。
http://hi.baidu.com/destinyai/item/2294c3da3460e51e21e25088
如果有不明白的地方，可以继续追问；或者我也可以提供完整代码。

Answer 2

把add如下改一下试试
int add(long C){
int result=0,n;
while(C>0){
result+=(n=C%10) << (~n&1);
C/=10;
}
return result;
}

追问

还是超时了，不过你能讲解一下你这么改是什么意思么？看不太懂？

追答

我再给你改一个，并说明改的意思。
//#include "stdafx.h"//vc++6.0加上这一行.
#include "stdio.h"
int add(long a,long b){
int result,od,ev,t,i,x;
for(result=od=ev=0,i=a;(x=i)B)
printf("Error!Reso...\n");
sum[i]=add(A,B);
}
for(i=0;i<t;i++)
printf("%d\n",sum[i]);
}
思路就是不要三番五次调用函数，调用一次把所有事做完，减少调用时耗。其余的看注释。结果行不行我也不知道……

追问

我很遗憾的跟你说，还是超时。。。。。你的题我没看，不过感觉和我的还是相差不大

追答

我觉得已经破解你的问题了。在VC++6.0下运行1 100000000几乎是零等待。在我的平台上，你提供的代码运行这个数是36秒，我第二次给你的代码需33秒，确实不差上下。经再三考虑，改进了算法，达到了目前水平。有兴趣不妨一看——
//#include "stdafx.h"//vc++6.0加上这一行.
#include "stdio.h"
int add(long a,long b){
int result,od,ev,t,i,x;
if(a>b) return 0;
for(result=od=ev=0,i=a;(x=i)B)
printf("Error!Redo...\n");
if(B-A>9){
la=A/10*10;
lb=B/10*10-1;
sum[i]=(lb-la+1)/10*45+add(lb+1,B)-add(la,A-1);
}
else sum[i]=add(A,B);
}
for(i=0;i<t;i++)
printf("%d\n",sum[i]);
}
没有全面测试，边缘情况可能会出错，若有，请仔细调试一下。