刀工对决

题目描述

为了争夺传说中的厨具永灵刀，特级厨师小当家和七星刀雷恩展开了神前刀工对决。对决总共有nn轮刀工测试，每轮给出两块鲷鱼肉，一块长度为，另一块长度为，厨师必须把这两份鲷鱼肉切成一样长。

已知小当家总共有两把菜刀，每把作用如下：

钢丝菜刀：若当前鲷鱼肉长度为的倍数，可以切掉三分之二的鲷鱼肉，切掉的部分必须扔掉，即变为。

百穴菜刀：若当前鲷鱼肉长度为的倍数，可以切掉五分之二的鲷鱼肉，切掉的部分必须扔掉，即变为。

小当家每使用菜刀切一刀鲷鱼肉就要花费秒，请问小当家完成轮测试的最短时间是多少。

输入描述:

第一行一个正整数，。
接下来行，每行两个正整数与，其中，。

输出描述:

输出小当家完成轮测试的最短时间，若小当家无法完成某一轮测试，输出。

各位注意，百穴菜刀是只能切掉的鱼片的！不是！！！

于是我便写了一个bfs，然后MLE了

#include <bits/stdc++.h>
using namespace std;
#define LL long long
struct node {
    LL a, b, step;
    node(int x = 0, int y = 0, int z = 0){a = x, b = y, step = z;}
};
queue<node> myq;
node st;
LL bfs()
{
    while(!myq.empty())
        myq.pop();
    myq.push(st);
    while(myq.size())
    {
        node tmp = myq.front();
        myq.pop();
        if(tmp.a == tmp.b)
            return tmp.step;
        if(tmp.a % 3 == 0)
            myq.push(node(tmp.a / 3, tmp.b, tmp.step + 1));
        if(tmp.a % 5 == 0)
            myq.push(node(tmp.a / 5 * 3, tmp.b, tmp.step + 1));
        if(tmp.b % 3 == 0)
            myq.push(node(tmp.a, tmp.b / 3, tmp.step + 1));
        if(tmp.b % 5 == 0)
            myq.push(node(tmp.a, tmp.b / 5 * 3, tmp.step + 1));
    }
    return -1;
}
int main()
{
    int n;
    LL a, b, ans = 0;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
    {
        scanf("%lld %lld", &a, &b);
        st = node(a, b, 0LL);
        if(a != b)
            if(bfs() == -1)
            {
                puts("-1");
                return 0;
            }
            else
                ans += bfs();
    }
    printf("%lld\n", ans);
    return 0;
}

现在我们来仔细分析一下这道题：

1. 如果输入的有解的话，那么a和b要么相等，要么都是由或组成的。
2. 再看看这两把菜刀怎么砍，如果是的话，就会变成，的话，就会变成，也可以看成这个变成了。

那么我们就可以这样做：
把a和b中的5全部变成3，但是如果有1个中的5变成3变完了，另外一个就不用了变了，然后再判断谁大谁小，然后再一直÷3，知道a和b相等为止

不多说了，上代码：

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, ans = 0, a, b;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d %d", &a, &b);
        if(a == b)
            continue;
        int cnta = 0, cntb = 0;
        while(a % 5 == 0)
        {
            a /= 5;
            a *= 3;
            cnta++;
        }
        while(b % 5 == 0)
        {
            b /= 5;
            b *= 3;
            cntb++;
        }
        int tmp = 0;
        if(cnta > cntb)
            tmp += cnta - cntb;
        if(cnta < cntb)
            tmp += cntb - cnta;
        cnta = 0, cntb = 0;
        if(a > b)
            while(a % 3 == 0 && a != b)
            {
                a /= 3;
                tmp++;
            }
        else
            while(b % 3 == 0 && b != a)
            {
                b /= 3;
                tmp++;
            }
        if(a != b)
        {
            printf("-1");
            return 0;
        }
        ans += tmp;
    }
    printf("%d\n", ans);
    return 0;
}

都看到这儿了，就点个赞吧~

（牛币+10086001）