注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

POJ1945Power Hungry Cows题解  

2014-03-09 19:07:39|  分类: POJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
                                                                         奶牛求幂
                                                        BY   LGS
题目大意:有两个数字,x,1。它们每次可以乘、或除并覆盖其中任意一个,也可以自己乘自己。求最少多少次操作后变成了X^N次。读入一个N。

题解:明显是BFS,一开始以为会超时,所以看了题解,发现了一个神剪枝:两个数中的其中一个只需枚举到200即可。这样首先HASH是必要的,HASH[20001][201]的bool型空间可以承受,其次由于POJ上只允许30MB的空间,而用三个队列分别记录:X,Y,答案步数。一共要20000*200*3的int类型,会爆空间,所以需要用到循环队列。这样时间空间都可以承受了。状态一共有8种,自己写吧,BFS基础。

总结:BFS基础题,用到hash+循环队列。共47行

核心代码:
void push()
 {
 if (xx<yy) swap();
 if ((xx<=20000)&&(yy<=300))
       if (!hash[xx][yy])
            {
            w=(w%xh)+1;
            la[w]=xx;lb[w]=yy;
            lans[w]=lans[t]+1;
            hash[xx][yy]=true;
 if ((xx==p)||(yy==p)){printf("%d",lans[w]);//for(;;);
 exit(0);}
            }
 }
  评论这张
 
阅读(40)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018