题目

分析

递归分析

首先，看到这个题，我们可以先从样例入手分析。看样例，容易发现每次剩下的长方形的宽就是上次长方形的长减宽，长就是上一个长方形的宽。（如果宽比长大，换一下顺序就可以了）

那我们就容易想到这道题可以用递归来解决。每次传入剩下的长方形的长和宽就行了。

直到长和宽有一个是零就可以了。

到这里，我们就可以写出递归的代码了。

递归代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#pragma GCC optimize(3)
#include<bits/stdc++.h>

using namespace std;

unsigned int totX,totY;
unsigned int RESULT;

void clac(unsigned int x,unsigned int y)
{
    if(x<y)//如果长比宽小，那就交换顺序，否则会出现负数 
    {
        swap(x,y);
    }
    if(x==0||y==0)
    {
        return;
    }
    if(x==1)
    {
        RESULT+=y;
        return;
    }
    if(y==1)
    {
        RESULT+=x;
        return;
    }
    //优化，如果长和宽有一个是一且都不是零，则还能分成的小正方形个数一定就是另一边的长度 
    RESULT++;
    clac(y,x-y);
}

int main()
{
    freopen("territory.in","r",stdin);
    freopen("territory.out","w",stdout);
    cin>>totX>>totY;
    clac(totX,totY);
    cout<<RESULT<<endl;
    fclose(stdin);
    fclose(stdout);
    return 0;
}

问题&解决方案

这么有理有据的递归代码，竟然会运行错误！！

测试点 输入文件 测试结果 运行用时 内存消耗 得分
#1 territory1.in 答案正确 0.000 s 2.543 MB 10
#2 territory2.in 答案正确 0.000 s 2.543 MB 10
#3 territory3.in 答案正确 0.000 s 2.535 MB 10
#4 territory4.in 答案正确 0.000 s 2.539 MB 10
#5 territory5.in 答案正确 0.000 s 2.535 MB 10
#6 territory6.in 答案正确 0.000 s 2.539 MB 10
#7 territory7.in 答案正确 0.000 s 2.539 MB 10
#8 territory8.in 运行时错误 不可用 不可用 0
#9 territory9.in 答案正确 0.000 s 3.547 MB 10
#10 territory10.in 答案正确 0.000 s 2.566 MB 10

康康测试点8的数据：

1
2 10000000

！！！！！

这么大的数据，结合上面的运行错误，明显这是爆栈了。

看来这个题不能使用递归。（那为什么还是递归测试[doge]）

明显只能使用循环了。

也很好写，只需要把刚才传入长和宽改为把长和宽存储在变量中，每次直接调用就可以了。

终极代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#pragma GCC optimize(3)
#include<bits/stdc++.h>

using namespace std;

int n,m,ans;

int main()
{
    freopen("territory.in","r",stdin);
    freopen("territory.out","w",stdout);
    cin>>n>>m;
    while(n&&m)
    {
        ans++;
        if(n==m)
        {
            cout<<ans<<endl;
            return 0;
        }
        if(n>m)
        {
            n-=m;
        }
        else
        {
            m-=n;
        }
    }
    return 0;
}