本文主要是介绍POJ 3909 Lucky numbers 深搜预存+二分，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
先用深搜将所有的lucky numbers 搜出来，然后再根据这些再深搜出所有的very lucky numbers，总共约35W个；最后输出数据时用二分查找进行计算
看别人的解题报告后，我也用了unique这个函数，这个函数具有去重功能，但实际上并不是删除重复的，而是将重复的放在整个数组后便，最后的返回值是新数组的尾地址，再减去首地址就能得到数组的大小了。
/*
ID: sdj22251
PROG: calfflac
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAX 100000000
#define LOCA
#define PI acos(-1.0)
using namespace std;
__int64 d[2000000];
int cnt = 0, ct;
__int64 mini = 1000000000000LL;
void dfs(int deep, __int64 k)
{if(deep > 12) return;d[cnt++] = k * 10 + 4;d[cnt++] = k * 10 + 7;dfs(deep + 1, k * 10 + 4);dfs(deep + 1, k * 10 + 7);
}
void dfs2(__int64 t, int k)
{int i;for(i = k; i < ct; i++){__int64 tmp = t * d[i];if(tmp <= mini && tmp > 0){d[cnt++] = tmp;dfs2(tmp, i);}else break;}
}
int main()
{
#ifdef LOCALfreopen("ride.in","r",stdin);freopen("ride.out","w",stdout);
#endifdfs(1, 0);sort(d, d + cnt);ct = cnt;dfs2(1, 0);sort(d, d + cnt);cnt = unique(d, d + cnt) - d;d[cnt] = mini + 5;int t;__int64 a, b;scanf("%d", &t);while(t--){scanf("%I64d%I64d", &a, &b);int high = cnt, low = 0, mid, s1, s2;bool flag = false;bool flag2 = false;while(low <= high){mid = (low + high) / 2;if(d[mid] == a) flag = true;if(d[mid] > a){high = mid - 1;}else low = mid + 1;}s1 = high + 1;low = 0;high = cnt;while(low <= high){mid = (low + high) / 2;if(d[mid] == b) flag2 = true;if(d[mid] > b){high = mid - 1;}else low = mid + 1;}s2 = high + 1;int ans = abs(s2 - s1);if(flag) ans++;printf("%d\n", ans);}return 0;
}
这篇关于POJ 3909 Lucky numbers 深搜预存+二分的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
