首页 > 代码库 > [数位统计] spoj 1433 The sum
[数位统计] spoj 1433 The sum
题意:对于数加一位减一位,给定N,求1~N的和。
例子12=1-2+3-4......-1+2=5
思路:
个人思路可能比较复杂,但是思路还是比较清晰的。
首先我们把一个数N分成两个部分,比如4568=1~999+1000~4568,567=1~99+100~567
也就是整百整千的数我们可以递推算出来,虽然找规律也是可以的~
就是1~999=1~99+100~999.
这样算的话 其实就解决了最后计算的问题,更能统一函数。
然后其实我们可以发现,位数是奇数的数,除了个位前面的数是两两抵消的。
比如 100~105=
-1+0-0
+1-0+1
-1+0-2
+1-0+3
....
而且个位便是0~9的和
所以只要算个数的奇偶性以及对10的整除关系就行了。
然后对于偶数为的数
比如1000~9876
我先计算1000~8999 然后 9000~9876
1000~8999其实就是算头尾两数和的差,中间都是抵消的。
然后9000~9876就按位计算就好了 减去和加上和依次类推。
规律拿笔算一下 不能发现的。
然后这道题注意两个地方。。
1、我不理解为什么极限的3个数爆64位了。我特殊处理了。
2、就是特殊处理的时候整数不能那么长,在后面加上LL就好了
代码:
#include"cstdlib" #include"cstdio" #include"cstring" #include"cmath" #include"stack" #include"algorithm" #include"iostream" using namespace std; long long xx=999999999999998LL; long long a[2][10],ans[16],ten[16]; long long solve(long long x) { long long len,t=1,n,tep,ans=0; len=(long long)log10(x*1.0)+1; n=len-1; while(n--) t*=10; if(len%2) //奇数位数 { tep=x-t+1; ans+=tep/10*a[1][9]; if(tep%10) ans+=a[1][tep%10-1]; if(tep%2) { x/=10; t/=10; int f=0; while(x) { if(f%2==0) ans-=x/t; else ans+=x/t; x%=t; t/=10; f++; } } } else //偶数位数 { ans=ans-t*a[0][x/t-1]; ans+=(x/t-1)*(t/10)*a[0][9]; //1000~8999 ans-=(x/t)*(x%t+1); tep=0; int f=0; x%=t; t/=10; while(x) { if(f) { ans-=tep*t*a[0][9]; ans-=t*a[0][x/t-1]; ans-=(x/t)*(x%t+1); } else { ans+=tep*t*a[0][9]; ans+=t*a[0][x/t-1]; ans+=(x/t)*(x%t+1); } tep=tep*10+x/t; x%=t; t/=10; f^=1; } } return ans; } int main() { memset(a,0,sizeof(a)); int i; for(i=1; i<=9; i++) a[0][i]=a[0][i-1]+i; for(i=1; i<=9; i++) { if(i%2) a[1][i]=a[1][i-1]+i; else a[1][i]=a[1][i-1]-i; } long long t=9; ans[1]=a[1][9]; for(i=2; i<=15; i++) { long long sum=0; t=t*10+9; sum=solve(t); ans[i]=ans[i-1]+sum; } long long n; while(scanf("%lld",&n),n) { long long len; if(n>=xx) { if(n==xx) puts("409090909090901"); else if(n==xx+1) puts("409090909090910"); else if(n==xx+2) puts("409090909090909"); continue; } if(n<10) { printf("%lld\n",a[1][n]); continue; } len=(long long)log10(n*1.0)+1; printf("%lld\n",ans[len-1]+solve(n)); } return 0; }
[数位统计] spoj 1433 The sum
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。