先用深搜将所有的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 LOCAL
freopen("ride.in","r",stdin);
freopen("ride.out","w",stdout);
#endif
dfs(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;
}
分享到:
相关推荐
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
北大POJ3026-Borg Maze【BFS+Prim】 解题报告+AC代码
北大POJ初级-所有题目AC代码+解题报告
北大POJ3733-Changing Digits【DFS+强剪枝】 解题报告+AC代码
北大POJ3373-Changing Digits【DFS+强剪枝】 解题报告+AC代码
北大POJ3252-Round Numbers 解题报告+AC代码
POJ2186-Popular Cows 【Tarjan+极大强连通分量+缩点】 解题报告+AC代码 http://hi.csdn.net/!s/BGDH68 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
各种搜索算法,配合POJ上的题目,含标程,及各题解题思路。
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
北大POJ1016-Numbers That Count【字符串处理】 解题报告+AC代码
NULL 博文链接:https://128kj.iteye.com/blog/1750462
1.把自己的污水排到河里V 2.把自己的污水送到右边> 3.把自己的污水送到左边
北大POJ初级-简单搜索 解题报告+AC代码
北大POJ初级题-数据结构:解题报告+AC代码
NULL 博文链接:https://128kj.iteye.com/blog/1745671
北大POJ2187-Beauty Contest 解题报告+AC代码
北大POJ1416-Shredding Company 解题报告+AC代码
北大POJ1163-The Triangle 解题报告+AC代码
北大POJ1019-Number Sequence 解题报告+AC代码
北大POJ3126-Prime Path 解题报告+AC代码