专栏文章

题解：P14039 [PAIO 2025] Cake

GGeorgeDeng
P14039题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minpsge5
此快照首次捕获于
2025/12/02 06:22
3 个月前
此快照最后确认于
2025/12/02 06:22
3 个月前
查看原文
红题交互是什么鬼？？？
别看是交互题，其实就是让你实现一个函数，完成题目指定操作。
因为我习惯 nn 表示行，mm 表示列，所以本题解的表述都以这个为准。
首先暴力是很好做的：对于一个 n×mn\times m 的矩形。我们判断 nn 和 mm 的大小。如果 n=mn=m，说明只需要再分一次，就可以了；如果 n>mn>m，说明是横着切一刀，n←n−mn\larr n-m，其中 ←\larr 表示复制操作；否则，同理，m←m−nm\larr m-n。
这样我们就能拿到暴力 7676 分了！
我们考虑优化。上面如果两个东西成倍数关系的话，就会重复执行很多次，所以我们只需要把重复的减法改成更快速的除法就行了。但是需要注意：我们在 n=mn=m 的情况下还是要算进答案里的，这里特殊处理一下就可以了。
AC 代码：
CPP
#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;
// }

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...