首页 > 代码库 > hdu 1104 Remainder

hdu 1104 Remainder

2024-07-14 22:39:45   222人阅读

http://acm.hdu.edu.cn/showproblem.php?pid=1104

a%b=(a%b+b)%b;

题意：开始给了你n, k, m，每次由+m, -m, *m, modm得到新的N，继续对N这样的操作,直到(n+1) mod k== N mod k时结束，并且打印路径

 1 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 #include <queue> 5 #include <string> 6 #include <algorithm> 7 using namespace std; 8 char str[4]={‘+‘,‘-‘,‘*‘,‘%‘}; 9 int n,k,m;10 bool vis[200000];11 struct node12 {13     int num;14     int step;15     string st;16 }st1,st2;17 18 void bfs()19 {20     memset(vis,false,sizeof(vis));21     queue<node>q;22     st1.num=n;23     st1.step=0;24     st1.st="";25     q.push(st1);26     vis[((n%k)+k)%k]=true;27     while(!q.empty())28     {29        st2=q.front();30        q.pop();31        if(((n+1)%k+k)%k==((st2.num%k)+k)%k)32        {33            printf("%d\n",st2.step);34            cout<<st2.st<<endl;35            return ;36        }37        for(int i=0; i<4; i++)38        {39            if(i==0)40            {41                st1.num=(st2.num+m)%(k*m);42                st1.st=st2.st+‘+‘;43            }44            else if(i==1)45            {46                st1.num=(st2.num-m)%(k*m);47                st1.st=st2.st+‘-‘;48            }49            else if(i==2)50            {51                st1.num=(st2.num*m)%(k*m);52                st1.st=st2.st+‘*‘;53            }54            else55            {56                st1.num=(st2.num%m+m)%m%(k*m);57                st1.st=st2.st+‘%‘;58            }59            st1.step=st2.step+1;60            if(!vis[(st1.num%k+k)%k])61            {62                q.push(st1);63                vis[(st1.num%k+k)%k]=true;64            }65        }66     }67     printf("0\n");68 }69 70 int main()71 {72     while(scanf("%d%d%d",&n,&k,&m)!=EOF)73     {74         if(n==0&&k==0&&m==0) break;75         bfs();76     }77     return 0;78 }
View Code

 


联系
我们