题目链接：hdu 5676
一开始看题还以为和数位dp相关的，后来才发现是搜索题，我手算了下，所有的super lucky number（也就是只含数字4, 7且4, 7的数量相等的数）加起来也不过几万个，可以采用打表的方法来把所有的super lucky number存储起来。因为4,7数量须相等，所以可以用一个二进制数的0,1来代替，先限定4,7数量分别为 i，之后就是求出包含 i 个0和 i 个1的 2*i 位所有这样的二进制数，然后简单转换一下（1->7, 0->4，这样子能从小到大 push 进 vector 中）得到对应的4,7数量分别为 i 的super lucky number，i 从1枚举到9（因为9*2=18达到了long long的上限）就能得到所有的super lucky number了，打好表后剩下的便是二分查找了。一开始wa了一发，后来才知道需要特判，因为打的表中最大的数只达到777777777444444444（9个4,9个7），对于比这个更大的数可以直接知道是44444444447777777777（10个4,10个7）。
代码如下：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef unsigned long long ull;
#define For(i,s,t) for(int i = s; i != t; ++i) vector<ull> luckys;
ull p10[] = {, , }; // 对于二进制数 x 做一个简单的转换
inline ull trans(int x, int m) {
ull num = ;
For(j, , m)
num += ((x & ( << j)) ? : ) * p10[j];
return num;
} // 求所有含有num1个1和num1个0的2*num1位的二进制数
template <typename T>
inline void cal(int num1, vector<T> &vec) {
int Max = , high = num1 << ;
For(j, num1, high) Max |= ( << j);
int st = ;
For(j, , num1) st |= ( << j);
while(st <= Max) {
vec.push_back(trans(st, high));
int x = st & -st, y = st + x; // 这个是《挑战》书上的模板，从小到大枚举二进制数中含有固定数量'1'的所有数
st = ((st & ~y) / x >> ) | y;
}
} inline void init(int n = ) {
For(i, , )
p10[i] = p10[i - ] * ;
For(i, , n + )
cal(i, luckys);
} // 模板函数二分查找vec中大于等于x的第一个元素
template <typename T>
inline int _find(const vector<T> &vec, const T &x) {
int mid, low = , up = vec.size() - ;
while(low <= up) {
mid = low + ((up - low) >> );
if(x < vec[mid] || !(vec[mid] < x)) up = mid - ;
else low = mid + ;
}
return low;
} int main() {
init();
int t;
ull n;
scanf("%d", &t);
while(t--) {
scanf("%llu", &n);
if(n > ) puts(""); // 需要特判
else {
int id = _find(luckys, n);
printf("%llu\n", luckys[id]);
}
}
return ;
}
后来在网上看了下，发现还能直接深搜打表的，简单又清晰多了：
void dfs(ull sum, int num4, int num7) {
if(num4 == && num7 == ) {
luckys.push_back(sum);
return ;
}
if(num4) dfs(sum * + , num4 - , num7);
if(num7) dfs(sum * + , num4, num7 - );
}
inline void init() {
For(i, , )
dfs(, i, i);
}得到的同样是从小到大的顺序，dfs结束后不用再排序。