上海国外网站建设,建设一个视频网站需要什么,做微秀的网站,传奇网站免费空间作者#xff1a;指针不指南吗 专栏#xff1a;蓝桥杯倒计时冲刺 #x1f43e;倒计时4天#xff0c;冲冲冲#xff01;#xff01;#xff01;#x1f43e; 文章目录1.整除序列2.走方格3.前缀和4.差分矩阵5.翻硬币1.整除序列 题目 链接#xff1a; 2065. 整除序列 - Ac… 作者指针不指南吗 专栏蓝桥杯倒计时冲刺 倒计时4天冲冲冲 文章目录1.整除序列2.走方格3.前缀和4.差分矩阵5.翻硬币1.整除序列 题目 链接 2065. 整除序列 - AcWing题库 有一个序列序列的第一个数是 n后面的每个数是前一个数整除 2请输出这个序列中值为正数的项。 输入格式 输入一行包含一个整数 n。 输出格式 输出一行包含多个整数相邻的整数之间用一个空格分隔表示答案。 数据范围 1≤n≤1018^{18}18 输入样例 20输出样例 20 10 5 2 1第一次 AC 0% #includebits/stdc.h
using namespace std;typedef long long ll;int main()
{ll n;cinn;while(n){coutn/2 ;n/2;}return 0;
}第二次 #includebits/stdc.h
using namespace std;typedef long long ll;int main()
{ll n;cinn;coutn ; //原数需要输出while(n1) //1/20不能要而且通过样例可以看出来每一个数组最后都是 1{coutn/2 ;n/2;}return 0;
}反思 特殊数值特判考试的时候没有检测只能自己写几个样例现在开始自己造样例确定无误之后在 提交
2.走方格 题目 链接 2067. 走方格 - AcWing题库 在平面上有一些二维的点阵。 这些点的编号就像二维数组的编号一样从上到下依次为第 1 至第 n 行从左到右依次为第 1 至第 m 列每一个点可以用行号和列号来表示。 现在有个人站在第 1 行第 1 列要走到第 n 行第 m 列。 只能向右或者向下走。 注意如果行号和列数都是偶数不能走入这一格中。 问有多少种方案。 输入格式 输入一行包含两个整数 n,m。 输出格式 输出一个整数表示答案。 数据范围 1≤n,m≤30 输入样例1 3 4输出样例1 2输入样例2 6 6输出样例2 0第一次 AC 8/10 #includebits/stdc.h
using namespace std;typedef pairint,int PII;const int N40;int ans;int n,m;
int g[N][N];
bool st[N][N];void dfs(int x,int y)
{if(xnym){ans;return;}//两种方案向右向下if(x%20y%20||(xn||ym)) //注意处理 边界条件我都说累了return;if(!st[x][y]){st[x][y]1;dfs(x1,y);dfs(x,y1);st[x][y]0;}
}int main()
{cinnm;dfs(1,1);coutans;return 0;
}第二次 AC 9/10 #includebits/stdc.h
using namespace std;typedef pairint,int PII;const int N40;int ans;int n,m;
int g[N][N];
bool st[N][N];void dfs(int x,int y)
{if(x%20y%20||(xn||ym)) //把这个提在前面return;if(xnym){ans;return;}//两种方案向右向下if(!st[x][y]){st[x][y]1;dfs(x1,y);dfs(x,y1);st[x][y]0;}
}int main()
{cinnm;dfs(1,1);coutans;return 0;
}题解 #include bits/stdc.h
using namespace std;int n, m;
int f[31][31]; // 记忆化数组int dfs(int x, int y) // 搜索点 (x, y)并返回从点 (x, y) 开始能到点 (n, m) 的路径数量
{if (x 1 || y 1){if (f[x][y]) return f[x][y]; // 如果该点已经被搜索过那么不再处理// 否则说明没搜索过需要搜索一遍if (x n) f[x][y] dfs(x 1, y);if (y m) f[x][y] dfs(x, y 1);}return f[x][y]; // 最后返回 f[x][y] 即可。如果 x, y 都是偶数那么 f[x][y] 就没被处理过必然为 0可以不特判。
}int main()
{scanf(%d%d, n, m);f[n][m] n 1 || m 1; // 这里要特判下 n, m 是否都为偶数printf(%d\n, dfs(1, 1));return 0;
}反思 暴搜没有把最后一个数据过了TLE我最爱的暴搜 TvT 看了这个题解虽然没有学习过记忆化搜索但他看起来好酷 get 新技能
3.前缀和 题目 链接 795. 前缀和 - AcWing题库 输入一个长度为 n 的整数序列。 接下来输入 m 个操作每个操作包含三个整数 l,r,c 表示将序列中 [ l , r ] 之间的每个数加上 c。 请你输出进行完所有操作后的序列。 输入格式 第一行包含两个整数 n 和 m。 第二行包含 n 个整数表示整数序列。 接下来 m 行每行包含三个整数 lrc表示一个操作。 输出格式 共一行包含 n 个整数表示最终序列。 数据范围 1≤n,m≤100000, 1≤l≤r≤n, −1000≤c≤1000, −1000≤整数序列中元素的值≤1000 第一次 AC 100% #includebits/stdc.h
using namespace std;const int N100010;int n,m;
int a[N],b[N];void insert(int l,int r,int c)
{b[l]c;b[r1]-c;
}int main()
{cinnm;for(int i1;in;i){cina[i];insert(i,i,a[i]); //这里注意是 a[i]}while(m--){int x,y,c;cinxyc;insert(x,y,c);}for(int i1;in;i){a[i]a[i-1]b[i];couta[i] ;}return 0;
}4.差分矩阵 题目 链接 798. 差分矩阵 - AcWing题库 输入一个 n 行 m 列的整数矩阵再输入 q 个操作每个操作包含五个整数 x1,y1,x2,y2,c其中 (x1,y1) 和 (x2,y2)表示一个子矩阵的左上角坐标和右下角坐标。 每个操作都要将选中的子矩阵中的每个元素的值加上 c。 请你将进行完所有操作后的矩阵输出。 输入格式 第一行包含整数 n,m,q 。 接下来 n 行每行包含 m 个整数表示整数矩阵。 接下来 q 行每行包含 5 个整数 x1,y1,x2,y2,c表示一个操作。 输出格式 共 n 行每行 m 个整数表示所有操作进行完毕后的最终矩阵。 数据范围 1≤n,m≤1000, 1≤q≤100000, 1≤x1≤x2≤n, 1≤y1≤y2≤m, −1000≤c≤1000, −1000≤矩阵内元素的值≤1000−1000≤矩阵内元素的值≤1000 输入样例 3 4 3
1 2 2 1
3 2 2 1
1 1 1 1
1 1 2 2 1
1 3 2 3 2
3 1 3 4 1输出样例 2 3 4 1
4 3 4 1
2 2 2 2第一次 AC 100% #includebits/stdc.h
using namespace std;const int N1010;int n,m,q;
int a[N][N],b[N][N];void insert(int x1,int y1,int x2,int y2,int c)
{b[x1][y1]c;b[x1][y21]-c;b[x21][y1]-c;b[x21][y21]c;
}int main()
{cinnmq;for(int i1;in;i)for(int j1;jm;j){cina[i][j];insert(i,j,i,j,a[i][j]); //利用函数构造差分数组}while(q--){int x1,y1,x2,y2,c;cinx1y1x2y2c;insert(x1,y1,x2,y2,c);}for(int i1;in;i){for(int j1;jm;j){b[i][j]b[i-1][j]b[i][j-1]-b[i-1][j-1]; //求前缀和coutb[i][j] ;}puts( ); //输出格式注意}return 0;
}反思 差分和前缀和利用图形联想记公式 公式中前缀和 -1 / 差分 1
5.翻硬币 题目 链接 1208. 翻硬币 - AcWing题库 小明正在玩一个“翻硬币”的游戏。 桌上放着排成一排的若干硬币。我们用 * 表示正面用 o 表示反面是小写字母不是零。 比如可能情形是**oo***oooo 如果同时翻转左边的两个硬币则变为oooo***oooo 现在小明的问题是如果已知了初始状态和要达到的目标状态每次只能同时翻转相邻的两个硬币,那么对特定的局面最少要翻动多少次呢 我们约定把翻动相邻的两个硬币叫做一步操作。 输入格式 两行等长的字符串分别表示初始状态和要达到的目标状态。 输出格式 一个整数表示最小操作步数 数据范围 输入字符串的长度均不超过100。 数据保证答案一定有解。 输入样例1 **********
o****o****输出样例1 5输入样例2 *o**o***o***
*o***o**o***输出样例2 1第一次 WA #includebits/stdc.h
using namespace std;int ans;
string a,b;void f(char c) //没有使用引用
{if(co)c*;else co;
}int main()
{cinab;for(int i0;ia.size();i){if(a[i]!b[i]){f(a[i]);f(a[i1]);ans;}}coutans;return 0;
}第二次 AC 100% #includebits/stdc.h
using namespace std;int ans;
string a,b;void f(char c) //这里引用
{if(co)c*;else co;
}int main()
{cinab;for(int i0;ia.size();i){if(a[i]!b[i]){f(a[i]);f(a[i1]);ans;}}coutans;return 0;
}反思 函数来改变某个变量记得使用 引用 函数最基础的知识都忘记了
