当前位置：首页 > news >正文

HDU - 4734 -- F(x)

news 2025/9/14 12:46:42

题目如下：

For a decimal number x with n digits $A_nA_{n-1}A_{n-2} ... A_2A_1)$ , we define its weight as $F(x) = A_n * 2^{n-1} + A_{n-1} * 2^{n-2} + ... + A_2 * 2 + A_1 * 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 $\le 10000)$ , indicating the number of test cases.
For each test case, there are two numbers $A$ and $B$ $\le A,B < 10^9)$
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

Output

Case #1: 1
Case #2: 2
Case #3: 13

思路 or 题解：

数位DP
dfs(数位， F(x) - 该位数的贡献，是否有限制)
具体请参考下面代码

AC 代码如下：

/*
Make it simple and keep self stupid
author：Joanh_Lan
*/
#pragma GCC optimize(3)
#pragma GCC optimize("inline") // 如果比赛允许开编译器优化的话，可以默写这两段
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <numeric>
#include <cstring>
#include <cmath>
#include <map>
#include <unordered_map>
#include <bitset>
#include <set>
#include <random>
#include <ctime>
#include <queue>
#include <stack>
#include <climits>
#define buff                     \ios::sync_with_stdio(false); \cin.tie(0);
// #define int long long
#define ll long long
#define PII pair<int, int>
#define px first
#define py second
typedef std::mt19937 Random_mt19937;
Random_mt19937 rnd(time(0));
using namespace std;
const int mod = 1e9 + 7;
const int inf = 2147483647;
const int N = 100009;
//int Mod(int a,int mod){return (a%mod+mod)%mod;}
//int lowbit(int x){return x&-x;}//最低位1及其后面的0构成的数值
//int qmi(int a, int k, int p){int res = 1 % p;while (k){if (k & 1) res = Mod(res * a , p);a = Mod(a * a , p);k >>= 1;}return res;}
//int inv(int a,int mod){return qmi(a,mod-2,mod);}
//int lcm(int a,int b){return a*b/__gcd(a,b);}
int f[30][N], dig[30], idx;
int calc(int x)
{int ans = 0, t = 1;while (x)ans += x % 10 * t, t <<= 1, x /= 10;return ans;
}
int dfs(int pos, int s, bool lim)
{if (pos == -1)	return s >= 0;if (s < 0)return 0;if (!lim && f[pos][s] != -1)	return f[pos][s];int len = lim ? dig[pos] : 9;int ans = 0;for (int i = 0; i <= len; i++)ans += dfs(pos - 1, s - i * (1 << pos), lim && i == len);if (!lim)	f[pos][s] = ans;return ans;
}
void solve()
{int x, n;	cin >> x >> n;idx = 0;while (n)dig[idx++] = n % 10, n /= 10;cout << dfs(idx - 1, calc(x), 1) << '\n';
}
int main()
{buff;memset(f, -1, sizeof f);int _ = 1;cin >> _;for (int i = 1; i <= _; i++){cout << "Case #" << i << ": ";solve();}
}