首页 > 代码库 > HDU 4734 F(x)

HDU 4734 F(x)

2024-08-03 18:54:06   222人阅读

Problem Description
For a decimal number x with n digits (AnAn-1An-2 ... A2A1), we define its weight as F(x) = An * 2n-1 + An-1 * 2n-2 + ... + A2 * 2 + A1 * 1. Now you are given two numbers A and B, please calculate how many numbers are there between 0 and B, inclusive, whose weight is no more than F(A).
 

Input
The first line has a number T (T <= 10000) , indicating the number of test cases.
For each test case, there are two numbers A and B (0 <= A,B < 109)
 

Output
For every case,you should output "Case #t: " at first, without quotes. The t is the case number starting from 1. Then output the answer.
 

Sample Input
3
0 100
1 10
5 100
 

Sample Output
Case #1: 1
Case #2: 2
Case #3: 13
 

Source

2013 ACM/ICPC Asia Regional Chengdu Online


题意：给你2个数n,m  要你求出0-m中，f(i)<=f(n)的数的个数


思路：数位DP的模板题目，这个时候的状态为当前位数的值

直接代码吧，或者可以参考我写的第一篇概率DP题提供一下思想


AC代码：

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;

int f[20][200000],bits[20];

int dfs(int pos,int sum,bool bianjie)
{
    int ans=0;
    if(pos==-1)return sum>=0;
    if(sum<0)return 0;
    if(!bianjie&&f[pos][sum]!=-1)
        return f[pos][sum];
    int u=bianjie?bits[pos]:9;
    for(int i=0;i<=u;i++)
    {
        ans+=dfs(pos-1,sum-i*(1<<pos),bianjie&&i==u);
    }
    return bianjie?ans:f[pos][sum]=ans;
}

int n,m;

int solve()
{
    int sum=0;
    int len=0;
    while(n)
    {
        sum=sum+(n%10)*(1<<len);
        len++;
        n/=10;
    }
   // printf("%d\n",sum);
    int len_m=0;
    while(m)
    {
        bits[len_m++]=m%10;
        m/=10;
    }
    return dfs(len_m-1,sum,true);
}


int main()
{
    int t;
    cin>>t;
    int cnt=1;
    memset(f,-1,sizeof(f));
    while(t--)
    {
        scanf("%d %d",&n,&m);
        cout<<"Case #"<<cnt++<<": "<<solve()<<endl;
    }
    return 0;
}


HDU 4734 F(x)


联系
我们