Fox Dividing Cheese [CF-371B]-白红宇的个人博客

Fox Dividing Cheese [CF-371B]

发布日期：2021-08-25 16:21:08 浏览次数：2 分类：技术文章

本文共 1705 字，大约阅读时间需要 5 分钟。

暴力一点的写法：bfs搜索（可以过，但是有更优的做法），共六种拓展方向，优化一点是：吃大的。

代码：

#include
     
      #include
      
       #include
       
         #include
        
         #include
         
          #define LL long longusing namespace std;int a0,b0,ans=100000000;struct H{    int a;    int b;    int step=0;};queue 
          
            q;int flag=0,f=0;void change1(H l){ H p; if(l.a%2==0){ p=l; p.a/=2;p.step++; if(p.a==p.b){flag=1;ans=min(ans,p.step);} q.push(p); } if(l.a%3==0){ p=l; p.a=p.a/3;p.step++; if(p.a==p.b){flag=1;ans=min(ans,p.step);} q.push(p); } if(l.a%5==0){ p=l; p.a=p.a/5;p.step++; if(p.a==p.b){flag=1;ans=min(ans,p.step);} q.push(p); }}void change2(H l){ H p; if(l.b%2==0){ p=l; p.b=p.b/2;p.step++; if(p.a==p.b){flag=1;ans=min(ans,p.step);} q.push(p); } if(l.b%3==0){ p=l; p.b=p.b/3;p.step++; if(p.a==p.b){flag=1;ans=min(ans,p.step);} q.push(p); } if(l.b%5==0){ p=l; p.b=p.b/5;p.step++; if(p.a==p.b){flag=1;ans=min(ans,p.step);} q.push(p); }}int main(){ scanf("%d%d",&a0,&b0); if(a0==b0){ printf("0\n");return 0;} H l; l.a=a0;l.b=b0; q.push(l); while(!q.empty()) { f=0; l=q.front(); q.pop(); if(l.a==l.b) break; if(l.a>l.b) change1(l); else change2(l); if(flag) break; } if(flag)printf("%d\n",ans); else printf("-1\n"); return 0;}

第二种做法：根据题意可知，两块蛋糕最后一定变为a,b的最大公约数c，结果就是a/c，b/c对于2,3,5分解质因数能分解几次的次数之和，若不能分解为1，就是-1

#include
     
      #include
      
       #include
       
         #include
        
         #include
         
          #define LL long longusing namespace std;int a,b,c;int gcd(int x,int y){    if(x
          
           =0&&a2>=0) printf("%d\n",a1+a2);//注意判断条件:应该是都不是-1 else printf("-1\n"); return 0;}

转载于:https://www.cnblogs.com/dfsac/p/7587903.html

转载地址：https://blog.csdn.net/weixin_33858485/article/details/92954735 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：grep使用示例

下一篇：清华梦的粉碎--写给清华大学的退学申请

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章