题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3943
题目大意：求出区间 (P,Q] 中找到第K个满足条件的数，条件是该数包含X个4和Y个7
Sample Input
1
38 400 1 1
10
1
2
3
4
5
6
7
8
9
10
Sample Output
Case #1:
47
74
147
174
247
274
347
374
Nya!
Nya!
分析一：
先预处理dp[i][j][k]表示第 i 位有 j 个4和 k 个7的数量。之后就可以通过高位开始枚举，求出区间内有多少个规定的数，如果询问大于总数，则输出“Nya!”
之后找第k大的数：首先可以确定出位数，dp[i][x][y]表示 i 位时的满足数，那么大于dp[len-1][x][y]，而小于dp[len][x][y]，len表示目标位数。
确认了位数之后，依然从高位开始。比如说高位首先是0，而dp[len-1][x][y]小于k，说明0开头的目标小于所求，继续往后找，把之前的删掉
有点意思
代码如下：
# include<iostream>
# include<cstdio>
# include<cstring>
# define LL __int64
using namespace std; LL dp[][][]; //dp[i][j][k]表示i位的数，有j个4，k个7的数量
LL l,r;
int x,y; void init()
{
int i,j,k;
memset(dp,,sizeof(dp));
dp[][][] = ;
for(i=; i<=; i++)
for(j=; j<i; j++)
for(k=; k+j<i; k++)
{
dp[i][j][k+] += dp[i-][j][k];
dp[i][j+][k] += dp[i-][j][k];
dp[i][j][k] += dp[i-][j][k]*; //在高位上加除4、7以外的8个数字
}
} LL get_count(LL n)
{
int bit[],len=;
while(n)
{
bit[++len] = n%;
n /= ;
}
LL ans = ;
int cx=x, cy=y;
for(int i=len; i; i--) //从高位开始枚举
{
for(int j=; j<bit[i]; j++)
if(j==)
{
if(cx)
ans += dp[i-][cx-][cy];
}
else if(j==)
{
if(cy)
ans += dp[i-][cx][cy-];
}
else
ans += dp[i-][cx][cy];
if(bit[i]==)
cx--;
if(bit[i]==)
cy--;
//如果高位出现的4、7的数量已经超过所求，则退出
if(cx< || cy<)
break;
}
return ans;
} LL solve(LL k)
{
int len = ;
while()
{
//找到目标长度
if(dp[len-][x][y]<k && dp[len][x][y]>=k)
break;
len++;
}
LL ret = ;
int cx=x, cy=y;
for(int i=len; i; i--)
{
//从高位开始枚举
for(int j=; j<; j++)
{
int tx = cx,ty=cy;
if(j==)
{
tx--;
if(tx<)
continue;
}
if(j==)
{
ty--;
if(ty<)
continue;
}
if(dp[i-][tx][ty] >= k)
{
ret = ret*+j;
cx=tx;
cy=ty;
break;
}
k -= dp[i-][tx][ty];
}
}
return ret;
} int main()
{
init();
int T,cas;
scanf("%d",&T);
for(cas=; cas<=T; cas++)
{
scanf("%I64d%I64d%d%d",&l,&r,&x,&y);
LL a=get_count(r+);
LL b=get_count(l+); //注意左开区间
int n;
scanf("%d",&n);
printf("Case #%d:\n",cas);
while(n--)
{
LL k;
scanf("%I64d",&k);
if(k > a-b)
puts("Nya!");
else
printf("%I64d\n",solve(k+b));
}
}
return ;
}
分析二：
将solve() 函数改成二分写法，答案更简洁
LL solve(LL k)
{
LL mid,ans=-,ret,left=l,right=r;
while(left<=right)
{
mid = (left+right)>>;
ret = get_count(mid+);
if(ret>=k)
{
ans =mid;
right = mid-;
}
else
left=mid + ;
}
return ans;
}