1312：【例3.4】昆虫繁殖
【题目描述】
科学家在热带森林中发现了一种特殊的昆虫，这种昆虫的繁殖能力很强。每对成虫过x个月产y对卵，每对卵要过两个月长成成虫。假设每个成虫不死，第一个月只有一对成虫，且卵长成成虫后的第一个月不产卵(过x个月产卵)，问过z个月以后，共有成虫多少对？0≤x≤20,1≤y≤20,x≤z≤500。
【题目分析】
用数组a表示成虫的数量，b表示卵的数量，有
a[n]=a[n-1]+b[n-2]
b[n]=y*a[n-x]
【代码实现】
#include<bits/stdc++.h>
using namespace std;
long long a[55], b[55];
/* 1312：【例3.4】昆虫繁殖 */
int main() {
int x, y, z;
cin >> x >> y >> z;
//初始条件
for (int i = 0; i <= x; i++) {
a[i] = 1;
b[i] = 0;
}
//递推过程
for (int i = x + 1; i <= z + 1; i++) {
a[i] = b[i - 2] + a[i - 1];
b[i] = a[i - x] * y;
}
//输出结果
cout << a[z + 1];
return 0;
}
1313：【例3.5】位数问题
【题目描述】
在所有的N位数中，有多少个数中有偶数个数字3?由于结果可能很大，你只需要输出这个答案对12345取余的值。
【题目分析】
【代码实现】
#include<bits/stdc++.h>
using namespace std;
int a[1005], b[1005];
int main() {
int n;
cin >> n;
if (n == 1) {
cout << 9;
return 0;
}
a[1] = 8; //从高位到低位思考 如果从低位到高位思考会少数量
b[1] = 1;
for (int i = 2; i <= n; i++) {
a[i] = (a[i - 1] * 9 + b[i - 1]) % 12345;
b[i] = (b[i - 1] * 9 + a[i - 1]) % 12345;
}
cout << a[n];
return 0;
}
1314：【例3.6】过河卒(Noip2002)
【题目描述】
棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上的某一点有一个对方的马（如C点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点，如图3-1中的C点和P1，……，P8，卒不能通过对方马的控制点。棋盘用坐标表示，A点(0,0)、B点(n, m) (n,m为不超过20的整数),同样马的位置坐标是需要给出的，C≠A且C≠B。现在要求你计算出卒从A点能够到达B点的路径的条数。
【题目分析】
【代码实现】
#include<bits/stdc++.h>
using namespace std;
/*使用两个数组进行求解*/
int main() {
int a, b, x, y;
cin >> a >> b >> x >> y;
int map_data[22][22] = {};
long long data[22][22] = {};
//初始化map位置
map_data[x][y] = 1;
if (x + 1 <= a && y + 2 <= b) map_data[x + 1][y + 2] = 1;
if (x + 2 <= a && y + 1 <= b) map_data[x + 2][y + 1] = 1;
if (x - 1 >= 0 && y + 2 <= b) map_data[x - 1][y + 2] = 1;
if (y - 2 >= 0 && x + 1 <= a) map_data[x + 1][y - 2] = 1;
if (x - 1 >= 0 && y - 2 >= 0) map_data[x - 1][y - 2] = 1;
if (y - 1 >= 0 && x + 2 <= a) map_data[x + 2][y - 1] = 1;
if (x - 2 >= 0 && y + 1 <= b) map_data[x - 2][y + 1] = 1;
if (x - 2 >= 0 && y - 1 >= 0) map_data[x - 2][y - 1] = 1;
//初始化边界条件
data[0][0] = 1;
for (int i = 1; i <= a; i++) {
if (map_data[i][0] == 0)data[i][0] = data[i - 1][0];
}
for (int i = 1; i <= b; i++) {
if (map_data[0][i] == 0)data[0][i] = data[0][i - 1];
}
//逐层递推
for (int i = 1; i <= a; i++) {
for (int j = 1; j <= b; j++) {
if (map_data[i][j] != 1)data[i][j] = data[i - 1][j] + data[i][j - 1];
else data[i][j] = 0;
}
}
cout << data[a][b];
}
1188：菲波那契数列(2)
【题目描述】
菲波那契数列是指这样的数列: 数列的第一个和第二个数都为11，接下来每个数都等于前面22个数之和。给出一个正整数a，要求菲波那契数列中第a个数对1000取模的结果是多少。
【题目分析】
【代码实现】
#include <bits/stdc++.h>
using namespace std;
int a[1000005];
int main() {
//input data
a[1] = 1;
a[2] = 1;
for (int i = 3; i <= 1000000; i++) {
a[i] = (a[i - 1] + a[i - 2]) % 1000;
}
int n;
cin >> n;
while (n--) {
int m;
cin >> m;
cout << a[m] << endl;
}
return 0;
}
1189：Pell数列
【题目描述】
Pell数列a1,a2,a3,…的定义是这样的，a1=1,a2=2,…,an=2an−1+an−2(n>2)。
给出一个正整数k，要求Pell数列的第k项模上32767是多少。
【题目分析】
【代码实现】
#include <bits/stdc++.h>
using namespace std;
int a[1000005];
int main() {
//input data
a[1] = 1;
a[2] = 2;
for (int i = 3; i <= 1000000; i++) {
a[i] = (2 * a[i - 1] + a[i - 2]) % 32767;
}
int n;
cin >> n;
while (n--) {
int m;
cin >> m;
cout << a[m] << endl;
}
return 0;
}
1190：上台阶
【题目描述】
楼梯有n(71>n>0)阶台阶,上楼时可以一步上1阶,也可以一步上2阶,也可以一步上3阶，编程计算共有多少种不同的走法。
【题目分析】
【代码实现】
#include <bits/stdc++.h>
using namespace std;
long long a[72];
int main() {
//input data
a[0] = 1;
a[1] = 1;
a[2] = 2;
a[3] = a[2] + a[1] + a[0];
for (int i = 3; i <= 72; i++) {
a[i] = a[i - 1] + a[i - 2] + a[i - 3];
}
int n;
while (cin >> n, n != 0) {
cout << a[n] << endl;
}
return 0;
}
1191：流感传染
【题目描述】
有一批易感人群住在网格状的宿舍区内，宿舍区为n*n的矩阵，每个格点为一个房间，房间里可能住人，也可能空着。在第一天，有些房间里的人得了流感，以后每天，得流感的人会使其邻居传染上流感，（已经得病的不变），空房间不会传染。请输出第m天得流感的人数。
【题目分析】
【代码实现】
#include <bits/stdc++.h>
using namespace std;
char a[105][105];
int vis[105][105];
int sum = 0;
int _next[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int main() {
//input data
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
char c;
scanf("%c", &c);
if (c == ' ' || c == '\n') {
j--;
continue;
}
a[i][j] = c;
if (a[i][j] == '@') {
vis[i][j] = 1;
}
}
}
int m;
cin >> m;
for (int i = 2; i <= m; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= n; k++) {
if (a[j][k] == '@' && vis[j][k] == i - 1) {
for (int l = 0; l < 4; l++) {
int nx = j + _next[l][0];
int ny = k + _next[l][1];
if (nx < 1 || ny < 1 || nx > n || ny > n) continue;
if (a[nx][ny] == '#' || a[nx][ny] == '@') continue;
a[nx][ny] = '@';
vis[nx][ny] = i;
}
}
}
}
}
// for (int i = 1; i <= n; i++) {
// for (int j = 1; j <= n; j++) {
// cout << a[i][j];
// }
// cout << endl;
// }
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (a[i][j] == '@') sum++;
}
}
cout << sum << endl;
return 0;
}
1192：放苹果
【题目描述】
把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。
【题目分析】
【代码实现】
#include <bits/stdc++.h>
using namespace std;
int a[15][15];
int main() {
//input data
int t, m, n;
for (int i = 0; i <= 10; i++) {
a[1][i] = a[0][i] = 1;
a[i][1] = 1;
a[i][0] = 0;
}
for (int i = 2; i <= 10; i++) {
for (int j = 2; j <= 10; j++) {
if (i < j) a[i][j] = a[i][i];
if (i >= j) a[i][j] = a[i][j - 1] + a[i - j][j];
}
}
cin >> t;
while (t--) {
cin >> m >> n;
cout << a[m][n] << endl;
}
return 0;
}
1193：吃糖果
【题目描述】
名名的妈妈从外地出差回来，带了一盒好吃又精美的巧克力给名名(盒内共有 N 块巧克力，0<N<20)。妈妈告诉名名每天可以吃一块或者两块巧克力。假设名名每天都吃巧克力，问名名共有多少种不同的吃完巧克力的方案。例如：如果N=1，则名名第1天就吃掉它，共有1种方案；如果N=2，则名名可以第1天吃1块，第2天吃1块，也可以第1天吃2块，共有2种方案；如果N=3，则名名第1天可以吃1块，剩2块，也可以第1天吃2块剩1块，所以名名共有2+1=3种方案；如果N=4，则名名可以第1天吃1块，剩3块，也可以第1天吃2块，剩2块，共有3+2=5种方案。现在给定N，请你写程序求出名名吃巧克力的方案数目。
【题目分析】
【代码实现】
#include <bits/stdc++.h>
using namespace std;
int a[20];
int main() {
//input data
a[1] = 1;
a[2] = 2;
a[3] = 3;
int n;
cin >> n;
for (int i = 3; i <= n; i++) {
a[i] = a[i - 1] + a[i - 2];
}
cout << a[n];
return 0;
}
1194：移动路线
【题目描述】
X桌子上有一个m行n列的方格矩阵，将每个方格用坐标表示，行坐标从下到上依次递增，列坐标从左至右依次递增，左下角方格的坐标为(1,1)，则右上角方格的坐标为(m,n)。
小明是个调皮的孩子，一天他捉来一只蚂蚁，不小心把蚂蚁的右脚弄伤了，于是蚂蚁只能向上或向右移动。小明把这只蚂蚁放在左下角的方格中，蚂蚁从
左下角的方格中移动到右上角的方格中，每步移动一个方格。蚂蚁始终在方格矩阵内移动，请计算出不同的移动路线的数目。
对于1行1列的方格矩阵，蚂蚁原地移动，移动路线数为1；对于1行2列（或2行1列）的方格矩阵，蚂蚁只需一次向右（或向上）移动，移动路线数也为1……对于一个2行3列的方格矩阵，如下图所示：
蚂蚁共有3种移动路线：
路线1：(1,1) → (1,2) → (1,3) → (2,3)
路线2：(1,1) → (1,2) → (2,2) → (2,3)
路线3：(1,1) → (2,1) → (2,2) → (2,3)
【题目分析】
【代码实现】
#include <bits/stdc++.h>
using namespace std;
long long a[20][20];
int main() {
//input data
for (int i = 1; i <= 19; i++) {
a[i][1] = 1;
a[1][i] = 1;
}
for (int i = 2; i <= 19; i++) {
for (int j = 2; j <= 19; j++) {
a[i][j] = a[i - 1][j] + a[i][j - 1];
}
}
int m, n;
cin >> m >> n;
cout << a[m][n];
return 0;
}
1195：判断整除
【题目描述】
一个给定的正整数序列，在每个数之前都插入++号或−−号后计算它们的和。比如序列：1、2、41、2、4共有88种可能的序列：
(+1) + (+2) + (+4) = 7 (+1) + (+2) + (-4) = -1 (+1) + (-2) + (+4) = 3 (+1) + (-2) + (-4) = -5 (-1) + (+2) + (+4) = 5 (-1) + (+2) + (-4) = -3 (-1) + (-2) + (+4) = 1 (-1) + (-2) + (-4) = -7
所有结果中至少有一个可被整数k整除，我们则称此正整数序列可被k整除。例如上述序列可以被3、5、73、5、7整除，而不能被2、4、6、8……2、4、6、8……整除。注意：0、−3、−6、−9……0、−3、−6、−9……都可以认为是3的倍数。
【题目分析】
【代码实现】
#include <bits/stdc++.h>
using namespace std;
int a[10005];
bool f[10005][105];
int main() {
//input data
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
a[i] = a[i] % k;
}
f[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < k; j++) {
if (f[i - 1][j] == 1) {
f[i][(j + a[i]) % k] = 1;
f[i][(j - a[i] + k) % k] = 1;
}
}
}
if (f[n][0] == 1) cout << "YES";
else cout << "NO";
return 0;
}
1196：踩方格
【题目描述】
有一个方格矩阵，矩阵边界在无穷远处。我们做如下假设：
a、每走一步时，只能从当前方格移动一格，走到某个相邻的方格上；
b、走过的格子立即塌陷无法再走第二次；
c、只能向北、东、西三个方向走；
请问：如果允许在方格矩阵上走n步，共有多少种不同的方案。2种走法只要有一步不一样，即被认为是不同的方案。
【题目分析】
【代码实现】
#include <bits/stdc++.h>
using namespace std;
int a[25];
int main() {
//input data
a[1] = 3;
a[2] = 7;
int n;
cin >> n;
for (int i = 3; i <= n; i++) {
a[i] = a[i - 1] * 2 + a[i - 2];
}
cout << a[n];
return 0;
}
1197：山区建小学
【题目描述】
政府在某山区修建了一条道路，恰好穿越总共m个村庄的每个村庄一次，没有回路或交叉，任意两个村庄只能通过这条路来往。已知任意两个相邻的村庄之间的距离为di(为正整数)，其中，0<i<m。为了提高山区的文化素质，政府又决定从m个村中选择n个村建小学(设0<n≤m<500)。请根据给定的m、n以及所有相邻村庄的距离，选择在哪些村庄建小学，才使得所有村到最近小学的距离总和最小，计算最小值。
【题目分析】
【代码实现】
#include<bits/stdc++.h>
using namespace std;
//int a[505];
int a[505][505];
int b[505][505];
int f[505][505];
int main() {
int m, n;
cin >> m >> n;
for (int i = 1; i < m; i++) {
cin >> a[i][i + 1];
a[i + 1][i] = a[i][i + 1];
}
//计算村庄到村庄之间的距离
for (int i = 1; i <= m; i++)
for (int j = i; j <= m; j++) {
if (i == j || a[i][j] != 0) continue;
a[j][i] = a[i][j] = a[i][j - 1] + a[j - 1][j];
}
//在各村庄之间修学校的距离
for (int i = 1; i <= m; i++) {
for (int j = i + 1; j <= m; j++) {
int mid = (i + j) / 2;
for (int k = i; k <= j; k++) {
b[i][j] += a[k][mid];
}
b[j][i] = b[i][j];
}
}
//边界条件
for (int i = 1; i <= m; i++) {
f[i][1] = b[1][i];
}
//动态规划 计算过程
for (int i = 1; i <= m; i++) {
for (int j = 2; j <= n; j++) {
f[i][j] = 1e8;
for (int k = 1; k <= i; k++) {
f[i][j] = min(f[i][j], f[k][j - 1] + b[k + 1][i]);
}
}
}
cout<<f[m][n];
// for (int i = 1; i <= m; i++) {
// for (int j = 1; j <= m; j++) {
// cout << setw(5) << f[i][j];
// }
// cout << endl;
// }
return 0;
}