Fxx and game（搜索加剪枝或者单调队列加dp） Fxx and game

128 阅读 0 评论 85 点赞

我是靠谱客的博主可靠星星，这篇文章主要介绍Fxx and game（搜索加剪枝或者单调队列加dp） Fxx and game，现在分享给大家，希望可以做个参考。

Fxx and game

Time Limit: 3000/1500 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)
Total Submission(s): 1446 Accepted Submission(s): 378

Problem Description

Young theoretical computer scientist Fxx designed a game for his students.

In each game, you will get three integers

X,k,t .In each step, you can only do one of the following moves:

1.X=X−i(0<=i<=t) .

2. if

k|X,X=X/k .

Now Fxx wants you to tell him the minimum steps to make

X become 1.

Input

In the first line, there is an integer

T(1≤T≤20) indicating the number of test cases.

As for the following

T lines, each line contains three integers

X,k,t(0≤t≤106,1≤X,k≤106)

For each text case,we assure that it's possible to make

X become 1。

Output

For each test case, output the answer.

Sample Input

复制代码

Sample Output

复制代码

代码：

复制代码

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<queue>
using namespace std;
int a,b,c;
int flag;
int vis[1000010];
int scan()
{
    int res=0,flag=0;
    char ch;
    if((ch=getchar())=='-')
        flag=1;
    else  if(ch>='0'&&ch<='9')
        res=ch-'0';
    while((ch=getchar())>='0'&&ch<='9')
        res=res*10+(ch-'0');
    return flag?-res:res;

}
//void out (int a)
//{
//    if(a<0)
//    {
//        putchar('-');
//        a=-a;
//    }
//    if(a>=10)
//    {
//        out(a/10);
//        putchar(a%10+'0');
//    }
//}
struct qq
{
    int x,y;
} q1,w1;
void  bfs(int a)
{
    q1.x=a;
    q1.y=0;
    queue<qq>w;
    while(!w.empty())
    {
        w.pop();
    }
    w.push(q1);
    while(!w.empty())
    {
        w1=w.front();
        if(w1.x==1)
        {
            flag=w1.y;
            return ;
        }
        w.pop();
        if(w1.x%b==0&&vis[w1.x/b]==0)
        {
            q1.x=w1.x/b;
            q1.y=w1.y+1;
            vis[w1.x/b]=1;
            w.push(q1);
        }
        int minn=min(c,w1.x-1);
        for(int i=minn; i>=1; i--)
        {

if(w1.x-i>=1&&vis[w1.x-i]==0)
            {
                q1.x=w1.x-i;
                q1.y=w1.y+1;
                vis[w1.x-i]=1;
                w.push(q1);
            }
            else
                break;

}
    }
}
int main()
{
    int q;
    scanf("%d",&q);
    while(q--)
    {
//        int a,b,c;
        memset(vis,0,sizeof(vis));
        a=scan();
        b=scan(),c=scan();
//        scanf("%d%d%d",&a,&b,&c);
        if(b==1)
        {
            int ss=0;
            if((a-1)%c!=0)
                ss=1;
            printf("%dn",(a-1)/c+ss);
            continue;
        }
        else  if(c==0)
        {
            int sum=0;
            while(a!=1)
            {
                a/=b;
                sum++;
            }
            printf("%dn",sum);
            continue;
        }
        vis[a]=1;
        bfs(a);
//        out(flag);
//        printf("n");
        printf("%dn",flag);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<queue>
using namespace std;
int a,b,c;
int flag;
int vis[1000010];
int scan()
{
    int res=0,flag=0;
    char ch;
    if((ch=getchar())=='-')
        flag=1;
    else  if(ch>='0'&&ch<='9')
        res=ch-'0';
    while((ch=getchar())>='0'&&ch<='9')
        res=res*10+(ch-'0');
    return flag?-res:res;

}
//void out (int a)
//{
//    if(a<0)
//    {
//        putchar('-');
//        a=-a;
//    }
//    if(a>=10)
//    {
//        out(a/10);
//        putchar(a%10+'0');
//    }
//}
struct qq
{
    int x,y;
} q1,w1;
void  bfs(int a)
{
    q1.x=a;
    q1.y=0;
    queue<qq>w;
    while(!w.empty())
    {
        w.pop();
    }
    w.push(q1);
    while(!w.empty())
    {
        w1=w.front();
        if(w1.x==1)
        {
            flag=w1.y;
            return ;
        }
        w.pop();
        if(w1.x%b==0&&vis[w1.x/b]==0)
        {
            q1.x=w1.x/b;
            q1.y=w1.y+1;
            vis[w1.x/b]=1;
            w.push(q1);
        }
        int minn=min(c,w1.x-1);
        for(int i=minn; i>=1; i--)
        {

            if(w1.x-i>=1&&vis[w1.x-i]==0)
            {
                q1.x=w1.x-i;
                q1.y=w1.y+1;
                vis[w1.x-i]=1;
                w.push(q1);
            }
            else
                break;

        }
    }
}
int main()
{
    int q;
    scanf("%d",&q);
    while(q--)
    {
//        int a,b,c;
        memset(vis,0,sizeof(vis));
        a=scan();
        b=scan(),c=scan();
//        scanf("%d%d%d",&a,&b,&c);
        if(b==1)
        {
            int ss=0;
            if((a-1)%c!=0)
                ss=1;
            printf("%dn",(a-1)/c+ss);
            continue;
        }
        else  if(c==0)
        {
            int sum=0;
            while(a!=1)
            {
                a/=b;
                sum++;
            }
            printf("%dn",sum);
            continue;
        }
        vis[a]=1;
        bfs(a);
//        out(flag);
//        printf("n");
        printf("%dn",flag);
    }
}

这里有一个剪枝很重要，就是遍历那个减得那个状态的时候，当发现小的元素已经存在的时候，后面就不必要再遍历了，直接跳出来就好了！！！！！厉害厉害！！！！