洛谷 P7695 [COCI2009-2010#4] PLANINA

题目背景

Mirko 和 Slavko 正在拍摄一部改编自科幻小说 Chicks in space 13 的电影。剧本要求他们呈现出不同的世界，所以他们决定在绿屏幕前拍摄整部电影，之后再添加 CGI 背景。Mirko 听说生成人工地形最好的办法是使用中点位移算法。

题目描述

为了执行这个算法，Mirko 选择了 $4$ 个点组成了一个完美正方形。然后他开始执行以下步骤：

• 在每个正方形的每一条边上，Mirko 都在正中间添加一个新点。这个新点上的地形高度是他所在这条边两个点上的平均高度。
• 在每个正方形的正中间，Mirko 也添加了一个新点。这个新点上的地形高度是所有 $4$ 个正方形定点的平均高度加上一个小的随机值。

Mirko 在执行完一次上面的所有操作后拥有了 $4$ 个新的方块。于是他不断地新建正方形，直到他对结果满意为止。下图说明了算法的初始状态、$1$ 次迭代和 $2$ 次迭代。

Mirko 发现到有些点属于不止一个正方形，为了减少内存消耗，他只存储这些点一次，但是一旦这个点存储进去了，它就会永远储存在内存中。现在他想请你编写一个程序，告诉他经过 $n$ 次迭代之后，总共需要在内存中存储多少点。

输入格式

输入仅一个整数 $n$，表示迭代的次数。

输出格式

输出仅一个整数，表示 $n$ 次迭代后内存内需要存储的点数。

样例 #1

样例输入 #1

1
1

样例输出 #1

9
1

样例 #2

样例输入 #2

2
1

样例输出 #2

25
1

样例 #3

样例输入 #3

5
1

样例输出 #3

1089
1

提示

【数据范围】

对于所有数据，$1⩽n⩽15$。

【题目来源】

本题来源自 COCI 2009-2010 CONTEST 4 T2 PLANINA，按照原题数据配置，满分 $50$ 分。

由 Eason_AC 翻译整理提供。

分析：

我们很容易找到一个规律：所有的点数=(2^n+1)^2，所以直接输出就行了。

代码：

#include

using namespace std;

long long n;

int main()
{
    cin>>n;

    int x=pow(pow(2,n)+1,2);//将公示带入

    cout<<x;

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

结束啦~~~