题解 CF1829D Gold Rush

cjh20090318 · 2023-05-07 20:42:36 · 题解

大家好，我是 CQ-C2024 蒟蒻 CJH。

题意

本题有多组数据。

给你一堆金条，有 n 个，你可以把一堆金条刚好分成两份使得其中一堆金条的数量正好为另外一堆数量的 2 倍。

问你有没有一种分割方法使得其中一堆金条的数量为 m。

分析

由题意，一堆能分割的金条必须为 3 的倍数。

如果这一堆金条的数量为 m，那么一定输出 YES。

如果这一堆金条的数量（这里设为 a）为 3 的倍数，那么就把它分割为 \dfrac{1}{3}a 和 \dfrac{2}{3}a。

就可以直接用 vector 来存每一堆金条，然后遍历每一堆金条进行操作即可。

代码

//the code is from chenjh
#include<cstdio>
#include<vector>
std::vector<int> a;
void solve(){
    int n,m;scanf("%d%d",&n,&m);
    if(n<=m){puts(n==m?"YES":"NO");return;}
    a.clear();//注意清空 vector。
    a.push_back(n);//加入第一堆金条。
    int size=1;
    while(1){
        for(int i=0;i<size;i++){//遍历 vector。
            if(a[i]==m){puts("YES");return;}//这一堆金条数量为 m 直接输出 "YES"。
            if(!(a[i]%3)) a.push_back(a[i]/3*2),a[i]/=3;//这一堆为 3 的倍数，将当前堆直接修改，另加一堆至 vector 末尾。
        }
        if(a.size()>size)size=a.size();//更新 vector 长度。
        else{puts("NO");return;}//当前长度没有变化，说明已经无解。
    }
    puts("YES");
}
int main(){
    int T;scanf("%d",&T);
    while(T--) solve();
    return 0;
}