题解：P14039 [PAIO 2025] Cake

GeorgeDeng · 2025-10-03 17:02:21 · 题解

红题交互是什么鬼？？？

别看是交互题，其实就是让你实现一个函数，完成题目指定操作。

因为我习惯 n 表示行，m 表示列，所以本题解的表述都以这个为准。

首先暴力是很好做的：对于一个 n\times m 的矩形。我们判断 n 和 m 的大小。如果 n=m，说明只需要再分一次，就可以了；如果 n>m，说明是横着切一刀，n\larr n-m，其中 \larr 表示复制操作；否则，同理，m\larr m-n。

这样我们就能拿到暴力 76 分了！

我们考虑优化。上面如果两个东西成倍数关系的话，就会重复执行很多次，所以我们只需要把重复的减法改成更快速的除法就行了。但是需要注意：我们在 n=m 的情况下还是要算进答案里的，这里特殊处理一下就可以了。

AC 代码：

#include <iostream>
using namespace std;

int count_square_cakes(int n, int m){
    swap(n,m);
    int cnt = 0;
    while(n!=0&&m!=0){
        // cout<<cnt<<' '<<n<<' '<<m<<endl;
        // cnt++;
        if(n==m){
            cnt++;//特殊处理
            break;
        }
        if(n<m){
            cnt+=m/n;//可以切 m/n 刀
            m%=n;
            // m-=n;
        }else{
            cnt+=n/m;//同理
            n%=m;
            // n-=m;
        }
        // cout<<cnt<<' '<<n<<' '<<m<<endl;
    }
    return cnt;
}

//========下面是调试代码========

// int main()
// {
//     int _;
//     cin>>_;
//     while(_--){
//         int n,m;
//         cin>>n>>m;
//         cout<<count_square_cakes(n,m)<<endl;
//     }
//     return 0;
// }