P9736 [COCI2022-2023#2] Ekspert 题解

DF_cloud · 2023-10-10 18:18:57 · 题解

考虑一下式子 x+x=2x \ 2x+2x=4x \ 4x+4x=8x 不难看出，我们可以通过加法得到 2^i\times x，我们可以把 y 转换为二进制，记 Y_i 为 y 在二进制下的第 i 位，则 x\times y=\sum_{i}^{}Y_i\times x。因为我们要使 n 尽可能的小，所以我们会选择枚举较小的数。（一些具体的东西可以看注释）

#include<bits/stdc++.h>
using namespace std;
long long x,y;
vector<string> opt;
int main(){
    cin>>x>>y;
    long long a,b,c;
    a=x,b=y,c=0;//这里没有用到D
    //枚举较小的数
    if(x<y){
        while(x){
            if(x%2){
                //如果当前x的位为一才累加进答案
                opt.push_back("B C C");
                c=b+c;
            }
            opt.push_back("B B B");
            //2^i*x+2^i*x=2^(i+1)*x
            b=b*2;
            x=x/2;
        }
    }
    else{
        while(y){
            if(y%2){
                opt.push_back("A C C");
                c=a+c;
            }
            opt.push_back("A A A");
            a=a*2;
            y=y/2;
        }
    }
    cout<<opt.size()<<endl;
    for(auto i:opt){
        cout<<i<<endl;
    }
    cout<<"C"<<endl;
    return 0;
}

提交记录