😀大家好，我是白晨，一个不是很能熬夜😫，但是也想日更的人✈。如果喜欢这篇文章，点个赞👍，关注一下👀白晨吧！你的支持就是我最大的动力！💪💪💪
文章目录
- 前言
- 算法实验复习
- 一、基本算法题目
- 1.二分查找
- 2.快速排序
- 3.归并排序
- 4.最长公共子序列
- 5.最大子数组和
- 6.最长上升子序列
- 7.八皇后
- 8.加1乘2平方
- 9.电子老鼠闯迷宫
- 10.素数环
- 11.斐波那契数列
- 12.01背包
- 二、进阶算法题目
- 1.八数码
- 2.活动安排
- 3.循环赛日程表
- 4.计算矩阵连乘
- 5.图的m着色问题
- 6.装载问题
- 7.图的最短路径
- 后记
前言
本篇文章送给每一个正在复习算法实验的同学❤️，愿大家都能满分过实验。本篇文章包含了常见算法题目，方便大家查漏补缺。算法实验不能光背代码，理解其中的意义，并且能实现出来才算真的掌握。能找到实验OJ的题目我会给出链接，一定要自己敲上一回，没有在线OJ的也要自己在本地IDE上实现一下。
这里要提醒一句，如果你是西工大考生，西工大算法实验考试是在做实验的网站上的，编译器非常弱，大概能支持到C++03左右的水准，vector<vector<int>>以及pair等是使用不了的，所以，要尽量避免用C++的一些语法。
- 算法实现中的pair可以用两个int代替，一个存x坐标，一个存y坐标
- vector<vector<int>> 这个是个二维数组，不会C++的同学可以直接提前开一个二维数组
算法实验复习
一、基本算法题目
这部分是必须要掌握的算法题目，可以说只要掌握了这部分，就不会挂科了
1.二分查找
🍬原题链接：二分查找
🍭算法思想：
🍡代码实现：
class Solution {
public:int search(vector<int>& nums, int target) {int left = 0;int right = nums.size() - 1;while (left <= right){int mid = (left + right) / 2;if (nums[mid] == target)return mid;else if (nums[mid] < target)left = mid + 1;elseright = mid - 1;}return -1;}
};
2.快速排序
🍬原题链接：排序数组
🍭算法思想：
任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右
子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
🍡代码实现：
#include <iostream>using namespace std;const int N = 100010;int q[N];void quick_sort(int* q, int left, int right)
{if (left >= right)return;int i = left - 1, j = right + 1, key = q[left + right >> 1];while (i < j){do i++; while (q[i] < key);// i之前的数全部小于等于keydo j--; while (q[j] > key);// i之后的数全部大于等于keyif (i < j) swap(q[i], q[j]);}quick_sort(q, left, j);quick_sort(q, j + 1, right);
}int main()
{int n;scanf("%d", &n);for (int i = 0; i < n; i++) scanf("%d", &q[i]);quick_sort(q, 0, n - 1);for (int i = 0; i < n; i++) printf("%d ", q[i]);return 0;
}
3.归并排序
🍬原题链接：排序数组
🍭算法思想：
基本分治思想，这里不多赘述。
- 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
- 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
- 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
- 重复步骤 3 直到某一指针达到序列尾；
- 将另一序列剩下的所有元素直接复制到合并序列尾。
🍡代码实现：
#include <iostream>using namespace std;const int N = 1e5 + 10;int v[N], tmp[N];void merge_sort(int v[], int left, int right)
{if (left >= right)return;int mid = left + right >> 1;merge_sort(v, left, mid);merge_sort(v, mid + 1, right);int i = left, j = mid + 1;int k = 0;while (i <= mid && j <= right){if (v[i] < v[j]) tmp[k++] = v[i++];else tmp[k++] = v[j++];}while (i <= mid)tmp[k++] = v[i++];while (j <= right)tmp[k++] = v[j++];// 临时数组每次是从0开始使用的，所以j从0开始for (i = left, j = 0; i <= right; ++i, ++j)v[i] = tmp[j];
}int main()
{int n;cin >> n;for (int i = 0; i < n; ++i)scanf("%d", &v[i]);merge_sort(v, 0, n - 1);for (int i = 0; i < n; ++i)printf("%d ", v[i]);return 0;
}
4.最长公共子序列
🍬原题链接：最长公共子序列
🍭算法思想：
-
这道题是一道非常经典的动态规划题目，实现的思路也比较简单。
-
状态：
f(i,j)—— s1前i个字符和s2前j个字符最长公共序列。 -
初始值：f(i,0)=f(0,j)=0f(i,0)=f(0,j)=0f(i,0)=f(0,j)=0
-
状态转移方程：如果s1[i−1]==s2[i−1]s1[i-1] == s2[i-1]s1[i−1]==s2[i−1]，
f(i,j)=max(f(i−1,j−1)+1,f(i−1,j),f(i,j−1))f(i,j)=max(f(i-1,j-1) + 1, f(i-1,j),f(i,j-1)) f(i,j)=max(f(i−1,j−1)+1,f(i−1,j),f(i,j−1))
反之，
f(i,j)=max(f(i−1,j−1),f(i−1,j),f(i,j−1))f(i,j)=max(f(i-1,j-1) , f(i-1,j),f(i,j-1)) f(i,j)=max(f(i−1,j−1),f(i−1,j),f(i,j−1)) -
结果：f(m,n)f(m,n)f(m,n)
🍡代码实现：
class Solution {
public:int longestCommonSubsequence(string text1, string text2) {vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));for (int i = 1; i <= text1.size(); ++i){for (int j = 1; j <= text2.size(); ++j){if (text1[i - 1] == text2[j - 1]) // 两字符相等{dp[i][j] = max(dp[i - 1][j - 1] + 1, max(dp[i][j - 1], dp[i - 1][j]));}else{dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);}}}return dp[text1.size()][text2.size()];}
};// 纯C实现
int longestCommonSubsequence(char* text1, char* text2) {int m = strlen(text1), n = strlen(text2);int dp[m + 1][n + 1];memset(dp, 0, sizeof(dp));for (int i = 1; i <= m; i++) {char c1 = text1[i - 1];for (int j = 1; j <= n; j++) {char c2 = text2[j - 1];if (c1 == c2) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = fmax(dp[i - 1][j], dp[i][j - 1]);}}}return dp[m][n];
}
5.最大子数组和
🍬原题链接：最大子数组和
🍭算法思想：
-
状态：f(x)f(x)f(x) —— 从上一段连续的最大和到 x 位置的最大和
-
状态转移方程：f(x)=max(f(x−1)+a[x],a[x])f(x)=max(f(x-1) + a[x], a[x])f(x)=max(f(x−1)+a[x],a[x]) —— 如果上一段的连续最大和与当前数的和大于当前数，就取上一段的连续最大和与当前数的和，反之，取当前数（相当于如果 前面连续串的和的最大值 以及 当前数 相加的和 如果还不如当前数，不如从这一位置重新开始一个连续的子串，反之继续延续前面的连续串）
-
初始值：f(0)=a[0]f(0) = a[0]f(0)=a[0] —— 从a[0]开始子串
-
结果：从 f(0)−f(n−1)f(0) - f(n-1)f(0)−f(n−1) 中选出最大值。因为连续串不确定，所以最后要判断一下。
-
实例：−2,1,−3,4,−1,2,1,−5-2 ,1,-3,4,-1,2,1,-5−2,1,−3,4,−1,2,1,−5
-
序号 0 1 2 3 4 5 6 7 a[x]a[x]a[x] -2 1 -3 4 -1 2 1 -5 f(x)f(x)f(x) -2 1 -2 4 3 5 6 1
🍡代码实现：
class Solution {
public:int maxSubArray(vector<int>& nums) {// 以第i个数字结尾的最大和vector<int> dp(nums.size(), 0);dp[0] = nums[0];int Max = dp[0];for (int i = 1; i < nums.size(); ++i){// 前一个dp是否大于0，不大于0说明前面的子序列的和都没用，不如从i开始组成子序列dp[i] = dp[i - 1] > 0 ? dp[i - 1] + nums[i] : nums[i];Max = max(dp[i], Max);}return Max;}
};
6.最长上升子序列
🍬原题链接：最长上升子序列
🍭算法思想：
-
动态规划经典题目，设
v为存放输入序列的数组，dp为动态规划数组。 -
状态：dp[i] —— 前i个元素的最长上升子序列的长度。
-
初始值：dp[i] = 1 ，每一个值都可以自己构成只有一个元素的最长上升子序列。
-
状态转移方程：如果v[i]>vj ，
dp[i]=max(dp[i],dp[j]+1)dp[i] = max(dp[i],dp[j]+1) dp[i]=max(dp[i],dp[j]+1)
-
返回值：max(dp[i])
🍡代码实现：
#include <vector>
#include <iostream>
using namespace std;int main()
{int n;while (cin >> n){vector<int> v(n);for (int i = 0; i < n; ++i)cin >> v[i];vector<int> dp(n, 1);// 初始化值都为1int ans = dp[0];// 记录最大上升序列for (int i = 1; i < n; ++i){for (int j = 0; j < i; ++j){if (v[j] < v[i])dp[i] = max(dp[i], dp[j] + 1);}ans = max(ans, dp[i]);}cout << ans << endl;}return 0;
}
7.八皇后
🍬原题链接：N 皇后
深度优先搜索经典题目，西工大OJ系统这道题我原本写法过不了，因为语法不支持，所以我拿C++写的可以当作参考，我自己代码下面有一个可以过OJ的代码。
🍭算法思想：
- 根据题意，皇后的同行，同列以及所处的两个斜线不能有皇后，所以这次我们可以选择按行搜索。
- 在每一行选择一个位置放皇后，每层放置皇后时，要根据当前皇后放置情况判断是否能放置，能放置才能进入下一层递归。
- 具体皇后放置判断标准：
- 当有皇后在同一行，同一列，同一斜线上时，返回
false。 - 斜线判断：同一上斜线的皇后坐标：行数 + 列数 = 定值
- 同一下斜线的皇后坐标：行数 - 列数 = 定值
- 满足在同一条斜线上的直接
false。
- 当有皇后在同一行，同一列，同一斜线上时，返回
🍡代码实现：
class Solution {
public:// allRet代表所有方案 curv为当前皇后放置的位置 // cur为当前查找的行数，当然也能理解为当前皇后的数量 n代表棋盘行数void DFS(vector<vector<pair<int, int>>>& allRet, vector<pair<int, int>>& curv, int curRow, int n){// 有n位皇后则返回if(curRow == n){allRet.push_back(curv);return;}// 按列查找for(int i = 0; i < n; ++i){// 判断放置位置是否合法if(isVaildPos(curv, curRow, i)){curv.emplace_back(curRow, i);DFS(allRet, curv, curRow + 1, n);curv.pop_back();}}}// 判断皇后位置是否合法bool isVaildPos(vector<pair<int, int>>& curv, int i, int j){for(auto& pos : curv){// 当有皇后在同一行，同一列，同一斜线上时，返回false// 斜线判断：同一上斜线 -- 行数 + 列数 == 定值// 同一下斜线 == 行数 - 列数 == 定值if(pos.first == i || pos.second == j || pos.first + pos.second == i + j || pos.first - pos.second == i - j)return false;}return true;}// 将全部可能的组合转换为字符串数组vector<vector<string>> transString(vector<vector<pair<int, int>>>& allRet, int n){vector<vector<string>> vv;for(auto& vpos : allRet){vector<string> vs(n, string(n, '.'));for(auto& pos : vpos){vs[pos.first][pos.second] = 'Q';}vv.push_back(vs);}return vv;}vector<vector<string>> solveNQueens(int n) {vector<vector<pair<int, int>>> allRet;vector<pair<int, int>> curv;DFS(allRet, curv, 0, n);return transString(allRet, n);}
};// 纯C实现
#include <iostream>using namespace std;int a[8],cnt,usedcol[8],used1[15],used2[15];void output()
{cnt++;cout<<"No "<<cnt<<':'<<endl;for(int i=0;i<8;i++){for(int j=0;j<8;j++){if(j==a[i]) cout<<'A';else cout<<'.';}cout<<endl;}
}void dfs(int i)
{if(i==8) {output();return;}for(int j=0;j<8;j++){if(!usedcol[j]&&!used1[j+i]&&!used2[j-i+7]){a[i]=j;usedcol[j]=used1[j+i]=used2[j-i+7]=1;dfs(i+1);usedcol[j]=used1[j+i]=used2[j-i+7]=0;}}return;
}int main()
{dfs(0);return 0;
}8.加1乘2平方
这道题没找到在线OJ的链接，大家可以在西工大的OJ平台自行查看。
🍭算法思想：
广度优先搜索，每次入队 x+1，x*2，x^2，直到找到答案，输出步数即可。
🍡代码实现：
#include <iostream>
#include <queue>
using namespace std;struct T
{int num,cnt;
}e1,e2;queue <T> q;
bool flag[10001];int main()
{int m,n;cin>>m>>n;e1.num=m;e1.cnt=0;q.push(e1);flag[e1.num]=true;while(!q.empty()){e2=q.front();q.pop();if(e2.num==n){cout<<e2.cnt<<endl;break;}else{e1.cnt=e2.cnt+1;e1.num=e2.num+1;if(e1.num<=n&&!flag[e1.num]){q.push(e1);flag[e1.num]=true;}e1.num=e2.num<<1;if(e1.num<=n&&!flag[e1.num]){q.push(e1);flag[e1.num]=true;}e1.num=e2.num*e2.num;if(e1.num<=n&&!flag[e1.num]){q.push(e1);flag[e1.num]=true;}}}
}9.电子老鼠闯迷宫
原题目没有找到，所以我选了一道和原题目思路差不多的题目，把这个掌握，做电子老鼠就不会有问题了。
🍬原题链接：腐烂的橘子
🍭算法思想：
-
由于题目要求是返回最小完全腐烂的时间，所以，用深度优先搜索很不好做，并且这道题的腐烂传染方式很适合BFS。
-
首先，将开始腐烂的橘子坐标加入队列，遍历这个橘子后，将其上、下、左、右四个方向的橘子入队（下一轮腐烂的橘子）。
-
接着，按照队列的顺序将橘子出队，遍历并将其上、下、左、右四个方向的橘子结点入队。
-
将一轮腐烂的橘子遍历完后，计时+1分钟。
-
重复2、3过程，直到队列为空。
-
最后，检查是否有新鲜橘子，如果有，返回-1，没有，返回分钟数。
-
🍡代码实现：
// 算法实现中的queue<pair>可以用两个queue<int>代替，一个存x坐标，一个存y坐标
// vector<vector<int>> 这个是个二维数组，不会C++的同学可以直接提前开一个二维数组
class Solution {
public:int nextMove[4][2] = {{1, 0}, {-1, 0}, {0 , 1}, {0, -1}};int orangesRotting(vector<vector<int>>& grid) {queue<pair<int, int>> q;// 让坏橘子入队for(int i = 0; i < grid.size(); ++i){for(int j = 0; j < grid[0].size(); ++j){if(grid[i][j] == 2){q.push(make_pair(i, j));}}}int cnt = 0;while(!q.empty()){size_t sz = q.size();// 判断本次有无橘子腐烂bool flag = false;while(sz--){auto curPos = q.front();q.pop();// 探查四个方向，判断新鲜橘子，将其腐烂并入队for(int i = 0; i < 4; ++i){int curx = curPos.first + nextMove[i][0];int cury = curPos.second + nextMove[i][1];// 判断是否越界if(curx < 0 || curx >= grid.size() || cury < 0 || cury >= grid[0].size())continue;// 检测是否有新鲜橘子if(grid[curx][cury] == 1){// 本次有橘子腐烂flag = true;grid[curx][cury] = 2;q.push(make_pair(curx, cury));}}}// 本次有橘子腐烂才能+时间if(flag)++cnt;}// 判断是否有新鲜橘子for(int i = 0; i < grid.size(); ++i){for(int j = 0; j < grid[0].size(); ++j){if(grid[i][j] == 1){return -1;}}}return cnt;}
};
10.素数环
原题目OJ链接没有找到，所以我用了洛谷一个很相近的替代。遇到原题时，只需要修改输出格式即可。
🍬原题链接：素数环
🍭算法思想：
直接暴力回溯即可。
🍡代码实现：
int n, output[17], cnt = 1;
bool book[17];
void dfs(int x);
void print();
bool isprime(int x);
int main() {while (cin >> n) {if (cnt > 1)cout << endl;cout << "Case " << cnt << ":" << endl;cnt++;output[0] = 1;book[1] = 1;dfs(1);memset(book, false, sizeof(book));}return 0;
}
void dfs(int x) {if (x == n && isprime(output[n - 1] + output[0])) {print();return;}for (int i = 2; i <= n; i++) {if (!book[i] && isprime(i + output[x - 1])) {output[x] = i;book[i] = 1;dfs(x + 1);book[i] = 0;}}
}
bool isprime(int x) {if (x < 2)return false;if (x == 2)return true;for (int i = 2; i <= sqrt(x); i++) {if (x % i == 0) return false;}return true;
}
void print() {for (int i = 0; i < n - 1; i++) {cout << output[i] << " ";}cout << output[n - 1] << endl;
}
11.斐波那契数列
基本动态规划，不赘述了。
int dp[n];int fib(int m)
{if(m<=2)return 1;dp[1]=dp[2]=1;for(int i=3;i<=m;i++)dp[i]=dp[i-1]+dp[i-2];return dp[m];
}
12.01背包
🍬原题链接：背包问题
🍭算法思想：
🍡代码实现：
class Solution {
public:int backPackII(int m, vector<int>& A, vector<int>& V) {if (A.empty() || V.empty() || m < 1)return 0;const int N = A.size() + 1;const int M = m + 1;vector<vector<int> > ret;ret.resize(N);// 初始化for (int i = 0; i != N; ++i) {ret[i].resize(M, 0);}for (int i = 1; i < N; i++){for (int j = 1; j < M; j++){// 如果背包总空间都不够放第i个物品，则放 i 个物品和 放 i - 1 个物品的情况相同if (j < A[i - 1])ret[i][j] = ret[i - 1][j];// 如果空间足够放第i个物品，则要判断是否要放入，详见上文解析elseret[i][j] = max(ret[i - 1][j], ret[i - 1][j - A[i - 1]] + V[i - 1]);}}return ret[N - 1][m];}
};
完全背包思路可以自行了解，这里直接给出代码
class Solution {
public:int backPackII(int m, vector<int>& A, vector<int>& V) {if (A.empty() || V.empty() || m < 1)return 0;const int N = A.size() + 1;const int M = m + 1;vector<vector<int> > ret;ret.resize(N);// 初始化for (int i = 0; i != N; ++i) {ret[i].resize(M, 0);}for (int i = 1; i < N; i++){for (int j = 1; j < M; j++){// 如果背包总空间都不够放第i个物品，则放 i 个物品和 放 i - 1 个物品的情况相同if (j < A[i - 1])ret[i][j] = ret[i - 1][j];// 如果空间足够放第i个物品，则要判断是否要放入，详见上文解析// 现在不是和上一行比较，而是和本行的进行比较，因为完全背包中物品是没有数量限制的elseret[i][j] = max(ret[i - 1][j], ret[i][j - A[i - 1]] + V[i - 1]);}}return ret[N - 1][m];}
};
二、进阶算法题目
学会上面的基本算法，现在你最起码能拿70分了。下面到了拿100分题目的进阶题目，后面的题目会解析稍微少一些，并且我们的OJ题目都比较老，在线OJ比较难找，所以后面我主要以代码为主，题目参考西工大OJ网站。
1.八数码
洛谷的八数码和我们的有差别，我们的八数码是可以无解的，洛谷的用例都是有解的，所以我选择拿洛谷的题讲思路，下面再贴一个西工大八数码的代码。
🍬原题链接：八数码难题
🍭算法思想：
双源BFS，重在代码理解。
🍡代码实现：
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <queue>
using namespace std;typedef long long ll;const ll target = 123456780;
ll start;int np[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
int mat[4][4]; // 数字的矩阵形式
queue<ll> q; // 存储每一步走过的形式
map<ll, int> step; // 存储到每一状态所需要的步数
map<ll, int> status; // 存储这一状态是正着来的还是倒着来的int BFS()
{if (target == start)return 0;q.push(start);q.push(target);step[start] = 0;step[target] = 1;status[start] = 1;status[target] = 2;int zx, zy; // 存储0在矩阵中的位置int t = 0;while (!q.empty()){ll now, cur = q.front();now = cur;q.pop();// 将数据放到矩阵中for (int i = 3; i >= 1; --i){for (int j = 3; j >= 1; --j){mat[i][j] = now % 10;now /= 10;if (mat[i][j] == 0){zx = i;zy = j;}}}// 四个方向遍历for (int i = 0; i < 4; ++i){int nx = zx + np[i][0];int ny = zy + np[i][1];if (nx < 1 || nx > 3 || ny < 1 || ny > 3)continue;// 交换swap(mat[zx][zy], mat[nx][ny]);// 得到新的数字int num = 0;for (int k = 1; k <= 3; ++k)for (int j = 1; j <= 3; ++j)num = num * 10 + mat[k][j];if (status[num] == status[cur]){// 已经遍历过num了swap(mat[zx][zy], mat[nx][ny]);continue;}if (status[num] + status[cur] == 3){// 两边都遍历过，此时两个步数相加就是最短的步数return step[num] + step[cur];}// 未遍历过才会走到这里status[num] = status[cur];step[num] = step[cur] + 1;q.push(num);swap(mat[zx][zy], mat[nx][ny]);}t++;if (t >= 34)return -1;}return -1;
}int main()
{char c;for (int i = 0; i < 9; ++i){cin >> c;if (c == 'x')start *= 10;else{start *= 10;start += c - '0';}}cout << BFS() << endl;return 0;
}// 西工大版本
#include<iostream>
#include<map>
#include<cstring>
#include<queue>
using namespace std;string str;
map<string, int> visit;struct Node
{string status;int cnt;Node(string s = "", int c = 0) :status(s), cnt(c) {}
};void swap(string& s, int i, int j)
{char c = s[i];s[i] = s[j], s[j] = c;
}string Up(string str) {int pos = str.find("0");if (pos <= 2) return "";swap(str, pos, pos - 3);return str;
}string Down(string str) {int pos = str.find("0");if (pos >= 6) return "";swap(str, pos, pos + 3);return str;
}string Left(string str) {int pos = str.find("0");if (pos == 0 || pos == 3 || pos == 6) return "";swap(str, pos, pos - 1);return str;
}string Right(string str) {int pos = str.find("0");if (pos == 2 || pos == 5 || pos == 8) return "";swap(str, pos, pos + 1);return str;
}int bfs()
{visit[str] = 1;queue<Node> Q;Q.push(Node(str));while (!Q.empty()){Node cn = Q.front();Q.pop();if (cn.status == "123456780")return cn.cnt;string news = Up(cn.status);if (news != "" && visit[news] != 1){Q.push(Node(news, cn.cnt + 1));visit[news] = 1;}news = Down(cn.status);if (news != "" && visit[news] != 1){Q.push(Node(news, cn.cnt + 1));visit[news] = 1;}news = Left(cn.status);if (news != "" && visit[news] != 1){Q.push(Node(news, cn.cnt + 1));visit[news] = 1;}news = Right(cn.status);if (news != "" && visit[news] != 1){Q.push(Node(news, cn.cnt + 1));visit[news] = 1;}}return -1;
}int main()
{string tmp;int n = 9;while (n && cin >> tmp){str += tmp;n--;}cout << bfs() << endl;return 0;
}2.活动安排
🍭算法思想：贪心算法
🍡代码实现：
#include <iostream>
#include <algorithm>
using namespace std;struct active
{int b,e;
}a[1001];struct rule
{bool operator()(const active &a,const active &b){return a.e<b.e;}
};int main()
{int n;cin>>n;for(int i=0;i<n;i++)cin>>a[i].b>>a[i].e;sort(a,a+n,rule());int r=a[0].e;int ans=1;for(int i=1;i<n;i++){if(a[i].b>=r){ans++;r=a[i].e;}}cout<<ans<<endl;return 0;
}
3.循环赛日程表
🍭算法思想：
- 按分治策略，我们可以将所有的选手分为两半，则n个选手的比赛日程表可以通过n/2个选手的比赛日程表来决定。
- 递归地用这种一分为二的策略对选手进行划分，直到只剩下两个选手时，比赛日程表的制定就变得很简单。
- 这时只要让这两个选手进行比赛就可以了。
🍡代码实现：
// 循环赛日程表
#include<iostream>
#include<cmath>
using namespace std;void schedule(int k, int n, int** array);int main()
{int k; // 运动员的人数n=2^kcout << "运动员的人数为n（n=2^k），请输入k的值：";cin >> k;int n = pow(2, k); // 运动员的人数n=2^kint** array = new int* [n+1]; // 循环赛日程表for (int i = 0;i < n+1;i++) array[i] = new int[n+1];// 填充日程表schedule(k, n, array);// 输出日程表cout << "\n循环赛日程表为：\n";for (int i = 1;i <= n;i++){for (int j = 1;j <= n;j++)cout << array[i][j] << " ";cout << "\n";}// 删除二维数组for (int i = 0;i < n + 1;i++)delete[] array[i];delete[] array;return 0;
}void schedule(int k, int n, int** array) // 数组下标从1开始
{for (int i = 1;i <= n;i++) // 第一行排1-narray[1][i] = i;int m = 1; // 用来控制每一次填表时i行j列的起始填充位置for (int s = 1;s <= k;s++) // k指分成k大部分进行填充日程表；s指第几大部分{n = n / 2;for (int t = 1;t <= n;t++) // 第s部分内的循环{for (int i = m + 1;i <= 2 * m;i++) // 行{for (int j = m + 1;j <= 2 * m;j++) // 列{array[i][j + (t - 1) * m * 2] = array[i - m][j + (t - 1) * m * 2 - m]; //左上角等于右下角的值array[i][j + (t - 1) * m * 2 - m] = array[i - m][j + (t - 1) * m * 2]; //左下角等于右上角的值}}}m *= 2;}}4.计算矩阵连乘
🍭算法思想：动态规划
🍡代码实现：
#include<iostream>
#include <cmath>
using namespace std;
const int N = 11;
int row[N], col[N], n, dp[N][N];int main()
{cin >> n;for (int i = 1; i <= n; i++)cin >> row[i] >> col[i];for(int cnt = 1;cnt<=n;cnt++)for (int i = 1,j=cnt; j <= n; i++,j++){if (i == j) dp[i][j] = 0;else{dp[i][j] = 100000;for (int k = i; k < j; k++) //k必须从i开始dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + row[i] * col[k] * col[j]);}}cout << dp[1][n] << endl;return 0;
}5.图的m着色问题
给定无向连通图G=(V, E)和m种不同的颜色，用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中相邻的两个顶点有不同的颜色。这个问题是图的m可着色判定问题。若一个图最少需要m种颜色才能使图中每条边连接的两个顶点着不同颜色，则称这个数m为该图的色数。求一个图的色数m的问题称为图的m可着色优化问题。
🍭算法思想：
本质上就是图的遍历问题。
🍡代码实现：
#include<iostream>
#include<vector>
using namespace std;
int n, m, r, ans;
int color[20];
vector <int> b[20]; //邻接表储存无向图bool check(int v,int k)
{for (int i = 0; i < b[v].size(); i++){int u = b[v][i];if (color[u] == k)return false;}return true;
}void dfs(int v,int c)
{color[v] = c;for (int i = 0; i < b[v].size(); i++){int u = b[v][i];if (color[u]) continue;for (int k = 1; k <= m; k++){if (check(u, k)){dfs(u, k);int j;for (j = 0; j < n; j++){if (!color[j])break;}if (j >= n)ans++;color[u] = 0; //特别注意此处需要消除标记}}}
}int main()
{cin >> n >> r >> m;for (int i = 0; i < r; i++){int u, v;cin >> u >> v;b[u].push_back(v);b[v].push_back(u);}for(int i=1;i<=m;i++)dfs(0,i);cout << ans << endl;return 0;
}6.装载问题
🍭算法思想：分治法
🍡代码实现：
#include<iostream>using namespace std;
int sign = 0, n, c1, c2, weigh[100];void FoundPath(int c1_w, int c2_w, int times)
{if (c1_w > c1 || c2_w > c2) return;if (times == n) {sign = 1;return;}FoundPath(c1_w + weigh[times], c2_w, times + 1);FoundPath(c1_w, c2_w + weigh[times], times + 1);return;
}int main()
{int cnt = 0, c1_w = 0, c2_w = 0, times = 0, ans[100];while (cin >> c1 >> c2 >> n){if (n == 0 && c1 == 0 && c2 == 0) break;for (int i = 0; i < n; i++)cin >> weigh[i];sign = 0, c1_w = 0, c2_w = 0, times = 0;FoundPath(c1_w, c2_w, times);ans[cnt++] = sign;}for (int i = 0; i < cnt; i++){if (ans[i] == 0)cout << "No" << endl;elsecout << "Yes" << endl;}return 0;
}7.图的最短路径
🍭算法思想：迪杰斯特拉算法
🍡代码实现：
#include<iostream>
using namespace std;int matrix[100][100]; //邻接矩阵表示带权有向图
bool visited[100]; //标记数组
int dist[100]; //源点到顶点i的最短距离
int path[100]; //记录最短路的路径
int source; //源点
int vertex_num; //顶点数
int arc_num; //边数void Dijkstra(int source)
{visited[source] = true;for (int i = 1; i <= vertex_num; i++){dist[i] = matrix[source][i]; //dist表示当前从源点到顶点i的最短特殊路径if(dist[i]!=INT_MAX)path[i] = source; //记录从源点到顶点i的最短特殊路径i的前一个顶点}int min_cost; //权值最小int min_cost_index; //权值最小的下标for (int i = 1; i <= vertex_num; i++) //找到源点到另外vertex_num-1个点的最短路径{min_cost = INT_MAX;for (int j = 1; j <= vertex_num; j++){if (visited[j] == false && dist[j] < min_cost) //找到权值最小{min_cost = dist[j];min_cost_index = j;}}visited[min_cost_index] = true; //该点已找到，进行标记for (int j = 1; j <=vertex_num; j++) //更新dist数组{if (visited[j] == false &&matrix[min_cost_index][j] != INT_MAX && //确保两点之间有边matrix[min_cost_index][j] + min_cost < dist[j]){dist[j] = matrix[min_cost_index][j] + min_cost;path[j] = min_cost_index;}}}
}void output()
{for (int i = 1; i <= vertex_num; i++){if (i != source){cout << source << "到" << i << "最短距离是：" << dist[i] << "，路径是：" << i;for (int t = path[i];t != source; t = path[t])cout << "--" << t;cout << "--" << source << endl;}}
}//单源最短路径
int main()
{cin >> vertex_num >> arc_num;for (int i = 0; i <= vertex_num; i++){for (int j = 0; j <= vertex_num; j++)if(i==j)matrix[i][j]=0;else matrix[i][j] = INT_MAX; //初始化matrix数组}int u, v, w;for (int i = 0; i < arc_num; i++){cin >> u >> v >> w;matrix[u][v] = w; //u到v的长度为w}cin >> source;Dijkstra(source);output();return 0;
}后记
掌握这最常见的19道题一般来说就能拿满分了，多多敲代码，不要只背诵代码。如果你感觉题目有些多，可以提前开始复习，一天做上几道。如果你只想及格，只需要掌握基本算法题目即可，保底70分。
最后，祝愿大家能考的都会，半个小时做完全部。
如果解析有不对之处还请指正，我会尽快修改，多谢大家的包容。
如果大家喜欢这个系列，还请大家多多支持啦😋！
如果这篇文章有帮到你，还请给我一个大拇指 👍和小星星 ⭐️支持一下白晨吧！喜欢白晨这篇文章的话，不如关注👀白晨，以便看到最新更新哟！！！
