OpenJudge NOI 2.2 9273:PKU2506Tiling | 2.3 9273:PKU2506Tiling
【题目链接】
OpenJudge NOI 2.2 9273:PKU2506Tiling
OpenJudge NOI 2.3 9273:PKU2506Tiling
【题目考点】
1. 递推
2. 高精度
【解题思路】
解法1：递推
- 递推状态： a i a_i ai：i列道路铺砖的方案数
- 初始状态：0列道路铺砖有1种方案，就是不铺。1列道路铺砖只有1种方案： a 0 = 1 , a 1 = 1 a_0=1, a_1=1 a0=1,a1=1
- 递推关系：
- 如果第i列道路只铺一个宽为1高为2的竖向的砖，那么i列道路的铺砖方案数等于前i-1列道路的铺砖方案数 a i − 1 a_{i-1} ai−1。
- 如果第i列和第i-1列道路铺了两个宽为2高为1的横向的砖，那么i列道路的铺砖方案数等于前i-2列道路的铺砖方案数 a i − 2 a_{i-2} ai−2。
- 如果第i列和第i-1列道路铺了一个宽为2高为2的横向的砖，那么i列道路的铺砖方案数等于前i-2列道路的铺砖方案数 a i − 2 a_{i-2} ai−2。
- 以上所有情况加和，递推关系为： a i = a i − 1 + 2 ∗ a i − 2 a_i=a_{i-1}+2*a_{i-2} ai=ai−1+2∗ai−2
解法2：递归
- 递归问题：求i列道路铺砖的方案数
- 递归关系：i列道路铺砖的方案数，是i-1列道路铺砖方案数加上2倍的i-2列道路铺砖的方案数（参考上面递推关系的分析方法）
- 递归出口：0列道路铺砖有1种方案，就是不铺。1列道路铺砖只有1种方案
【注意】：
因为
a
i
=
a
i
−
1
+
2
a
i
−
2
>
2
a
i
−
2
a_i=a_{i-1}+2a_{i-2}>2a_{i-2}
ai=ai−1+2ai−2>2ai−2，
因此：
a
201
>
2
a
199
>
2
2
a
197
>
.
.
.
>
2
100
a
1
=
2
100
a_{201}>2a_{199}>2^2a_{197}>...>2^{100}a_1=2^{100}
a201>2a199>22a197>...>2100a1=2100，是一个高精度数字。
n最大为250，因此该题结果最大值
a
250
a_{250}
a250也一定是一个高精度数字。
因此该题必须使用高精度计算。
估算结果的位数：
a
i
=
a
i
−
1
+
2
a
i
−
2
<
3
a
i
−
1
<
3
2
a
i
−
2
<
.
.
.
<
3
i
−
1
a
1
=
3
i
−
1
a_i=a_{i-1}+2a_{i-2}<3a_{i-1}<3^2a_{i-2}<...<3^{i-1}a_1=3^{i-1}
ai=ai−1+2ai−2<3ai−1<32ai−2<...<3i−1a1=3i−1
所以
a
250
<
3
249
<
3
250
a_{250}<3^{249}<3^{250}
a250<3249<3250
求
3
250
3^{250}
3250的位数
⌊
l
o
g
10
3
250
⌋
+
1
<
250
∗
l
o
g
10
3
+
1
<
250
∗
l
o
g
10
10
+
1
=
251
\lfloor log_{10}3^{250}\rfloor +1<250*log_{10}3+1<250*log_{10}10+1=251
⌊log103250⌋+1<250∗log103+1<250∗log1010+1=251
因此可以把高精度数字的位数设为255。
【题解代码】
解法1：递推
- 写法1：使用全局变量和函数
#include <bits/stdc++.h>
using namespace std;
#define N 255 //经过估算结果位数不超过251
void showNum(int a[])
{
for(int i = a[0]; i >= 1; --i)
cout << a[i];
cout << endl;
}
void setLen(int a[], int i)
{
while(a[i] == 0 && i > 1)
i--;
a[0] = i;
}
void Add(int a[], int b[]) // a += b
{
int c = 0, i;
for(i = 1; i <= a[0] || i <= b[0]; ++i)
{
a[i] += b[i]+c;
c = a[i]/10;
a[i] %= 10;
}
a[i] = c;
setLen(a, i);
}
int main()
{
int n, a[255][N] = {};//a[i]：i列道路铺砖的方案数
a[0][0] = 1, a[0][1] = 1;//a[0] = 1
a[1][0] = 1, a[1][1] = 1;//a[1] = 1
for(int i = 2; i <= 250; ++i)
{//a[i] = a[i-1]+2*a[i-2]
Add(a[i], a[i-1]);
Add(a[i], a[i-2]);
Add(a[i], a[i-2]);
}
while(cin >> n)
showNum(a[n]);
return 0;
}
- 写法2：使用类和重载运算符
#include<bits/stdc++.h>
using namespace std;
#define N 255
class HPN
{
private:
int a[N];
public:
HPN()
{
memset(a, 0, sizeof(a));
}
HPN(int n)//前提：n小于10
{
memset(a, 0, sizeof(a));
a[0] = 1;
a[1] = n;
}
int& operator [] (int i)
{
return a[i];
}
HPN operator + (HPN b)
{
HPN r;
int c = 0, i;
for(i = 1; i <= a[0] || i <= b[0]; ++i)
{
r[i] = a[i] + b[i] + c;
c = r[i] / 10;
r[i] %= 10;
}
r[i] = c;
while(r[i] == 0)
i--;
r[0] = i;
return r;
}
void show()
{
for(int i = a[0]; i >= 1; --i)
cout << a[i];
cout << endl;
}
};
int main()
{
HPN a[255];//a[i]：i列道路铺砖的方案数
a[0] = HPN(1);
a[1] = HPN(1);
for(int i = 2; i <= 250; ++i)
a[i] = a[i-1]+a[i-2]+a[i-2];//由于只重载了+运算符，因此用加法来写递推关系
int n;
while(cin >> n)
a[n].show();
return 0;
}
解法2：递归
使用类和重载运算符，记忆化递归
#include<bits/stdc++.h>
using namespace std;
#define N 255
class HPN
{
private:
int a[N];
public:
HPN()
{
memset(a, 0, sizeof(a));
}
HPN(int n)//前提：n小于10
{
memset(a, 0, sizeof(a));
a[0] = 1;
a[1] = n;
}
int& operator [] (int i)
{
return a[i];
}
HPN operator + (HPN b)
{
HPN r;
int c = 0, i;
for(i = 1; i <= a[0] || i <= b[0]; ++i)
{
r[i] = a[i] + b[i] + c;
c = r[i] / 10;
r[i] %= 10;
}
r[i] = c;
while(r[i] == 0)
i--;
r[0] = i;
return r;
}
void show()
{
for(int i = a[0]; i >= 1; --i)
cout << a[i];
cout << endl;
}
};
HPN a[255];//a[i]：i列道路铺砖的方案数
HPN solve(int i)//求i列道路铺砖的方案数
{
if(i == 0 || i == 1)
return HPN(1);
if(a[i][0])//通过看a[i]数字是否设置位数，来判断a[i]是否已经求出
return a[i];
else
return a[i] = solve(i-1) + solve(i-2) + solve(i-2);
}
int main()
{
int n;
while(cin >> n)
solve(n).show();
return 0;
}