poj3252 数位dp

这题不是用10进制储存的，要转化成2进制再计算

dp[i][j][k]   i是位数，j是1的个数，k是0的个数

#include<map>

#include<set>

#include<cmath>

#include<queue>

#include<stack>

#include<vector>

#include<cstdio>

#include<cassert>

#include<iomanip>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#define C 0.5772156649

#define pi acos(-1.0)

#define ll long long

#define mod 1000000007

#define ls l,m,rt<<1

#define rs m+1,r,rt<<1|1

#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;

const double g=10.0,eps=1e-;

const int N=+,maxn=+,inf=0x3f3f3f;

int dp[N][N][N],digit[N];

int dfs(int len,int one,int zero,bool fi,bool fp)

{

    if(!len)

    {

        if(fi)return ;

        return zero>=one;

    }

    if(!fp&&!fi&&dp[len][one][zero]!=-)return dp[len][one][zero];

    int ans=,fpmax=fp ? digit[len] : ;

    for(int i=;i<=fpmax;i++)

    {

        if(fi)

        {

            if(i==)ans+=dfs(len-,,,fi,fp&&i==fpmax);

            else ans+=dfs(len-,one+,zero,fi&,fp&&i==fpmax);

        }

        else

        {

            if(i==)ans+=dfs(len-,one,zero+,fi&,fp&&i==fpmax);

            else ans+=dfs(len-,one+,zero,fi&,fp&&i==fpmax);

        }

    }

    if(!fp&&!fi)dp[len][one][zero]=ans;

    return ans;

}

ll solve(ll x)

{

    int len=;

    while(x)

    {

        digit[++len]=x&;

        x/=;

    }

    return dfs(len,,,,);

}

int main()

{

    ios::sync_with_stdio(false);

    cin.tie();

    int a,b;

    memset(dp,-,sizeof dp);

    cin>>a>>b;

    cout<<solve(b)-solve(a-)<<endl;

    return ;

}

/********************

********************/

写法1

#include<map>

#include<set>

#include<cmath>

#include<queue>

#include<stack>

#include<vector>

#include<cstdio>

#include<cassert>

#include<iomanip>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#define C 0.5772156649

#define pi acos(-1.0)

#define ll long long

#define mod 1000000007

#define ls l,m,rt<<1

#define rs m+1,r,rt<<1|1

#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;

const double g=10.0,eps=1e-;

const int N=+,maxn=+,inf=0x3f3f3f;

int dp[N][N][N],digit[N];

int dfs(int len,int one,int zero,bool fi,bool fp)

{

    if(!len)

    {

        return !fi&&zero>=one;

    }

    if(!fp&&!fi&&dp[len][one][zero]!=-)return dp[len][one][zero];

    int ans=,fpmax=fp ? digit[len] : ;

    for(int i=;i<=fpmax;i++)

    {

        if(fi)

        {

            if(i==)ans+=dfs(len-,,,fi,fp&&i==fpmax);

            else ans+=dfs(len-,one+,zero,fi&,fp&&i==fpmax);

        }

        else

        {

            if(i==)ans+=dfs(len-,one,zero+,fi&,fp&&i==fpmax);

            else ans+=dfs(len-,one+,zero,fi&,fp&&i==fpmax);

        }

    }

    if(!fp&&!fi)dp[len][one][zero]=ans;

    return ans;

}

ll solve(ll x)

{

    int len=;

    while(x)

    {

        digit[++len]=x&;

        x/=;

    }

    return dfs(len,,,,);

}

int main()

{

    ios::sync_with_stdio(false);

    cin.tie();

    int a,b;

    memset(dp,-,sizeof dp);

    cin>>a>>b;

    cout<<solve(b)-solve(a-)<<endl;

    return ;

}

/********************

********************/

写法2