上海计算机学会2024年5月月赛C++乙组T1蜜蜂与幼虫
发布时间
阅读量：
阅读量
蜜蜂与幼虫
内存限制: 256 Mb时间限制: 1000 ms
题目描述
蜂巢由一些正六边形的格子组成，这些格子分上下两排，一共有 n 个格子。如果 n 是偶数，则每一排分别有 n/2 个格子，若 n 是奇数，则下排比上排多一个。
一只成年的蜜蜂，会占据两个相邻的格子，而一只蜜蜂的幼虫只能占据一个格子。
若蜂巢所有的格子都被蜜蜂或幼虫占据了，那么会有多少种不同的方案呢？两个方案若在任何一个格子上的布置有区别，就被看作是不同的方案。
答案可能很大，输出模 1,000,000,007 的余数。
输入格式
- 单个整数：表示 n
输出格式
- 单个整数：表示答案。
数据范围
- 30% 的数据，1≤n≤10
- 60% 的数据，1≤n≤1,000
- 100% 的数据，1≤n≤1,000,000
样例数据
输入:
4
输出:
8
解析：
对于第i个格子，a[i]
只有一个幼虫， a[i-1];
一只成虫占i和i-1格子，a[i-2];
一只成虫占i和i-2格子，一只幼虫占i-1格子，a[i-3];
一只成虫占i和i-2格子，一只成虫占i-1格子和i-3格子，a[i-4];
所以a[i]=a[i-1]+a[i-2]+a[i-3]+a[i-4];
详见代码：
#include <bits/stdc++.h>
using namespace std;
int n;
int a[1000005];
int mod=1000000007;
int main() {
cin>>n;
a[0]=1;
a[1]=1;
a[2]=2;
a[3]=4;
for(int i=4;i<=n;i++){
for(int j=1;j<=4;j++){
a[i]+=a[i-j];
a[i]%=mod;
}
}
cout<<a[n];
return 0;
}
AI写代码cpp
全部评论 (0)
还没有任何评论哟~