首页 > 代码库 > HDU 1104 Remainder （BFS求最小步数 打印路径）
HDU 1104 Remainder （BFS求最小步数 打印路径）
题目链接
题意 ： 给你N，K,M，N可以+，- ，*，% M，然后变为新的N，问你最少几次操作能使（原来的N+1）%K与（新的N）%k相等。并输出相应的操作。
思路 ： 首先要注意题中给的%，是要将负数变为正数的，所以取余的时候要注意，又因为各种问题……
% 的问题是：a mod b = (a % b + b) % b，不是平常的取余。
讨论里有个人是这样说的：
关于此题的用bfs搜索，大家都是知道的。既然使用了bfs，则队列是少不了的，为了叙述的方便，记运算符集合 oper = {+,-,*,%}, op = {+,-,*}, pe = {+,-,%}。N在经过一些列的运算，可能会很大，所以溢出问题，需要考虑充分。因为最后比较的是两个数对k取余是否相等，因此，在队列中存储对k取余后的值，各种文章中谈论的都是 ((n oper m)%k oper m)%k 是不是等于(n oper m oper m)%k对于op运算是成立的，但是%参与时，结果是不等。例如： 记n = 2, m = 8, k =3. 则((n * m)%k % m)%k = 1 而(n * m % m)%k = 0。关于另一个结论：%只能出现在第一个位置或者出现在*的后面，且%最多只能出现两次。 因为对任意n,( n pe m ) % m = n % m. 对于乘法则是不一定的，n * m % m 必为0。 由于一系列{+,-,%}运算相当于在n的基础上，‘+’相当于加上若干个m，‘-’相当于减去若干个m，‘%’相当于一次同时减去（或者加上）若干个m。而他们的总和带来的结果就是n的变化是m的整数倍，所以上面的式子相等。也就是说如果有一个序列中有‘%’，则它的前面要么是空的，要么是‘*’，因为如果是其他的只会使得操作序列更长。例如： +-+-+++%+*+-*-*可以变成%+*+-*-*，后者比前者更短。 *%+-+-***-+*%+*这样的路径也是不存在的，因为*%使得n为0，而后面的*%也为0， 重复，所以不会入队列的。因为‘%’出现的情况很有限，并且出现的位置，也可以知道。特殊处理一下，就可以了。其他的对k取余没有问题。
1 #include <stdio.h> 2 #include <string.h> 3 #include <string> 4 #include <iostream> 5 #include <queue> 6 using namespace std ; 7 8 struct node 9 {10 int step ;11 int an ;12 string ch ;13 } p,q,temp;14 int vis[1001000] ;15 int n,m,k,km ;16 void bfs()17 {18 queue<node>Q ;19 memset(vis,0,sizeof(vis)) ;20 p.an = (n % km) + km ;21 vis[p.an] = 1 ;22 p.step = 0 ;23 Q.push(p) ;24 while(!Q.empty())25 {26 q = Q.front();27 Q.pop();28 if(q.an % k == ((n + 1) % k + k)%k )29 {30 printf("%d\n",q.step) ;31 cout<<q.ch<<endl;32 return ;33 }34 int x = q.an;35 temp.step = q.step + 1 ;36 for(int i = 0 ; i < 4 ; i++)37 {38 if(i == 0)39 {40 temp.an = (x+m) % km;41 temp.ch = q.ch+‘+‘ ;42 }43 else if(i == 1)44 {45 temp.an = ((x-m)%km+km)%km;46 temp.ch = q.ch+‘-‘ ;47 }48 else if(i == 2)49 {50 temp.an = (x*m)%km;51 temp.ch = q.ch+‘*‘ ;52 }53 else if(i == 3)54 {55 temp.an = (x%m)%km;56 temp.ch = q.ch+‘%‘ ;57 }58 if(!vis[temp.an])59 {60 Q.push(temp) ;61 vis[temp.an] = 1 ;62 }63 }64 }65 printf("0\n") ;66 }67 68 int main()69 {70 71 while(~scanf("%d %d %d",&n,&k,&m))72 {73 if(n == 0 && m == 0 && k == 0) break ;74 km = k*m ;75 bfs() ;76 }77 return 0 ;78 }
HDU 1104 Remainder （BFS求最小步数 打印路径）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。