今日涉及算法：
暴力枚举，二分，贪心，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; }
二、小Ａ的糖果（贪心）
题目链接：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。
解题思路：
二分，二分的ｃｈｅｃｋ是最难写的，可以多思考一下。
二分四步法：
第一步：数组，录入。
第二步：定义左端点，右端点，考虑是最大值最小还是最小值最大
如果求大于等于里面的最小值，求第一次出现x的位置，用（ｌ＋ｒ＋１）／２
如果求小于等于里面的最大值，求最后一次出现ｘ的位置，用（ｌ＋ｒ）／２
第三步：根据题目考虑ｃｈｅｃｋ函数如何去写,调整细节
第四步：循环板子
求出最小值最大，用第二个，这里我们让每个木头都除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; }
相信各位通过这些题目能巩固基本功，希望各位蓝桥杯都能考出自己想要的成绩！
