http://acm.nbut.cn/Problem/view.xhtml?id=1475
题意：给出一个数，需要你统计在这个数范围内有多少个1........
思路：从高位到低位计算，例如1312
最高位==1,说明最高位为一个的数字1000——1312，有313种
次高位==3>1，那么先思考它本身为1的情况，只有三位数的时候，范围为1——312，其中第三位为1的情况有100种，在这情况下，如果有四位数，1——1312，第三位为1的情况，应该是它只有3位数的时候为1的情况加上有四位数时为1的情况，那么应该是200种
次低位==1，同样的它只有两位的时候本身为1的情况只有3种（10，11，12），但在小于三位数（1--99）的情况下，第二位为1的情况有10种，再综合三位数与四位数的情况，次低位为1的情况有10*（13）+3==133种
最低位==2>1，那么本身为1的情况只有一种，那不止一位的情况下最低位为1有1*（n/10）种，再加上自己本身为132种
总共为778种
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
using namespace std;
typedef __int64 ss;
__int64 a[20]; int main()
{
a[0]=0;
a[1]=1;
a[2]=10;
a[3]=100;
a[4]=1000;
a[5]=10000;
a[6]=100000;
a[7]=1000000;
a[8]=10000000;
a[9]=100000000;
a[10]=1000000000;
//s[11]=10000000000;
//s[12]=100000000000;
//s[13]=1000000000000;
ss n;
while(scanf("%I64d",&n)>0)
{
ss b[15];
ss len=(ss)log10((double)n)+1,sum=0;
for(ss i=len;i>=1;i--)
{
if(i==len)
{
b[i]=n%(ss)(pow(10.0,(double)(i-1))+0.5);
}
else if(i==1)
{
b[i]=n/10;
}
else
{
b[i]=n/(ss)(pow(10.0,(double)i)+0.5);
}
}
for(ss i=len;i>=1;i--)
{
ss k=n%(ss)(pow(10.0,(double)i)+0.5)/(ss)(pow(10.0,(double)(i-1))+0.5);
//printf(" k=%I64d\n",k);
ss ans=0;
if(i==len)
{
if(k==1)
{
ans=b[i]+1;
}
if(k>1)
{
ans=a[i];
}
sum+=ans;
//printf("i==%I64d %I64d %I64d %I64d\n",i,b[i],a[i],sum);
continue;
}
if(k>1)
{
ss ans=0;
ans+=b[i]+1;
sum+=ans*a[i];
//printf("i==%I64d %I64d %I64d %I64d\n",i,b[i],a[i],sum);
continue;
}
if(k==1)
{
ss ans=0;
ans+=b[i];
sum+=ans*a[i];
ss tmp=n%(ss)(pow(10.0,(double)(i-1))+0.5);
sum+=tmp+1;
//printf("i==%I64d %I64d %I64d tmp=%I64d\n",i,b[i],a[i],tmp);
continue;
}
if(k==0)
{
sum+=b[i]*a[i];
//printf("i==%I64d %I64d %I64d %I64d\n",i,b[i],a[i],sum);
continue;
}
}
printf("%I64d\n",sum);
}
return 0;
}