HDU5167 – Fibonacci(dfs暴搜)

题目链接:HDU5167

【题意】判断一个数N(<=10^9)是否能表示为斐波那契数列中的数的乘积。

【分析】比赛的时候搞个离线,结果离线写错了,悲剧呀,改成预处理就好了,直接dfs暴搜我用HASH存出现过的数字。

【AC CODE】218ms

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <map>
//#include <unordered_map>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 44, MAXM = 1000000000;
const LL MOD = 1000007;
LL fb[100];
int t,mx;
struct HASH{
    int head[MOD], next[2371715+10], sum[2371715+10], cnt, node[2371715+10];
    void clear(){
        cnt = 0;
        clc(head,-1);
        clc(sum,0);
    }
    int hash(LL s){
        return s%MOD;
    }
    void insert(LL s){
        int id = hash(s);
        int u = head[id];
        while(~u){
            if(s == node[u])
            {
                sum[u]++;
                return;
            }
            u = next[u];
        }
        sum[cnt] = 1;
        node[cnt] = s;
        next[cnt] = head[id];
        head[id] = cnt++;
    }
    int query(LL s){
        int id = hash(s);
        int u = head[id];
        while(~u){
            if(node[u] == s) return sum[u];
            u = next[u];
        }
        return -1;
    }
}vis;


void dfs(LL num)
{
	if(0 <= num && num <= MAXM)
		vis.insert(num);
	else return;
	repe(i,2,MAXN)
	{
		LL to = num*fb[i];
		if(-1 == vis.query(to))
			dfs(to);
	}
}
int main()
{
#ifdef SHY
	freopen("e:\\1.txt", "r", stdin);
	//freopen("e:\\out.txt", "w", stdout);
#endif
	fb[0] = 0, fb[1] = 1;
	repe(i,2,MAXN) fb[i] = fb[i-1]+fb[i-2];
	vis.clear();
	vis.insert(0);
	dfs(1);
	scanf("%d%*c", &t);
	while(t--)
	{
		int n;
		scanf("%d%*c", &n);
		if(~vis.query(n)) puts("Yes");
		else puts("No");
	}
	return 0;
}
/*
7
4
17
233
34
7
0
34
=====
Yes
No
Yes
Yes
No
Yes
Yes
*/

 

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

请输入正确的验证码