题解 P6337 【[COCI2007-2008#2] CRNE】

· · 题解

前言 ：

题面传送们

blog

除出题人外第一个水掉此题的人来发一篇题解qwq~

这题其实就是一个传统的平面切蛋糕问题（不过说真的切棋盘有点过分了吧）

思路 ：

大家可以先在纸上试着画画模拟切棋盘的过程（注意题目中这句话：切与矩形的边平行的 n 次），可以列出下表：

切的刀数 棋盘最多被切成的块数
1 2
2 4
3 6
4 9
5 12
6 16
7 20
8 25
9 30
10 36

我们先看刀数为偶数的，

切的刀数 棋盘最多被切成的块数
2 4
4 9
6 16
8 25
10 36

上面表格中第二栏的数字仿佛似曾相识，没错就是 x^2 的形式，那么紧接着可以发现刀数 n 为偶数时，最多被切成的块数就是：

(\dfrac{n}{2}+1)^2

那么再推回去，就不难得出块数是：

(\dfrac{n}{2}+1)\times(n-\dfrac{n}{2}+1)

有了上面的公式，就可以一分钟出代码啦！

代码 ：

#include<bits/stdc++.h>
using namespace std;
int n;
int main()
{
    cin>>n;
    cout<<(n/2+1)*(n-n/2+1);//公式 
}