首页 > 代码库 > hdu 1104 数论+bfs

hdu 1104 数论+bfs

2024-07-02 03:31:39   232人阅读

题意：给n,m，k;输出n经过+-*%后(n%k+k)%k==((n+1)%k)%k  输出最小路径与运算副

zsd：% 只是求余数 有正负 mod 是求模 无正负、

yhd:对m*k求余对 对k求余不对

?
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
#include<iostream>
#include<queue>
using namespace std;
struct Node
{
    int x;
    int step;
    queue<char> q;
};
int v[1000010];
int n,m,k;
bool bfs()
{
    int s=((n+1)%k+k)%k;
    queue<Node>q;
    Node now,next;
    now.x=n;now.step=0;
    q.push(now);
    memset(v,0,sizeof(v));
    while(!q.empty())
    {
        now=q.front();
        if((now.x%k+k)%k==s)
        {
            printf("%d\n",now.step);
            while(now.step--)
            {
                printf("%c",now.q.front());
                now.q.pop();
            }
            printf("\n");
            return true;
        }
        q.pop();
        int xx;
        xx=(now.x+m)%(k*m);
        if(!v[(xx%k+k)%k])
        {
            v[(xx%k+k)%k]=1;
            next=now;next.x=xx;next.q.push(‘+‘);next.step++;
            q.push(next);
        }
        xx=(now.x-m)%(k*m);
        if(!v[(xx%k+k)%k])
        {
             v[(xx%k+k)%k]=1;
            next=now;next.x=xx;next.q.push(‘-‘);next.step++;
            q.push(next);
        }
        xx=(now.x*m)%(k*m);//因为xx会变得很大 所以要求余变小
        if(!v[(xx%k+k)%k])
        {
            v[(xx%k+k)%k]=1;
            next=now;next.x=xx;next.q.push(‘*‘);next.step++;
            q.push(next);
        }
        xx=((now.x%m+m)%m)%(m*k);
        if(!v[(xx%k+k)%k])
        {v[(xx%k+k)%k]=1;
        next=now;next.x=xx;next.q.push(‘%‘);next.step++;
        q.push(next);
        }
    }
    return 0;
}
int main()
{
 
    while(scanf("%d%d%d",&n,&k,&m)!=EOF)
    {
        if(n==0&&k==0&&m==0)
            break;
        if(!bfs())
            printf("0\n");
    }
    return 0;
}

 


联系
我们