P9736题解

· · 题解

P9736题目解析:

看到题目，A 和 B 一开始就是 x 和 y，而要得到的是 x \times y，所以只要把 x 加上 y 次或者把 y 加上 x 次即可。

发现 C 的初始值为 0，所以可以把所有值都丢到 C 里面。

然后我们发现，每次进行 A A A 的操作时，变量 A 都会乘 2，于是很自然的想到 2 进制，所以我们就想到把其中一个作为基准，把另外一个数转化为 2 进制，遍历每一位，是 1 就加，非 1 就不加，就可以得到答案了。

问题来了，是不是两个数都可以作为基准呢？

从本质上来讲，其实是可以的，但题目中有一句话：

请你使用该种操作不超过 100 次

所以就不行，因为大的数要的操作次数自然也会变多，但是你并不能保证大的数的操作数不超过 100 次,而小的数一定比大的更优，所以该选小的，这篇题解和这篇题解在这方面就有问题，但是这题并不卡这一点。

注意：x \times y \le 10^{18}，记得开 long long

这篇题解就没开 long long。

AC Code:

#include<bits/stdc++.h>
#define int long long
//切记，一定开long long
using namespace std;
int x,y;
vector<string>s;
signed main(){
    cin >> x >> y;
    if(y<x){
        //选择小的切 
        while(y){
            //判断是否要加 
            if(y%2==0)s.push_back("A A A");//A*=2
            else{
                s.push_back("A C C");//C+=A
                s.push_back("A A A");//A*=2
            }
            y/=2;
        }
    }
    else{
        while(x){
            //判断是否要加 
            if(x%2==0)s.push_back("B B B");//B*=2
            else{
                s.push_back("B C C");//C+=B
                s.push_back("B B B");//B*=2
            }
            x/=2;
        }
    }   
    cout << s.size() << "\n";
    for(int i = 0;i<s.size();i++)cout << s[i] << "\n";//输出 
    cout << "C";//答案存在C中，输出C 
    return 0;
}

结束语：此题难度并不大，但仍有很多细节需要注意，值得回味。