做电子外贸网站,深圳建筑企业排名,wordpress首页没有显示文章图片,南和县建设局黄页网站1191#xff1a;流感传染 【题目描述】 有一批易感人群住在网格状的宿舍区内#xff0c;宿舍区为n*n的矩阵#xff0c;每个格点为一个房间#xff0c;房间里可能住人#xff0c;也可能空着。在第一天#xff0c;有些房间里的人得了流感#xff0c;以后每天#xff0c;得…1191流感传染 【题目描述】 有一批易感人群住在网格状的宿舍区内宿舍区为n*n的矩阵每个格点为一个房间房间里可能住人也可能空着。在第一天有些房间里的人得了流感以后每天得流感的人会使其邻居传染上流感已经得病的不变空房间不会传染。请输出第m天得流感的人数。 【输入】 第一行一个数字nn不超过100表示有n*n的宿舍房间。 接下来的n行每行n个字符’.’表示第一天该房间住着健康的人’#’表示该房间空着’’表示第一天该房间住着得流感的人。 接下来的一行是一个整数mm不超过100。 【输出】 输出第m天得流感的人数。 【输入样例】 5
....#
.#..
.#..
#....
.....
4 【输出样例】 16 #includeiostream
using namespace std;
const int N 1e2 10;
char a[N][N];//房间数组
int dx[] { 0,0,1,-1 };
int dy[] { 1,-1,0,0 };
bool vis[N][N];//标记当天生病的
int main()
{int n; cin n;//存储房间for (int i 1; i n; i){for (int j 1; j n; j){cin a[i][j];}}//记录生病的人数int cnt0;int m;cin m;//开始感染for (int day 2; day m; day){memset(vis,0,sizeof vis);for (int i 1; i n; i){for (int j 1; j n; j){if (a[i][j] !vis[i][j]) {//遍历所有可能感染的方向for (int k 0; k 4; k){int bx i dx[k], by j dy[k];//超出房间的边界if (i1 || in || j1 || jn)continue;if (a[bx][by] .) {a[bx][by] ;//标记当天被感染的vis[bx][by] 1;}}}}}}for (int i 1; i n; i){for (int j 1; j n; j){if (a[i][j] )cnt;}}cout cnt;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点的路径的条数 【输入】 给出n、m和C点的坐标。 【输出】 从A点能够到达B点的路径的条数。 【输入样例】 8 6 0 4 【输出样例】 1617
#includeiostream
using namespace std;
#define int long long
const int N 1e2 10;
int a[N][N];
//马可走的八个方向
int dx[] {1,1,-1,-1,2,2,-2,-2};
int dy[] {2,-2,2,-2,1,-1,1,-1};
bool vis[N][N];//马运动的轨迹
/*
//边界
a[i][j]1
//递推关系式
a[i][j]a[i-1][j]a[i][j-1]
*/
signed main()
{int tx, ty;//B点坐标int cx, cy;//C点坐标cin tx ty cx cy;vis[cx][cy] 1;//标记马//马运动的轨迹for (int i 0; i 8; i){int cxx cx dx[i], cyy cy dy[i];//如果新生成的坐标越界则跳过继续生成下一个坐标if (cxx0 || cxxtx || cyy0 || cyyty)continue;//0也是边界vis[cxx][cyy] 1;}//边界a[0][0] 1;//处理第一行for (int j 1; j ty; j){if (!vis[0][j])a[0][j] a[0][j - 1];elsea[0][j] 0;}//处理第一列for (int i 1; i tx; i){if (!vis[i][0])a[i][0] a[i - 1][0];elsea[i][0] 0;}//递推for (int i 1; i tx; i){for (int j 1; j ty; j){if (!vis[i][j])a[i][j] a[i - 1][j] a[i][j - 1];elsea[i][j] 0;}}cout a[tx][ty] endl;return 0;
} 1194移动路线 【题目描述】 X桌子上有一个m行n列的方格矩阵将每个方格用坐标表示行坐标从下到上依次递增列坐标从左至右依次递增左下角方格的坐标为(1,1)则右上角方格的坐标为(m,n)。 小明是个调皮的孩子一天他捉来一只蚂蚁不小心把蚂蚁的右脚弄伤了于是蚂蚁只能向上或向右移动。小明把这只蚂蚁放在左下角的方格中蚂蚁从 左下角的方格中移动到右上角的方格中每步移动一个方格。蚂蚁始终在方格矩阵内移动请计算出不同的移动路线的数目。 对于1行1列的方格矩阵蚂蚁原地移动移动路线数为1对于1行2列或2行1列的方格矩阵蚂蚁只需一次向右或向上移动移动路线数也为1……对于一个2行3列的方格矩阵如下图所示 (2,1)(2,2)(2,3)(1,1)(1,2)(1,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) 【输入】 输入只有一行包括两个整数m和n0 mn ≤ 20代表方格矩阵的行数和列数m、n之间用空格隔开。 【输出】 输出只有一行为不同的移动路线的数目。 【输入样例】 2 3 【输出样例】 3 #includeiostream
using namespace std;
#define int long long
const int N 1e2 10;
int a[N][N];
signed main()
{int n, m;cin n m;//处理边界a[1][1] 1;//处理第一行for (int j 2; j m; j)a[1][j] a[1][j-1];//处理其余路线for (int i 2; i n; i)a[i][1] a[i - 1][1];for (int i 2; i n; i)for (int j 2; j m; j)a[i][j] a[i][j - 1] a[i - 1][j];cout a[n][m];return 0;
} 1196踩方格 【题目描述】 有一个方格矩阵矩阵边界在无穷远处。我们做如下假设 a、每走一步时只能从当前方格移动一格走到某个相邻的方格上 b、走过的格子立即塌陷无法再走第二次 c、只能向北、东、西三个方向走 请问如果允许在方格矩阵上走n步共有多少种不同的方案。2种走法只要有一步不一样即被认为是不同的方案。 【输入】 允许在方格上行走的步数n(n≤20)。 【输出】 计算出的方案数量。 【输入样例】 2 【输出样例】 7 #includeiostream
using namespace std;
#define int long long
const int N 1e2 10;
int a[N][N];
int l[N], r[N], u[N];//向左 右 上 的方案总数
signed main()
{int n; cin n;l[1] r[1] u[1] 1;/*若i-1步向左那么第i部只能向上或者向左若i-1步向右那么第i部只能向上或者向右若i-1步向上那么第i部能向上或者向左或者向右*/int ans 0;//记录方案数for (int i 2; i n; i){l[i] u[i - 1] l[i - 1];r[i] u[i - 1] r[i - 1];u[i] u[i - 1] l[i - 1] r[i - 1];ans l[i] r[i] u[i];}cout ans;return 0;
}
1313【例3.5】位数问题 【题目描述】 在所有的N位数中有多少个数中有偶数个数字33?由于结果可能很大你只需要输出这个答案对1234512345取余的值。 【输入】 读入一个数N(N≤1000)(≤1000)。 【输出】 输出有多少个数中有偶数个数字33。 【输入样例】 2 【输出样例】 73 #includeiostream
using namespace std;
#define int long long
/*
1位数 2位数 3位数 4位数even[1] odd[1] even[2] odd[2] even[3] odd[3] even[4] odd[4]
0 3 9*even[1]odd[1] 9*odd[1]even[1] 9*even[2]odd[2] 9*odd[2]even[2] 8*even[3]odd[3] 8*odd[3]even[3]
1
2
4
5
6
7
8
9
*/
const int N 1e3 10, mod 12345;
int even[N], odd[N];
signed main() {even[1] 9; odd[1] 1;int n; cin n;int t 9;for (int i 2; i n; i) {if (i n) t 8;//当走到最高位时最高位不能为0方案少一种变为8odd[i] (t * odd[i - 1] % mod even[i - 1] % mod) % mod;even[i] (t * even[i - 1] % mod odd[i - 1] % mod) % mod;}cout even[n] endl;return 0;
}
1201菲波那契数列 【题目描述】 菲波那契数列是指这样的数列: 数列的第一个和第二个数都为1接下来每个数都等于前面2个数之和。 给出一个正整数a要求菲波那契数列中第a个数是多少。 【输入】 第1行是测试数据的组数n后面跟着n行输入。每组测试数据占1行包括一个正整数a(1a20)。 【输出】 输出有n行每行输出对应一个输入。输出应是一个正整数为菲波那契数列中第a个数的大小。 【输入样例】 4
5
2
19
1 【输出样例】 5
1
4181
1 #includeiostream
using namespace std;
const int N1e210;
int fbnq(int x)
{if (x 2)return 1;return fbnq(x - 1) fbnq(x - 2);
}
int main()
{int n; cin n;int x;while (n--){cin x;cout fbnq(x) endl;;}return 0;
}
1202Pell数列 【题目描述】 Pell数列a1,a2,a3,...1,2,3,...的定义是这样的a11,a22,...,an2an−1an−2(n2)11,22,...,2−1−2(2)。 给出一个正整数 k要求Pell数列的第 k 项模上 3276732767 是多少。 【输入】 第1行是测试数据的组数 n后面跟着 n 行输入。每组测试数据占 11 行包括一个正整数k(1≤k1000000)(1≤1000000)。 【输出】 n 行每行输出对应一个输入。输出应是一个非负整数。 【输入样例】 2
1
8 【输出样例】 1
408 #includeiostream
using namespace std;
const int N1e610;
#define int long long
int m 32767;
int a[N];
int pell(int x)
{//剪枝求过的项不需要重复求if (a[x])return a[x];if (x 2)return a[x]x;return a[x](2 * pell(x - 1) % m pell(x - 2) % m) % m;
}
signed main()
{int n; cin n;int x;while (n--){cin x;cout pell(x) endl;;}return 0;
}
1204爬楼梯 【题目描述】 树老师爬楼梯他可以每次走1级或者2级输入楼梯的级数求不同的走法数。 例如楼梯一共有3级他可以每次都走一级或者第一次走一级第二次走两级也可以第一次走两级第二次走一级一共3种方法。 【输入】 输入包含若干行每行包含一个正整数N代表楼梯级数1≤N≤30。 【输出】 不同的走法数每一行输入对应一行输出。 【输入样例】 5
8
10 【输出样例】 8
34
89 #includeiostream
using namespace std;
const int N1e210;
#define int long long
int a[N];
int stairs(int x)
{/*s(8) a[8]s(7)s(6)34s(7) a[7]s(6)s(5)21s(6) a[6]s(5)s(4)13s(5) a[5]s(4)s(3)8s(4) a[4]s(3)s(2)5 s(3) a[3]s(2)s(1)3 *///剪枝if (a[x])return a[x];if (x 2)return a[x] x;return a[x]stairs(x - 1) stairs(x - 2);
}
signed main()
{int x;while (cin x){cout stairs(x) endl;}return 0;
}
