实际上我只是贴我做的题而已
不仅如此，我还是一两道题就给一篇博客
骨牌问题(yzoj1366)
Description
有 2 行 N 列的长方形，可以用 N 个 1*2 的骨牌铺满，但可能有很多种不同的铺法。现在给出自然数n，请回答当长方形为 2 行 n 列时，有多少种不同的铺设方法。
第一行一个整数t表示测试数据组数。下面的t行，每行一个整数n。
Output
每组数据输出一行一个整数，表示方案总数，这个数可能很大，所以只需输出模10007后的结果。
| Sample Input |
Sample Output |
| 3 2 5 7 |
2 8 21 |
难得换行了，但是实际上答案是要求换行的
这一个比较的简单，可以看出来就是斐波那契数列
所以直接打表法
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| #include<bits/stdc++.h>
#define maxn 100003
#define Mod 10007
using namespace std;
int f[maxn];
int main(){
f[1]=1;f[2]=2;
for(int i=3;i<maxn;i++)f[i]=(f[i-1]+f[i-2])%Mod;
int n;
scanf("%d",&n);
while(n--){
int t;
cin>>t;
cout<<f[t]<<endl;
}
return 0;
}
|
爬楼梯(yzoj1367)
Description
何老师爬楼梯，他可以每步上 1 、2或3 级，输入楼梯的级数，求不同的走法数。例如：楼梯一共有3级，他可以每步都走一级，或者第一步走一级，第二步走两级，也可以第一步走两级，第二步走一级，还有就是第一步就上3级，所以一共4种方法。
Input
第一行：N、K。 第二行：K个整数h[i]，表示坏了的楼梯的级数(1<=h[i]<=N)。
Output
不同的走法数，这个数字可能很巨大，所以输出最后答案mod 1234567
我懒得给样例了，说实话我不喜欢抄题
Analysis
这个的话把坏掉的楼梯直接变成方案数0就可以了，注意边界要特殊处理。方程的话经过推理事
$$
f[n]=f[n-1]+f[n-2]+f[n-3]
$$
Code
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
| #include<bits/stdc++.h>
#define Mod 1234567
#define maxi 1007
using namespace std;
int f[maxi];
bool is_broken[maxi];
int main(){
memset(is_broken,0,sizeof(is_broken));
memset(f,0,sizeof(f));
int n,k;
f[1]=1;f[2]=2;f[3]=4;
scanf("%d%d",&n,&k);
for(int i=1;i<=k;i++){
int x;
scanf("%d",&x);
is_broken[x]=true;
}
if(is_broken[1]){
f[1]=0;f[2]-=1;f[3]-=2;
}
if(is_broken[2]){
f[2]=0;
if(is_broken[1]){
f[3]-=1;
}
else f[3]-=2;
}
if(is_broken[3]){
f[3]=0;
}
for(int i=4;i<=n;i++){
if(is_broken[i])f[i]=0;
else f[i]=(f[i-1]+f[i-2]+f[i-3])%Mod;
}
printf("%d",f[n]);
return 0;
}
|