虎牙C++笔试分享

#include <iostream>
using namespace std;
int v[100];
int dp[100][3];
int dfs(int len,int flag,bool limit){
    if (flag == 3) return 0;
    if (len == 0) return 1;
    if (!limit&&dp[len][flag] != -1) return dp[len][flag];
    int maxx = limit ? v[len] : 1;
    int cnt = 0;
    for (int i = 0; i <= maxx; i++){
        if (i == 0){
            cnt += dfs(len-1,0,limit&&i == v[len]);
        }
        else{
            cnt += dfs(len-1, flag+1 , limit&&i == v[len]);
        }
    }
    return limit ? cnt : dp[len][flag] = cnt;
}
int solve(long long x){
    memset(v, 0, sizeof(v));
    int k = 0;
    while (x){
        v[++k] = x % 2;
        x >>=1;
    }
    return dfs(k, 0, true);
}
int main(){
    memset(dp, -1, sizeof(dp));
    long long a;
    cin >> a;
    cout<<solve(a)<<endl;
    return 0;
}