Codeforces 9C Hexadecimal's Numbers - 有技巧的枚举

三叶草

2017-08-01 21:35:53
writer：pprp
集训第一天：作为第一道题来讲，说了两种算法，
第一种是跟二进制数联系起来进行分析；
第二种是用深度搜索来做，虽然接触过深度搜索但是这种题型还是我第一次见；
题目：
统计1~n之间有多少数字只由0，1构成
1 ≤ n ≤ 1e9
用深度搜索解决这种问题；
代码如下：

#include <iostream>
#include <map>
using namespace std;
map<int,int>vis;
long long ans = 0;
int n;
//深度搜索,模仿
void dfs(int x)
{
  if(x > n)
    return;
  if(vis[x])
    return;
  vis[x] = 1;
  ans++;
  dfs(x*10);
  dfs(x*10+1);
}
int main()
{
  cin >> n;
  
  dfs(1);
  
  cout << ans << endl;
  return 0;
}

遇到的问题：不知道为什么用数组来取代map就不能通过，最后还是用了map
代码改变世界