2010-1086

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

by yuxingdubai

典故(题目来源?):
{{{
这道题来源是一个很经典的笑话,说: 一个蛋糕用3刀,怎么分给5个小朋友.
那道题的解答是先两刀把蛋糕切成4份, 然后最后一刀砍死一个小朋友..

= = 嗯.... 以上..
}}}

解题报告:
{{{
这题中的clone操作就和"砍死小朋友的一样的". 在理解的题意的时候要注意这个蛋糕必须是全部切完了再复制其中的某一块, 可以复制很多次.(不能切的时候复制)
而且切蛋糕的时候是全部切完了再把蛋糕分开.. 即一刀不能切在其中的一部分上..
转化成数学模型就是求竖切cv刀, 横切ch刀, 最后clone i次后, 蛋糕数量为n.

    cv + ch + i == m;
    if(cv != 0) 2 * cv * (1+ch) + i == n;
    if(cv == 0) 1+ch + i == n;

要求 i 最小情况下的整数解.
我用搜索的方法过的.
搜索时从 i = 0 开始, 保证第一个解就是要输出的解.
因为竖切多切一刀就可以把让蛋糕数量x2, 而横切多切一刀只会让蛋糕数量+1,
所以要从 ch = m - i 开始慢慢增加 cv , 减少 ch , 直到蛋糕数量大于 n 跳出循环.
}}}

代码:
{{{
#!cpp
#include<cstdio>
using namespace std;
int main(){
    int i, t, n, m, r, cv;
    scanf("%d", &t);
    while(t--){
        scanf("%d%d", &n, &m);
        r = -1;
        for(i = m; i >= 0; i--){
            if((i+1)+(m-i) == n){ r = m-i; break;}
            for(cv = 1; cv < i && 2*cv*(1+i-cv)+(m-i) <= n; cv++)
                if(2*cv*(1+i-cv)+(m-i) == n){ r = m-i; break;}
            if(r != -1) break;
        }
        printf("%d\n", r);
    }
    return 0;
}
}}}

by yuxingdubai

典故(题目来源?):

这道题来源是一个很经典的笑话,说: 一个蛋糕用3刀,怎么分给5个小朋友.
那道题的解答是先两刀把蛋糕切成4份, 然后最后一刀砍死一个小朋友..
= = 嗯.... 以上..

解题报告:

这题中的clone操作就和"砍死小朋友的一样的". 在理解的题意的时候要注意这个蛋糕必须是全部切完了再复制其中的某一块, 可以复制很多次.(不能切的时候复制)
而且切蛋糕的时候是全部切完了再把蛋糕分开.. 即一刀不能切在其中的一部分上..
转化成数学模型就是求竖切cv刀, 横切ch刀, 最后clone i次后, 蛋糕数量为n.
    cv + ch + i == m;
    if(cv != 0) 2 * cv * (1+ch) + i == n;
    if(cv == 0) 1+ch + i == n;
要求 i 最小情况下的整数解.
我用搜索的方法过的.
搜索时从 i = 0 开始, 保证第一个解就是要输出的解.
因为竖切多切一刀就可以把让蛋糕数量x2, 而横切多切一刀只会让蛋糕数量+1,
所以要从 ch = m - i 开始慢慢增加 cv , 减少 ch , 直到蛋糕数量大于 n 跳出循环.

代码:

#include<cstdio>
using namespace std;
int main(){
    int i, t, n, m, r, cv;
    scanf("%d", &t);
    while(t--){
        scanf("%d%d", &n, &m);
        r = -1;
        for(i = m; i >= 0; i--){
            if((i+1)+(m-i) == n){ r = m-i; break;}
            for(cv = 1; cv < i && 2*cv*(1+i-cv)+(m-i) <= n; cv++)
                if(2*cv*(1+i-cv)+(m-i) == n){ r = m-i; break;}
            if(r != -1) break;
        }
        printf("%d\n", r);
    }
    return 0;
}