在天地人三界之中,二次元空间已是家喻户晓。但是,存在于神秘国度的三次元空间却鲜为人知,因为那是只有神知道的世界。
传说中,要进入三次元空间必须通过守门大将的考核。
这是一个很简单的题目。
对于任意一个非负数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;
}
我大概明白你的意思了,但是他需要求每个数字的奇数和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
如果有不明白的地方,可以继续追问;或者我也可以提供完整代码。
还是超时了,不过你能讲解一下你这么改是什么意思么?看不太懂?
追答我再给你改一个,并说明改的意思。
//#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]);
}
没有全面测试,边缘情况可能会出错,若有,请仔细调试一下。