题目

源地址:

http://codeforces.com/problemset/problem/9/C

理解

题意不难理解。给定一个n,要你求出从0到n有多少个仅用0和1能表示出来的数。 想法很简单,我们先来处理最为简化的情况,如果给定一个二进制数,我们要求出比这个小的二进制数的个数有多少。小脑一动,我们就能知道,这个个数就是这个二进制数转化为十进制数的大小。 那么问题来了,给定一个十进制数,我们怎样才能求出这个最大的二进制数呢?其实我们可以这样来处理:每一位都有三种情况,0或者1或者大于1。0和1不需要进行任何操作,如果大于1,我们则把从这一位起的每一位都变成1。这样处理之后,我们就得到了最大的二进制数。然后就是一个简单的进制转换问题。

其实当天晚上的BestCoder 18的1003题跟这个有点像,不过做BC的时候,我没有捋清楚思路,最后还是没有敲出来。不过多亏被虐了一发,这道题才顺利地推出了结论。

代码


char n[10];
ll a[10],len;
ll ans=0;

int main(int argc, char const *argv[])
{
	scanf("%s", n);
	len=strlen(n);
	for(int i=0;i<len;i++)
    {
        a[i]=n[i]-'0';
    }
    for(int i=0;i<len;i++)
    {
        if(a[i]>1)
        {
            for(int j=i;j<len;j++)
            {
                a[j]=1;
            }
        }
    }
    for(int i=0;i<len;i++)
    {
        ans+=a[len-i-1]*(ll)pow(2,i);
    }
    printf("%I64d\n", ans);
	return 0;
}

更新日志

  • 2014年11月16日 已AC。