今日涉及算法:
暴力枚举,二分,贪心,dfs,bfs,01背包,双指针,哈希表,并查集。最短路和树,前缀和,质数约数,快速幂大家自己复习一下看看模板就好,这些就是基本常考的了,接下来就开始今天的疯狂复习之路吧!
一丶全排列问题(暴力枚举)
题目链接:P1706 全排列问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目要求:
按照字典序输出自然数 1 到 n 所有不重复的排列,即 nn 的全排列,要求所产生的任一数字序列中不允许出现重复的数字。
解题思路:
这是一个全排列暴力,大家记好,比赛很可能出!
按我自己的方法四步
全排列四步:
第一步:搞定标记数组(用没用过这个数),原数组和输入。
第二步:判断结束条件(如何时打印)。
第三步:考虑循环次数,判断用没用过。
第四步:递归回溯。
#include<bits/stdc++.h> using namespace std; int n,pd[100],a[100]; void dfs(int k) { if(k==n) { for(int i=1;i<=n;i++) { printf("%5d",a[i]); } printf("\n"); return ; } for(int i=1;i<=n;i++) { if(!pd[i]) { pd[i]=1; a[k+1]=i; dfs(k+1); pd[i]=0; } } } int main() { cin>>n; dfs(0); return 0; }
二、小A的糖果(贪心)
题目链接:P3817 小A的糖果 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目要求:
小 A 有 n 个糖果盒,第 i 个盒中有 ai 颗糖果。
小 A 每次可以从其中一盒糖果中吃掉一颗,他想知道,要让任意两个相邻的盒子中糖的个数之和都不大于 x,至少得吃掉几颗糖。
解题思路:
贪心,源于生活,你现实够贪心,贪心写的就好(不是)
贪心是我认为不和其他板子一样,纯粹就是看情况,如果不顺真的贪不出来,这个东西蓝桥也不会
出太难,大家有兴趣可以去练练其他贪心。
#include<bits/stdc++.h> using namespace std; long long sum; int n,x,a[100010]; int main() { cin>>n>>x; for(int i=1;i<=n;i++) { cin>>a[i]; } for(int i=1;i<n;i++) { if(a[i]+a[i+1]>x) { sum += a[i+1] - x+a[i]; a[i+1] = x-a[i]; } } cout<<sum; return 0; }
三、木材加工(二分)
题目链接:P2440 木材加工 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目要求:
木材厂有 n 根原木,现在想把这些木头切割成 k 段长度均为 l 的小段木头(木头有可能有剩余)。
当然,我们希望得到的小段木头越长越好,请求出 l 的最大值。
木头长度的单位是 cm,原木的长度都是正整数,我们要求切割得到的小段木头的长度也是正整数。
例如有两根原木长度分别为 11 和 21,要求切割成等长的 6 段,很明显能切割出来的小段木头长度最长为 5。
解题思路:
二分,二分的check是最难写的,可以多思考一下。
二分四步法:
第一步:数组,录入。
第二步:定义左端点,右端点,考虑是最大值最小还是最小值最大
如果求大于等于里面的最小值,求第一次出现x的位置,用(l+r+1)/2
如果求小于等于里面的最大值,求最后一次出现x的位置,用(l+r)/2
第三步:根据题目考虑check函数如何去写,调整细节
第四步:循环板子
求出最小值最大,用第二个,这里我们让每个木头都除mid加起来,如果大于等于k就让他l=mid,否则r=mid。(如果是另一个模板第一个就是r=mid)
#include<bits/stdc++.h> using namespace std; int n,k; int a[100007]; int main() { cin>>n>>k; int r = 0; for(int i=1;i<=n;i++) { cin>>a[i]; if(a[i]>r) { r = a[i]; } } int l=0,mid; while(l+1<r) { mid=(l+r)/2; int sum=0; for(int i=1;i<=n;i++) { sum += a[i]/mid; } if(sum>=k) { l = mid; } else { r = mid; } } cout<<l<<endl; return 0; }
四、八皇后(dfs)
题目链接:八皇后
题目要求:
一个如下的 6×6 的跳棋棋盘,有六个棋子被放置在棋盘上,使得每行、每列有且只有一个,每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。
上面的布局可以用序列2 4 6 1 3 5 来描述,第 i 个数字表示在第 i 行的相应位置有一个棋子,如下:
行号 1 2 3 4 5 6
列号 2 4 6 1 3 5
这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。
并把它们以上面的序列方法输出,解按字典顺序排列。
请输出前 3 个解。最后一行是解的总个数。
解题思路:
为什么要用八皇后,就是因为他很经典,用到了标记数组,斜线判断等,综合练习了dfs
dfs四步法:
第一步:定义好标记数组,存图数组,如果是迷宫 连通块需要定义方向数组,录入
第二步:判断结束条件是否打印(有的时候不需要打印)
第三步:循环判断四个方向或者八个方向(没有方向的话直接判断有没有用过),有没有用过。
第四步:递归调用,回溯。
#include<bits/stdc++.h> using namespace std; int a[100],b[100],c[100],d[100]; //a数组表示的是行; //b数组表示的是列; //c表示的是左下到右上的对角线; //d表示的是左上到右下的对角线; int n,sum; int print() { if(sum<=2) { for(int k=1;k<=n;k++) { cout<<a[k]<<" "; } cout<<endl; } sum++; } void queen(int i) { if(i>n) { print(); return; } else { for(int j=1;j<=n;j++) { if((!b[j])&&(!c[i+j])&&(!d[i-j+n])) { a[i]=j; b[j]=1; c[i+j]=1; d[i-j+n]=1; queen(i+1); b[j]=0; c[i+j]=0; d[i-j+n]=0; } } } } int main() { cin>>n; queen(1); cout<<sum; return 0; }
五、子串分值(双指针)
题目链接:子串分值 - 蓝桥云课 (lanqiao.cn)
题目要求:
对于一个字符串 S,我们定义 S 的分值 f(S) 为 S 中恰好出现一次的字符个数。例如f(aba)=1,f(abc)=3,f(aaa)=0。现在给定一个字符串 S0⋯n−1(长度为 n,1≤n≤105),请你计算对于所有 S 的非空子串 Si⋯j(0≤i≤j
解题思路:
双指针,双指针四步法也不难。
第一步:首先考虑这个题目是滑窗还是快慢指针,然后正常的录入。
第二步:如果是滑窗,那就确定滑窗的判断条件,如果是快慢指针,考虑右指针在末尾还是在左指针前面一个一起走。
第三步:选择while或者for循环,进行双指针扫描,如果是滑窗判断完之后记得更新指针位置,快慢指针也是。
第四步:如果是累积的和就每次相加,如果不是就直接输出啦。
这个就是双指针,一个左端点一个右端点在末尾扫描,然后累加
#include<bits/stdc++.h> using namespace std; int main() { string s; cin >> s; long long len = s.length(); long long sum = 0; int l,r; char ss; for(int i = 0; i < len;i++) { ss = s[i]; for(r = i + 1; r < len;r++) { if(s[r]==ss) { break; } } for(l = i - 1; l >= 0;l--) { if(s[l]==ss) { break; } } sum += (r - i) * (i - l); cout<<l<<""; } cout << sum; return 0; }
六、缺失的第一个正数(哈希表)
题目链接:41. 缺失的第一个正数 - 力扣(LeetCode) (leetcode-cn.com)
题目要求:
给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
解题思路:
简单哈希的四步法
第一步:定义哈希数组,录入。
第二步:在录入数据的时候每次让哈希数组在该值的下标++或者=1(如果是abcd这种记得-'a')
第三步:判断值,如果在哈希表里出现次数少于条件或者大于条件就输出(根据题目多变)
第四步:输出原数组值或者该哈希值。
记得,循环判断哈希表里的值要根据数据范围开循环范围。这是一个简单哈希,难得也不会考估计,这个可以套在很多题目里面用,灵活多变
#define MAX 500001 int hash[500001]; int firstMissingPositive(int* nums, int numsSize){ memset(hash,0,sizeof(hash)); for(int i=0;i { if(nums[i]>0&&nums[i] { hash[nums[i]]++; } } for(int i=1;i<=numsSize;i++) { if(hash[i]==0) { return i; } } return numsSize+1; }
七、马的遍历(bfs)
题目链接:P1443 马的遍历 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目要求:
有一个 n×m 的棋盘,在某个点 (x,y) 上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步。
解题思路:
标准的bfs,bfs四步法
第一步:存图,标记数组,确定起始点结束点,方向数组。
第二步:有必要可以初始化,定义结构体(或者其他的办法搞队列),定义队列。
第三步:压入起点,时间(可以根据题目单独判断不进队列),标记,定义变量获取队首元素,弹出,循环判断方向是否出界是否用过。
第四步:如果到了终点返回或者输出,否则标记并且压入,时间+1.
#include<bits/stdc++.h> using namespace std; const int N = 401; int dx[] = {2,-2,2,-2,-1,1,-1,1}; int dy[] = {1,1,-1,-1,2,2,-2,-2}; int a[N][N]; int b[N][N]; int n,m,x,y; struct node{ int x,y; }; void bfs(int x,int y) { queue<node>q; q.push({x,y}); a[x][y] = 1; b[x][y] = 0; while(q.size()) { node tt = q.front(); q.pop(); for(int i=0;i<8;i++) { int xxx = tt.x + dx[i]; int yyy = tt.y + dy[i]; if(xxx<1||xxx>n||yyy<1||yyy>m) { continue; } if(!a[xxx][yyy]) { a[xxx][yyy] = 1; b[xxx][yyy] = b[tt.x][tt.y]+1; q.push({xxx,yyy}); } } } } int main() { memset(b,-1,sizeof(b)); cin >> n >> m >> x >> y; bfs(x,y); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { printf("%-5d",b[i][j]); } cout<<endl; } return 0; }
八、合根植物(并查集)
题目链接:进去登录点题集 真题 搜索合根植物
题目要求:
w星球的一个种植园,被分成 m * n 个小格子(东西方向m行,南北方向n列)。每个格子里种了一株合根植物。
这种植物有个特点,它的根可能会沿着南北或东西方向伸展,从而与另一个格子的植物合成为一体。
如果我们告诉你哪些小格子间出现了连根现象,你能说出这个园中一共有多少株合根植物吗?
解题思路:
并查集四步法
第一步:初始化函数
第二步:查找函数
第三步:判断函数
第四步:根据题目要求循环使用这些函数
我相信各位学过并查集的都懂我的意思,没学过的话来这里学 链接:通俗易懂并查集
#include<bits/stdc++.h> using namespace std; const int N = 1000010; int m,n,k,pre[N],ans; bool vis[N]; void init() { memset(vis,0,sizeof(vis)); for(int i=1;i<=n*m;i++) { pre[i] = i; } } int find(int x) { if(x!=pre[x]) { return pre[x] = find(pre[x]); } return x; } void join(int x,int y) { int xx = find(x); int yy = find(y); if(xx!=yy) { pre[yy] = xx; } } int main() { scanf("%d%d%d",&n,&m,&k); init(); for(int i=0;i<k;i++) { int x,y; scanf("%d%d",&x,&y); join(x,y); } for(int i=1;i<=n*m;i++) { vis[find(i)] = 1; } for(int i=1;i<=n*m;i++) { ans += vis[i]; } cout<<ans<<endl; return 0; }
九、采药(01背包)
题目链接:P1048 [NOIP2005 普及组] 采药 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目要求:
辰辰是个天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。为此,他想拜附近最有威望的医师为师。医师为了判断他的资质,给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说:“孩子,这个山洞里有一些不同的草药,采每一株都需要一些时间,每一株也有它自身的价值。我会给你一段时间,在这段时间里,你可以采到一些草药。如果你是一个聪明的孩子,你应该可以让采到的草药的总价值最大。”
如果你是辰辰,你能完成这个任务吗?
解题思路:
01背包啊 背包四步法(这里根据y总的dp分析来的)
第一步:确定集合,集合属性。
第二步:状态计算。
第三步:确定状态转移方程
第四步:初始化并且dp
集合:f[i][j]表示采第i株药,花费时间j可以采到的草药的最大总价值。集合属性:max
状态计算: 最后一个不同点就是选不选第i个物品 左边所有不选第i个物品的方案 右边是所有选择
左边:从1-i-1选总体积小于j的集合 左边这个集合就是fi-1,j
右边:从1-i选并且总体积小于j i固定所以只看变化的部分包含i的话小于等于j 如果不包含就是小于等于j-vi 最大值式f(i-1,j-vi) 最终结果:f(i-1,j-vi)+wi
状态转移方程:f[j] = max(f[j],f[j-v[i]]+w[i])(01背包优化到一维,i可以不用)
二维状态转移:f[i,j] = max(f(i-1,j),fi-1(j-vi)+wi)
#include<bits/stdc++.h> using namespace std; int f[1001]; int v[1001],w[1001]; int main() { int n,m; cin>>n>>m; for(int i=1;i<=m;i++) { cin>>v[i]>>w[i]; } for(int i=1;i<=m;i++) { for(int j=n;j>=v[i];j--) { f[j] = max(f[j],f[j-v[i]]+w[i]); } } cout<<f[n]; return 0; }
十、数字三角形(线性dp)
题目链接:]数字三角形
题目要求:
观察下面的数字金字塔。
写一个程序来查找从最高点到底部任意处结束的路径,使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。
7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
在上面的样例中,从 7→3→8→7→5 的路径产生了最大
解题思路:
很简单的线性dp,可以从上到下,从下到上。四步法
第一步:确定集合,集合属性,根据题目要求选择一种方法(自己熟悉的)。
第二步:状态计算。
第三步:确定状态转移方程
第四步:初始化并且dp
状态表示:f[i,j]
集合:所有从起点走到ij的路径
属性:max
状态计算
左上状态:fi-1j]-1+a[i,j]从起点走到这里的最大值 右上状态f[i-1,j]+a[i,j] 同上 两者取max就是答案
方程:f[i,j] = max(f[i-1,j]+a[i,j],f[i-1,j-1]+a[i,j]
倒着做的方程:f[i][j] = max(a[i+1][j],a[i+1][j+1])
读入不用初始化 i=r j=i >=1 最后最顶上的就是答案
#include<bits/stdc++.h> using namespace std; int r; int f[1010][1010]; int main() { cin >> r; for(int i=1;i<=r;i++) { for(int j=1;j<=i;j++) { cin>>f[i][j]; } } for(int i = r;i>=1;i--) { for(int j=i;j>=1;j--) { f[i][j] = max(f[i+1][j],f[i+1][j+1])+f[i][j]; } } cout<<f[1][1]; return 0; }
相信各位通过这些题目能巩固基本功,希望各位蓝桥杯都能考出自己想要的成绩!