62 lines
1.7 KiB
C++
62 lines
1.7 KiB
C++
#include <cstdio>
|
||
#include <cstring>
|
||
#include <iostream>
|
||
#include <cmath>
|
||
|
||
using namespace std;
|
||
const int N = 32; //数位的长度上限
|
||
const int M = 1024 * 10 + 10; //剩余的数大小(状态集合按这个划分)
|
||
int f[N][M]; //结果DP数组
|
||
int a[N]; //数位拆分出来的数组
|
||
int fa;
|
||
//利用递归计算出
|
||
int F(int x) {
|
||
if (x == 0) return 0;
|
||
return F(x / 10) * 2 + x % 10;
|
||
}
|
||
|
||
/**
|
||
* @param pos 数位位置
|
||
* @param st 剩余对比值,初始值是F(x)
|
||
* @param limit 是不是贴上界
|
||
* @return
|
||
*/
|
||
int dfs(int pos, int st, bool limit) {
|
||
if (pos == 0) return st >= 0; //如果到达最后，并且有剩余，表示f(i)<= f(x)，计数++
|
||
if (st < 0) return 0; //中途或最后一旦发生小于0情况，剪枝
|
||
if (!limit && ~f[pos][st]) return f[pos][st];
|
||
int ans = 0;
|
||
int up = limit ? a[pos] : 9;
|
||
for (int i = 0; i <= up; i++)
|
||
//st = st - i * 2^ ( p-1 )
|
||
ans += dfs(pos - 1, st - i * (1 << (pos - 1)), limit && i == a[pos]);
|
||
|
||
if (!limit) f[pos][st] = ans;
|
||
return ans;
|
||
}
|
||
|
||
inline int calc(int x) {
|
||
int al = 0;
|
||
while (x) a[++al] = x % 10, x /= 10;
|
||
return dfs(al, fa, true);
|
||
}
|
||
|
||
int main() {
|
||
//不加78MS，加了31MS，效果还是很明显的
|
||
ios::sync_with_stdio(false);
|
||
cin.tie(0);
|
||
|
||
int T;
|
||
int cnt = 1;
|
||
cin >> T; //这个数值太BT了，最大10000次！
|
||
|
||
//优化的写法
|
||
memset(f, -1, sizeof f);
|
||
while (T--) {
|
||
int x, y;
|
||
cin >> x >> y;
|
||
fa = F(x); //计算出F(x)值,这是一个固定值
|
||
printf("Case #%d: %d\n", cnt++, calc(y));
|
||
}
|
||
return 0;
|
||
} |