题解
注:以下lg底数均为10,就是数学里的常用对数
方法一
直接膜你
从1到n开始枚举,每个数字判断的复杂度是O(lg\ n),总复杂度是O(nlg\ n)
有点卡常数,所以:
方法二
dfs大发好!
直接dfs,最后相当于一个lg\ n元01集合S,每个元素a_{i}\in{S},若a_{i}=1相当于这个数字有10^{i-1},所以dfs可以排除掉许多无用决策
时间复杂度O(2^{lg\ n}),其实就等于O(\sqrt[log_{2}\ 10]{n}),竟然比O(\sqrt[3]{n})还要小(比分块还快)
每次确定下一个决策只有两个分支,因为数字里只能有0或者1所以就是10x和10x+1
代码
比膜你不知道短了多少的代码
#include<stdio.h>
int n,res;
void dfs(int x)
{
if(x>n) return ; //大于n就结束
++res; //累加答案
dfs(x*10);
dfs(x*10+1); //向下扩展
return ;
}
int main()
{
scanf("%d",&n);
dfs(1); //从第一个成立的数字1开始
printf("%d\n",res);
return 0;
}
方法三
注意到dfs有可能会爆栈啊还慢的要命,所以下面介绍一种O(lg\ n)的算法(不考虑高精度)
其实可以简化一下,从[方法二]就可以看出来,其实当n在第i位(从右往左)大于等于1时,相当于答案就会增加2^{i-1}(可以联合子集个数想一想)。
注意:当这一位为0但是这位左边(更高位)有大于1的数字时,就要把这个数字看成1(所以我用的是字符串处理)
最后预处理一下2的幂,就可以O(lg\ n)\approx{O(1)}
python
版本是正解(因为大数据要高精),虽然常数比较大,但是10^{10^{6}}应该还是可以轻松过的
代码
(我用的是C++
)
#include<string>
#include<iostream>
using namespace std;
int n,two[20],res,sized,digit;
string s;
bool flag;
int main()
{
ios::sync_with_stdio(false);
two[0]=1;
for(register int i=1;i<11;++i) two[i]=two[i-1]<<1; //预处理2的幂
cin>>s;
sized=s.size();
digit=sized-1; //当前位数
for(register int i=0;i<sized;--digit,++i)
{
if(s[i]>49) flag=true; //如果有大于1的数字后面的0等于1
if(s[i]>48||flag) res+=two[digit]; //符合要求就累加答案
}
cout<<res<<endl;
return 0;
}