hdu 4734 F(x) (数位dp)

Posted by 111qqz on Friday, March 18, 2016

TOC

题目链接s
题意:将一个10进制数x按照2进制展开后得到的值设为f(x)…现在给出a,b(10^9)问【0,b】中满足f[x]<=f[a]的数的个数。
思路:先算出f[a]…然后我们发现f(x)最大也就10*2^10=10240.。。数组可以存下。。搞之。和上一道题类似。。我们不关心两个f函数的值具体是多少。。。只关心他们的相对大小情况。。所以还是可以合并成一个变量。。。然而我用两个变量为什么错了。。不懂==

错误代码(用两个变量分别记录)

/* ***********************************************
Author :111qqz
Created Time :2016年03月17日 星期四 21时30分57秒
File Name :code/hdu/4734.cpp
************************************************ */

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair

using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
int a,b;
int digit[15],digita[15];
int fa;
int dp[10][110000];//dp[i][j]表示长度为i,f[x]为j的方案数...
int power[20];

int cal( int n)
{
    ms(digita,0);
    int len = 0 ;
    while (n)
    {
    digita[++len] = n % 10;
    n /= 10 ;
    }
    int base = 1;
    int res = 0 ;
    for ( int i = 1 ; i <= len ; i ++)
    {
//	cout<<"digita:"<<digita[i]<<endl;
    res +=digita[i]*base;
    base*=2;
    }

    return res;
}


int dfs(int pos,int sum,bool limit)
{
    if (pos==0)  return  sum<=fa;
    if (sum>fa) return 0; //sum只会越来越大。。所以这里可以减一下。。。
  //  if (sum+(power[pos+1]-1)*9<=fa) return 1; //如果后面的位置取最大仍然满足,可以提前就确定。减!
    if (!limit&&dp[pos][sum]!=-1) return dp[pos][sum];

    int mx = limit?digit[pos]:9;

    int res = 0  ;
    for ( int i = 0 ; i <= mx ; i++)
    {
       res+=dfs(pos-1,sum+i*power[pos],limit&&i==mx);
    }

  //  if (!limit) dp[pos][sum] = res;
    return res;
}
int solve ( int n)
{
    ms(digit,0);
    int len = 0 ;
    while (n)
    {
    digit[++len] = n % 10;
    n /= 10;
    }

    return dfs(len,0,true);
}

void pre()
{
    power[1] = 1;
    for ( int i = 2 ; i <= 12 ; i++)
    {
    power[i] = power[i-1]*2;
    }
}
int main()
{
    #ifndef  ONLINE_JUDGE 
    freopen("code/in.txt","r",stdin);
  #endif
    pre();
    int T;
    cin>>T;
    ms(dp,-1);
    int cas = 0 ;
    while (T--)
    {
        scanf("%d %d",&a,&b);
        fa = cal(a);
        int ans = solve(b);
        printf("Case #%d: %d\n",++cas,ans);
    }

  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}

AC代码:

/* ***********************************************
Author :111qqz
Created Time :2016年03月18日 星期五 08时57分02秒
File Name :code/hdu/r4734.cpp
************************************************ */

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair

using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
int digit[20];
int a,b;
int dp[11][11000];
int power[15];
int fa;
int cal( int n)
{
//    cout<<"n:"<<n;
    int base = 1;
    int res = 0 ;
    while (n)
    {
    res += (n)*base;
    base*=2;
    n/=10;
    }
//    cout<<" res:"<<res<<endl;
    return res;
}

int dfs( int pos,int sum,bool limit)  //依然是只关心两个数的相对大小。。。而不关心他们具体是多少。。
{                                       //所以可以合并成一个变量。。。
//    cout<<"pos:"<<pos<<" sum:"<<sum<<endl;
    if (pos==0) return sum>=0;
    if (sum<0) return 0;

    if (!limit&&dp[pos][sum]!=-1) return dp[pos][sum];
    
    int mx = limit? digit[pos] : 9 ;
    int res = 0 ;
    for ( int i =  0 ; i <= mx ; i++)
    {
    res+=dfs(pos-1,sum-power[pos]*i,limit&&i==mx);
    }
    if (!limit) dp[pos][sum] = res;
    return res;
}
int solve ( int n )
{
    int len = 0 ;
    ms(digit,0);
    while (n)
    {
    digit[++len] = n % 10;
    n/=10;
    }
//    for ( int i = len ; i >=1 ;  i--) cout<<digit[i];
    return dfs(len,cal(a),true);
}
int main()
    {
    #ifndef  ONLINE_JUDGE 
    freopen("code/in.txt","r",stdin);
  #endif
	
    power[1] = 1;
    for ( int  i = 2 ; i <= 12 ; i++) power[i] = power[i-1] * 2; //循环不小心从1开始。。。结果全0了。。。。2333
    int T;
    cin>>T;
    int cas = 0;
    ms(dp,-1);
    while (T--)
    {
        scanf("%d %d",&a,&b);
        fa = cal(a);
        int ans = solve(b);
        printf("Case #%d: %d\n",++cas,ans);

    }

  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}

「真诚赞赏,手留余香」

111qqz的小窝

真诚赞赏,手留余香

使用微信扫描二维码完成支付