noj1475（递推题）统计多少个1

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;

}

巴特西

noj1475（递推题）统计多少个1

最新文章

热门文章