首页 > 代码库 > Codeforces 9C Hexadecimal's Numbers - 有技巧的枚举

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

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