如有WA全是多组输入问题，请自行修改，或在评论区向我反馈，我会及时修改，如有注释不够详细等问题，也可联系我进行修改：
P1138 American Heritage
C++：
#include <iostream>#include <string>using namespace std;string inorder, preorder; // 前序遍历和中序遍历void postorder(int in_start, int in_end, int pre_start, int pre_end) { if (in_start > in_end) { // 如果起点大于终点，说明没有子树需要构造 return; } // 根节点为前序遍历的第一个节点 char root = preorder[pre_start]; // 在中序遍历中找到根节点的位置 int root_pos = inorder.find(root); // 递归构建左子树，in_start到root_pos-1为左子树的中序遍历，pre_start+1到pre_start+1+root_pos-in_start-1为左子树的前序遍历 postorder(in_start, root_pos - 1, pre_start + 1, pre_start + 1 + root_pos - in_start - 1); // 递归构建右子树，root_pos+1到in_end为右子树的中序遍历，pre_start+1+root_pos-in_start到pre_end为右子树的前序遍历 postorder(root_pos + 1, in_end, pre_start + 1 + root_pos - in_start, pre_end); // 输出当前节点 cout << root;}int main() { cin >> inorder >> preorder; // 输入中序遍历和前序遍历 postorder(0, inorder.size() - 1, 0, preorder.size() - 1); // 构造二叉树并输出后序遍历 cout << endl; return 0;}C：
#include <stdio.h>#include <string.h>#define MAX_N 26char inorder[MAX_N + 1], preorder[MAX_N + 1]; // 前序遍历和中序遍历void postorder(int in_start, int in_end, int pre_start, int pre_end) { if (in_start > in_end) { // 如果起点大于终点，说明没有子树需要构造 return; } // 根节点为前序遍历的第一个节点 char root = preorder[pre_start]; // 在中序遍历中找到根节点的位置 int root_pos = strchr(inorder, root) - inorder; // 递归构建左子树，in_start到root_pos-1为左子树的中序遍历，pre_start+1到pre_start+1+root_pos-in_start-1为左子树的前序遍历 postorder(in_start, root_pos - 1, pre_start + 1, pre_start + 1 + root_pos - in_start - 1); // 递归构建右子树，root_pos+1到in_end为右子树的中序遍历，pre_start+1+root_pos-in_start到pre_end为右子树的前序遍历 postorder(root_pos + 1, in_end, pre_start + 1 + root_pos - in_start, pre_end); // 输出当前节点 printf("%c", root);}int main() { scanf("%s%s", inorder, preorder); // 输入中序遍历和前序遍历 postorder(0, strlen(inorder) - 1, 0, strlen(preorder) - 1); // 构造二叉树并输出后序遍历 printf("\n"); return 0;}P1220 皇后摆放问题
C++：
#include <iostream>#include <vector>using namespace std;const int N = 8;vector<int> pos(N); // 记录皇后在每一行的位置int res = 0; // 记录摆放的种类数bool is_valid(int row, int col) { for (int i = 0; i < row; i++) { // 遍历前面的行，看是否有冲突 if (pos[i] == col || pos[i] - i == col - row || pos[i] + i == col + row) { return false; // 冲突 } } return true; // 不冲突}void backtrack(int row) { if (row == N) { // 找到一种合法摆法 res++; return; } for (int col = 0; col < N; col++) { if (is_valid(row, col)) { // 如果当前位置合法，则放置皇后 pos[row] = col; backtrack(row + 1); // 递归放置下一行的皇后 } }}int main() { int cnt = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { int x; cin >> x; if (x == 1) { // 已经有皇后了 pos[cnt++] = j; // 记录位置 } } } backtrack(cnt); // 从第 cnt 行开始回溯 cout << res << endl; // 输出摆法的种类数 return 0;}C：
#include <stdio.h>#include <stdbool.h>#define N 8int pos[N]; // 记录皇后在每一行的位置int res = 0; // 记录摆放的种类数bool is_valid(int row, int col) { for (int i = 0; i < row; i++) { // 遍历前面的行，看是否有冲突 if (pos[i] == col || pos[i] - i == col - row || pos[i] + i == col + row) { return false; // 冲突 } } return true; // 不冲突}void backtrack(int row) { if (row == N) { // 找到一种合法摆法 res++; return; } for (int col = 0; col < N; col++) { if (is_valid(row, col)) { // 如果当前位置合法，则放置皇后 pos[row] = col; backtrack(row + 1); // 递归放置下一行的皇后 } }}int main() { int cnt = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { int x; scanf("%d", &x); if (x == 1) { // 已经有皇后了 pos[cnt++] = j; // 记录位置 } } } backtrack(cnt); // 从第 cnt 行开始回溯 printf("%d\n", res); // 输出摆法的种类数 return 0;}P1236 夺取宝藏
C++:
#include <iostream>#include <cstring>#include <algorithm>using namespace std;const int N = 1010;int a[N][N]; // 保存宝藏的价值int f[N][N]; // f[i][j]表示从左上角走到(i, j)时能够得到的最大价值int main() { int m, n; while (cin >> m >> n) { memset(f, 0, sizeof f); // 初始化f数组为0 for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { cin >> a[i][j]; } } for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { f[i][j] = max(f[i - 1][j], f[i][j - 1]) + a[i][j]; // 动态转移方程 } } cout << f[m][n] << endl; // 输出最大价值之和 } return 0;}C:
#include <stdio.h>#include <string.h>#include <stdlib.h>#define N 1010int a[N][N]; // 保存宝藏的价值int f[N][N]; // f[i][j]表示从左上角走到(i, j)时能够得到的最大价值int main() { int m, n; while (scanf("%d%d", &m, &n) != EOF) { memset(f, 0, sizeof f); // 初始化f数组为0 for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { scanf("%d", &a[i][j]); } } for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { f[i][j] = f[i - 1][j] > f[i][j - 1] ? f[i - 1][j] : f[i][j - 1]; f[i][j] += a[i][j]; // 动态转移方程 } } printf("%d\n", f[m][n]); // 输出最大价值之和 } return 0;}P1268 连续子段的最大和
C++:
#include <iostream>#include <algorithm>using namespace std;const int N = 10010;int a[N], f[N];int main() { int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } int res = a[1]; // 初始化res为第一个数 f[1] = a[1]; // 初始化f[1]为第一个数 for (int i = 2; i <= n; i++) { f[i] = max(f[i - 1] + a[i], a[i]); // 动态转移方程 res = max(res, f[i]); // 更新最大值 } cout << res << endl; // 输出子段的最大和 return 0;}C:
#include <stdio.h>#include <stdlib.h>#include <string.h>#define N 10010int a[N], f[N];int main() { int n; scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); } int res = a[1]; // 初始化res为第一个数 f[1] = a[1]; // 初始化f[1]为第一个数 for (int i = 2; i <= n; i++) { f[i] = f[i - 1] + a[i] > a[i] ? f[i - 1] + a[i] : a[i]; // 动态转移方程 res = res > f[i] ? res : f[i]; // 更新最大值 } printf("%d\n", res); // 输出子段的最大和 return 0;}P1296 分形宇宙
C++
#include <iostream>#include <cmath>using namespace std;const int N = 4000;char g[N][N]; // 定义二维字符数组，存储分形图int n; // 定义分形图的度void dfs(int x, int y, int k) { // 定义递归函数 if (k == 1) { // 递归边界，一度分形就是一个点 g[x][y] = 'X'; return; } int len = pow(3, k - 2); // 每个子分形的长度 dfs(x, y, k - 1); // 左上角子分形 dfs(x, y + 2 * len, k - 1); // 右上角子分形 dfs(x + len, y + len, k - 1); // 中间子分形 dfs(x + 2 * len, y, k - 1); // 左下角子分形 dfs(x + 2 * len, y + 2 * len, k - 1); // 右下角子分形 for (int i = x; i < x + len; i++) { // 添加连线 g[i][y + len] = ' '; } for (int i = y; i < y + 2 * len; i++) { // 添加连线 g[x + len][i] = '-'; }}int main() { while (cin >> n) { int len = pow(3, n - 1); // 计算分形的长度 for (int i = 0; i < len; i++) { // 初始化分形图 for (int j = 0; j < len; j++) { g[i][j] = ' '; } } dfs(0, 0, n); // 生成分形图 for (int i = 0; i < len; i++) { // 输出分形图 for (int j = 0; j < len; j++) { cout << g[i][j]; } cout << endl; } cout << '-' << endl; // 分割线 } return 0;}C:
#include <stdio.h>#include <math.h>#define N 4000char g[N][N]; // 定义二维字符数组，存储分形图int n; // 定义分形图的度void dfs(int x, int y, int k) { // 定义递归函数 if (k == 1) { // 递归边界，一度分形就是一个点 g[x][y] = 'X'; return; } int len = pow(3, k - 2); // 每个子分形的长度 dfs(x, y, k - 1); // 左上角子分形 dfs(x, y + 2 * len, k - 1); // 右上角子分形 dfs(x + len, y + len, k - 1); // 中间子分形 dfs(x + 2 * len, y, k - 1); // 左下角子分形 dfs(x + 2 * len, y + 2 * len, k - 1); // 右下角子分形 for (int i = x; i < x + len; i++) { // 添加连线 g[i][y + len] = ' '; } for (int i = y; i < y + 2 * len; i++) { // 添加连线 g[x + len][i] = '-'; }}int main() { while (scanf("%d", &n) != EOF) { int len = pow(3, n - 1); // 计算分形的长度 for (int i = 0; i < len; i++) { // 初始化分形图 for (int j = 0; j < len; j++) { g[i][j] = ' '; } } dfs(0, 0, n); // 生成分形图 for (int i = 0; i < len; i++) { // 输出分形图 for (int j = 0; j < len; j++) { printf("%c", g[i][j]); } printf("\n"); } printf("-\n"); // 分割线 } return 0;}P1305 素数环
C++
#include <iostream>#include <vector>#include <cstring>using namespace std;const int MAXN = 20;int n;vector<int> path; // 存储当前的素数环bool used[MAXN]; // 记录数字是否使用过bool is_prime[50]; // 记录素数void dfs(int k) { // k表示当前要填的数字 if (k == n) { // 递归边界，当前素数环填满 if (is_prime[path[0] + path[n - 1]]) { // 判断首尾数字的和是否为素数 cout << path[0]; for (int i = 1; i < n; i++) { cout << " " << path[i]; } cout << endl; } return; } for (int i = 2; i <= n; i++) { // 枚举当前要填的数字 if (used[i]) continue; // 当前数字已经使用过了 if (!is_prime[i + path[k - 1]]) continue; // 当前数字和前一个数字的和不是素数 used[i] = true; path.push_back(i); dfs(k + 1); path.pop_back(); used[i] = false; }}int main() { // 预处理素数表 memset(is_prime, true, sizeof(is_prime)); is_prime[0] = is_prime[1] = false; for (int i = 2; i < 50; i++) { if (is_prime[i]) { for (int j = i * i; j < 50; j += i) { is_prime[j] = false; } } } // 处理输入输出 int cnt = 0; while (cin >> n) { if (cnt > 0) cout << endl; // 多组数据之间的分隔符 cnt++; cout << "Case " << cnt << ":" << endl; path.clear(); // 清空存储当前素数环的vector memset(used, false, sizeof(used)); used[1] = true; // 素数环从1开始 path.push_back(1); dfs(1); } return 0;}C:
#include <stdio.h>#include <stdbool.h>#include <string.h>#define MAXN 20int n;int path[MAXN]; // 存储当前的素数环bool used[MAXN]; // 记录数字是否使用过bool is_prime[50]; // 记录素数void dfs(int k) { // k表示当前要填的数字 if (k == n) { // 递归边界，当前素数环填满 if (is_prime[path[0] + path[n - 1]]) { // 判断首尾数字的和是否为素数 printf("%d", path[0]); for (int i = 1; i < n; i++) { printf(" %d", path[i]); } printf("\n"); } return; } for (int i = 2; i <= n; i++) { // 枚举当前要填的数字 if (used[i]) continue; // 当前数字已经使用过了 if (!is_prime[i + path[k - 1]]) continue; // 当前数字和前一个数字的和不是素数 used[i] = true; path[k] = i; dfs(k + 1); used[i] = false; }}int main() { // 预处理素数表 memset(is_prime, true, sizeof(is_prime)); is_prime[0] = is_prime[1] = false; for (int i = 2; i < 50; i++) { if (is_prime[i]) { for (int j = i * i; j < 50; j += i) { is_prime[j] = false; } } } // 处理输入输出 int cnt = 0; while (scanf("%d", &n) != EOF) { if (cnt > 0) printf("\n"); // 多组数据之间的分隔符 cnt++; printf("Case %d:\n", cnt); memset(used, false, sizeof(used)); used[1] = true; // 素数环从1开始 path[0] = 1; dfs(1); } return 0;}P1357 食物链(一)
C++：
#include <iostream>#include <vector>#include <cstring>using namespace std;const int MAXN = 1005;int n, m;vector<int> graph[MAXN];bool vis[MAXN];int ans = 0;void dfs(int u, int depth) { ans = max(ans, depth); for (int i = 0; i < graph[u].size(); i++) { int v = graph[u][i]; if (!vis[v]) { vis[v] = true; dfs(v, depth+1); vis[v] = false; } }}int main() { while (cin >> n >> m) { memset(vis, false, sizeof(vis)); ans = 0; for (int i = 1; i <= n; i++) { graph[i].clear(); } for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; graph[u].push_back(v); } for (int i = 1; i <= n; i++) { vis[i] = true; dfs(i, 1); vis[i] = false; } cout << ans << endl; } return 0;}P1439 背包九讲(1)：简单的0-1背包
C++：
#include <iostream>#include <cstring>using namespace std;const int MAX_N = 30; // 物品最大数量const int MAX_V = 20000; // 箱子最大容量int n, V; // n表示物品数量，V表示箱子容量int w[MAX_N], v[MAX_N]; // w表示每个物品的价值，v表示每个物品的体积int dp[MAX_N + 1][MAX_V + 1]; // dp数组表示在前i个物品中，容量为j的情况下，能获得的最大价值int main(){ cin >> V >> n; for (int i = 0; i < n; ++i) { cin >> v[i] >> w[i]; } // 初始化第0行和第0列的值为0 memset(dp, 0, sizeof(dp)); // 计算dp数组 for (int i = 0; i < n; ++i) { for (int j = 0; j <= V; ++j) { if (j < v[i]) { dp[i + 1][j] = dp[i][j]; // 放不下，继承上一行的值 } else { dp[i + 1][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]); // 取较大值 } } } // 输出结果 cout << dp[n][V] << endl; return 0;}C：
#include <stdio.h>#include <string.h>#define MAX_N 30 // 物品最大数量#define MAX_V 20000 // 箱子最大容量int n, V; // n表示物品数量，V表示箱子容量int w[MAX_N], v[MAX_N]; // w表示每个物品的价值，v表示每个物品的体积int dp[MAX_N + 1][MAX_V + 1]; // dp数组表示在前i个物品中，容量为j的情况下，能获得的最大价值int max(int a, int b){ return a > b ? a : b;}int main(){ scanf("%d%d", &V, &n); for (int i = 0; i < n; ++i) { scanf("%d%d", &v[i], &w[i]); } // 初始化第0行和第0列的值为0 memset(dp, 0, sizeof(dp)); // 计算dp数组 for (int i = 0; i < n; ++i) { for (int j = 0; j <= V; ++j) { if (j < v[i]) { dp[i + 1][j] = dp[i][j]; // 放不下，继承上一行的值 } else { dp[i + 1][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]); // 取较大值 } } } // 输出结果 printf("%d\n", dp[n][V]); return 0;}P1475 智力大冲浪
C++：
#include <iostream>#include <cstring>using namespace std;const int MAX_N = 30; // 物品最大数量const int MAX_V = 20000; // 箱子最大容量int n, V; // n表示物品数量，V表示箱子容量int w[MAX_N], v[MAX_N]; // w表示每个物品的价值，v表示每个物品的体积int dp[MAX_N + 1][MAX_V + 1]; // dp数组表示在前i个物品中，容量为j的情况下，能获得的最大价值int max(int a, int b){ return a > b ? a : b;}int main(){ // 输入数据 cin >> V >> n; for (int i = 0; i < n; ++i) { cin >> v[i] >> w[i]; } // 初始化dp数组 memset(dp, 0, sizeof(dp)); // 计算dp数组 for (int i = 0; i < n; ++i) { for (int j = 0; j <= V; ++j) { if (j < v[i]) { // 如果当前物品体积大于当前剩余容量，则不能放入箱子中，继承上一行的结果 dp[i + 1][j] = dp[i][j]; } else { // 如果当前物品可以放入箱子中，则考虑将这个物品放入箱子中能带来多大的价值，取较大值 dp[i + 1][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]); } } } // 输出结果 cout << dp[n][V] << endl; return 0;}C：
#include <stdio.h>#include <string.h>#define MAX_N 30 // 物品最大数量#define MAX_V 20000 // 箱子最大容量int n, V; // n表示物品数量，V表示箱子容量int w[MAX_N], v[MAX_N]; // w表示每个物品的价值，v表示每个物品的体积int dp[MAX_N + 1][MAX_V + 1]; // dp数组表示在前i个物品中，容量为j的情况下，能获得的最大价值int max(int a, int b){ return a > b ? a : b;}int main(){ // 输入数据 scanf("%d%d", &V, &n); for (int i = 0; i < n; ++i) { scanf("%d%d", &v[i], &w[i]); } // 初始化dp数组 memset(dp, 0, sizeof(dp)); // 计算dp数组 for (int i = 0; i < n; ++i) { for (int j = 0; j <= V; ++j) { if (j < v[i]) { // 如果当前物品体积大于当前剩余容量，则不能放入箱子中，继承上一行的结果 dp[i + 1][j] = dp[i][j]; } else { // 如果当前物品可以放入箱子中，则考虑将这个物品放入箱子中能带来多大的价值，取较大值 dp[i + 1][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]); } } } // 输出结果 printf("%d\n", dp[n][V]); return 0;}P1476 加工生产调度
C++：
#include <iostream>#include <cstring>#include <queue>#include <vector>using namespace std;const int MAX_N = 1000;int n; // 产品的数量int time_a[MAX_N], time_b[MAX_N]; // time_a表示每个产品在A车间加工所需要的时间，time_b表示每个产品在B车间加工所需要的时间int in_degree[MAX_N]; // 记录每个产品的入度vector<int> edges[MAX_N]; // 采用邻接表存储图int main(){ while (cin >> n) { // 输入数据 for (int i = 0; i < n; ++i) { cin >> time_a[i]; } for (int i = 0; i < n; ++i) { cin >> time_b[i]; } // 初始化 memset(in_degree, 0, sizeof(in_degree)); for (int i = 0; i < n; ++i) { edges[i].clear(); } // 建立A车间到B车间的依赖关系 for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { if (time_a[i] + time_b[i] > time_a[j] + time_b[j]) { edges[j].push_back(i); ++in_degree[i]; } else { edges[i].push_back(j); ++in_degree[j]; } } } // 拓扑排序 int time = 0; queue<int> q; for (int i = 0; i < n; ++i) { if (in_degree[i] == 0) { q.push(i); } } while (!q.empty()) { int u = q.front(); q.pop(); time = max(time, time_a[u]); // 计算加工时间 for (int i = 0; i < edges[u].size(); ++i) { int v = edges[u][i]; --in_degree[v]; if (in_degree[v] == 0) { q.push(v); } } } time += time_b[n - 1]; // 加上最后一个产品在B车间加工的时间 // 输出结果 cout << time << endl; } return 0;}P1477 部分背包问题
C++：
#include <iostream>#include <algorithm>#include <cstring>using namespace std;const int MAX_N = 100;const int MAX_T = 1000;struct Item { int weight; // 金币的重量 int value; // 金币的价值 double unit_price; // 金币的单位价值 bool operator < (const Item& other) const { return unit_price > other.unit_price; }};Item items[MAX_N];int n, T; // n表示金币的数量，T表示背包的承重量int main(){ // 输入数据 cin >> n >> T; for (int i = 0; i < n; ++i) { cin >> items[i].weight >> items[i].value; items[i].unit_price = (double)items[i].value / items[i].weight; } // 按照单位价值从大到小排序 sort(items, items + n); // 计算最大价值 double ans = 0; for (int i = 0; i < n; ++i) { if (T >= items[i].weight) { // 如果可以将整个物品放入背包中 ans += items[i].value; T -= items[i].weight; } else { // 否则将物品拆分 ans += T * items[i].unit_price; break; } } // 输出结果 printf("%.2lf\n", ans); return 0;}B1631 [Usaco2007 Feb]Cow Party
C++：
#include <iostream>#include <cstring>#include <algorithm>#include <queue>using namespace std;const int MAX_N = 1003;const int MAX_M = 100003;const int INF = 0x3f3f3f3f;struct Edge { int v, w; // v表示边的终点，w表示边的长度 int next; // next表示下一个与起点相同的边的编号};Edge edges[MAX_M]; // 存储所有的边int head[MAX_N]; // head[i]表示起点为i的所有边中编号最小的那条边的编号int dist[MAX_N]; // dist[i]表示从终点到i的最短距离bool visited[MAX_N]; // visited[i]表示终点到i的最短路是否已经确定int n, m, x; // n表示点的数量，m表示边的数量，x表示终点的编号void addEdge(int u, int v, int w, int id){ edges[id].v = v; edges[id].w = w; edges[id].next = head[u]; head[u] = id;}void dijkstra(){ memset(dist, INF, sizeof(dist)); memset(visited, false, sizeof(visited)); dist[x] = 0; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; pq.push(make_pair(dist[x], x)); while (!pq.empty()) { int u = pq.top().second; pq.pop(); if (visited[u]) continue; visited[u] = true; for (int i = head[u]; i != -1; i = edges[i].next) { int v = edges[i].v; int w = edges[i].w; if (dist[v] > dist[u] + w) { dist[v] = dist[u] + w; pq.push(make_pair(dist[v], v)); } } }}int main(){ // 输入数据 cin >> n >> m >> x; memset(head, -1, sizeof(head)); for (int i = 0; i < m; ++i) { int u, v, w; cin >> u >> v >> w; addEdge(v, u, w, i); } // 计算最短路 dijkstra(); // 找到最大值 int ans = 0; for (int i = 1; i <= n; ++i) { if (dist[i] != INF) { for (int j = head[i]; j != -1; j = edges[j].next) { int v = edges[j].v; int w = edges[j].w; ans = max(ans, dist[i] + dist[v] + w); } } } // 输出结果 cout << ans << endl; return 0;}B3408 [Usaco2009 Oct]Heat Wave 热浪
C++：
#include <iostream>#include <vector>#include <queue>#include <cstring>using namespace std;const int N = 2510, M = 3 * 6200; // 根据题目要求设置节点数和边数的上限int h[N], e[M], w[M], ne[M], idx; // 邻接表存图，idx 表示当前边的编号int dist[N]; // 存储从起点到每个节点的最短距离bool st[N]; // 标记每个节点是否已经加入到 S 集合中int n, m, s, t;void add(int a, int b, int c) // 添加一条边 a -> b，边权为 c{ e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;}int dijkstra() // 返回从起点到终点的最短距离{ memset(dist, 0x3f, sizeof dist); // 初始化为无穷大 dist[s] = 0; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q; q.push({0, s}); while (q.size()) { auto t = q.top(); q.pop(); int ver = t.second, distance = t.first; if (st[ver]) continue; st[ver] = true; for (int i = h[ver]; i != -1; i = ne[i]) { int j = e[i]; if (dist[j] > distance + w[i]) { dist[j] = distance + w[i]; q.push({dist[j], j}); } } } if (dist[t] == 0x3f3f3f3f) return -1; return dist[t];}int main(){ memset(h, -1, sizeof h); cin >> n >> m >> s >> t; while (m -- ) { int a, b, c; cin >> a >> b >> c; add(a, b, c); add(b, a, c); // 无向图，所以要添加两条边 } cout << dijkstra() << endl; return 0;}B3445 [Usaco2014 Feb] Roadblock
C++：
P1635 月饼
C++：
#include <iostream>#include <vector>#include <algorithm>using namespace std;struct MoonCake { int t, b, h; // t为进食时间，b为过期时间，h为快乐值};int main() { int n, T; cin >> n >> T; vector<MoonCake> cakes(n); for (int i = 0; i < n; i++) { cin >> cakes[i].t >> cakes[i].b >> cakes[i].h; } // 将月饼按照过期时间从早到晚排序 sort(cakes.begin(), cakes.end(), [](const MoonCake& a, const MoonCake& b) { return a.b < b.b; }); // 动态规划，dp[i][j]表示考虑前i个月饼，限制时间为j时的最大快乐值 vector<vector<int>> dp(n + 1, vector<int>(T + 1)); for (int i = 1; i <= n; i++) { for (int j = 1; j <= T; j++) { // 先不选第i个月饼 dp[i][j] = dp[i - 1][j]; // 判断能否选第i个月饼，即限制时间是否大于等于月饼的过期时间 if (j >= cakes[i - 1].b) { // 选第i个月饼 dp[i][j] = max(dp[i][j], dp[i - 1][j - cakes[i - 1].t] + cakes[i - 1].h); } } } cout << dp[n][T] << endl; return 0;}P1648 炼丹术
C++：
#include <iostream>#include <vector>using namespace std;const int MOD = 998244353;int main() { int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; a[i]--; } // 计算出所有S(A)等于A的药材集合的数量 vector<int> dp(n + 1); dp[0] = 1; for (int i = 1; i <= n; i++) { // 计算f[i][j] for (int j = i - 1; j >= 0; j--) { dp[j + 1] = (dp[j] - dp[j + 1] + MOD) % MOD; } dp[0] = 1; // 统计所有f[n][k]的值之和 int ans = 0; for (int k = 1; k <= i; k++) { ans = (ans + 1LL * dp[k] * (n - k + 1) % MOD) % MOD; } cout << ans << endl; // 更新dp数组 for (int j = i; j >= 0; j--) { if (j > 0) { dp[j] = (dp[j] + dp[j - 1]) % MOD; } } } return 0;}P1719 Let's play a game!
C++：
#include <iostream>#include <vector>using namespace std;// 返回一个整数的二进制表示中，1的个数int count_bits(int x) { int res = 0; while (x > 0) { res += x & 1; x >>= 1; } return res;}int main() { int n, k; cin >> n >> k; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } // 计算所有元素为k的下标 vector<int> idx; for (int i = 0; i < n; i++) { if (a[i] == k) { idx.push_back(i); } } // 枚举所有可能的删除方案，求最小删除次数 int ans = n; for (int b = 0; b <= 30; b++) { int mask = (1 << b) - 1; for (int i = 0; i < idx.size(); i++) { // 如果i个数全部被删除，需要的操作次数 int cnt = count_bits((idx[i] >> b) ^ mask); // 判断是否满足所有元素均为k bool flag = true; for (int j = 0; j < idx.size(); j++) { if ((idx[i] >> b) != (idx[j] >> b)) { flag = false; break; } } if (flag) { ans = min(ans, cnt); } } } cout << ans << endl; return 0;}P1740 Ink on paper
C++：
#include <iostream>#include <vector>#include <queue>#include <cmath>using namespace std;const double INF = 1e20;// 计算两个点之间的距离double dist(double x1, double y1, double x2, double y2) { return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));}int main() { int T; cin >> T; while (T--) { int n; cin >> n; // 读入所有的点 vector<double> x(n), y(n); for (int i = 0; i < n; i++) { cin >> x[i] >> y[i]; } // 最短路径数组 vector<double> d(n, INF); // 最小堆，存储待处理的点 priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> pq; // 初始点为第一个点，距离为0 d[0] = 0; pq.push({0, 0}); while (!pq.empty()) { // 取出当前距离最小的点 auto [dist, u] = pq.top(); pq.pop(); // 如果这个点已经处理过了，直接跳过 if (dist > d[u]) { continue; } // 处理所有与当前点相邻的点 for (int v = 0; v < n; v++) { if (v == u) { continue; } double w = dist(x[u], y[u], x[v], y[v]) - 1.0; if (w < 0) { w = 0; } // 如果能够缩短到v点的距离，则更新 if (d[v] > d[u] + w) { d[v] = d[u] + w; pq.push({d[v], v}); } } } // 输出答案的平方 printf("%.0f\n", d[n-1] * d[n-1]); } return 0;}P1743 Audiophobia
C++：
#include <iostream>#include <cstdio>#include <cstring>#include <queue>using namespace std;const int N = 110;const int M = 1010;struct Edge { int next; // 下一条边的编号 int to; // 目标节点编号 int w; // 权值} edge[M << 1];int head[N], tot;int n, m, q;void add(int u, int v, int w) { // 添加一条边 edge[++tot].to = v; edge[tot].w = w; edge[tot].next = head[u]; head[u] = tot;}struct Node { int dis; // 距离 int id; // 节点编号 bool operator < (const Node &W) const { return dis > W.dis; }};bool vis[N];int dis[N];int dijkstra(int s, int t) { // s为起点，t为终点 priority_queue<Node> q; // 小根堆 memset(vis, false, sizeof(vis)); memset(dis, 0x3f, sizeof(dis)); dis[s] = 0; // 起点距离为0 q.push({0, s}); // 把起点加入队列 while (!q.empty()) { Node now = q.top(); q.pop(); int u = now.id; if (vis[u]) continue; // 已经访问过了 vis[u] = true; // 标记为已经访问 for (int i = head[u]; i; i = edge[i].next) { int v = edge[i].to; if (dis[v] > max(dis[u], edge[i].w)) { // 更新距离 dis[v] = max(dis[u], edge[i].w); q.push({dis[v], v}); // 把新节点加入队列 } } } if (dis[t] == 0x3f3f3f3f) return -1; // 没有路径 else return dis[t]; // 返回最短距离}int main() { int T = 0; // 样例编号 while (scanf("%d%d%d", &n, &m, &q) != EOF) { memset(head, 0, sizeof(head)); tot = 0; for (int i = 1; i <= m; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); add(u, v, w); add(v, u, w); // 无向图，要加两次 } printf("Case #%d\n", ++T); // 样例编号加1 while (q--) { int s, t; scanf("%d%d", &s, &t); int res = dijkstra(s, t); if (res == -1) puts("no path"); // 没有路径 else printf("%d\n", res); } } return 0;}P1747 单调不降序列中与x最接近元素
C++：
#include <iostream>#include <cstdio>#include <algorithm>using namespace std;const int N = 100010;int a[N];int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &a[i]); int m; scanf("%d", &m); while (m--) { int x; scanf("%d", &x); int l = 0, r = n - 1; while (l < r) { int mid = (l + r) >> 1; if (a[mid] >= x) r = mid; // 右半部分有可能更小 else l = mid + 1; // 左半部分肯定不符合要求 } if (l == 0) printf("%d\n", a[0]); // 特判 else if (l == n - 1) printf("%d\n", a[n - 1]); // 特判 else { if (a[l] - x <= x - a[l - 1]) printf("%d\n", a[l]); // 找到了更小的元素 else printf("%d\n", a[l - 1]); // 找到了更小的元素 } } return 0;}P1748 a+b+c+d==0
C++：
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <unordered_map>using namespace std;const int N = 2010;int a[N], b[N], c[N], d[N];int n;int main() { int T; scanf("%d", &T); while (T--) { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d%d%d%d", &a[i], &b[i], &c[i], &d[i]); unordered_map<int, int> mp; for (int i = 0; i < n; i++) { // 枚举a和b的组合 for (int j = 0; j < n; j++) { mp[a[i] + b[j]]++; } } int res = 0; for (int i = 0; i < n; i++) { // 枚举c和d的组合 for (int j = 0; j < n; j++) { int sum = c[i] + d[j]; if (mp.count(-sum)) res += mp[-sum]; // 找到了和为-sum的组合 } } printf("%d\n", res); } return 0;}P1750 求逆序对
C++：
#include <iostream>#include <cstdio>#include <cstring>using namespace std;typedef long long LL; // 要开long longconst int N = 500010;int a[N], tmp[N];LL res;void merge_sort(int l, int r) { if (l >= r) return; int mid = (l + r) >> 1; merge_sort(l, mid); merge_sort(mid + 1, r); int i = l, j = mid + 1, k = 0; while (i <= mid && j <= r) { // 统计逆序对的个数 if (a[i] <= a[j]) tmp[k++] = a[i++]; else { tmp[k++] = a[j++]; res += mid - i + 1; // 统计个数 } } while (i <= mid) tmp[k++] = a[i++]; while (j <= r) tmp[k++] = a[j++]; for (int i = l, j = 0; i <= r; i++, j++) a[i] = tmp[j];}int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &a[i]); merge_sort(0, n - 1); printf("%lld\n", res); return 0;}P1763 friendly group
C++：
#include <iostream>#include <cstdio>#include <cstring>#include <vector>using namespace std;const int N = 300010;int h[N], e[N], ne[N], idx; // 邻接表int color[N], cnt[2], f[N]; // cnt[0]和cnt[1]是染色后两种颜色的点数，f[i]表示以点i为根的子树中选或不选i的最大权值和vector<int> v; // 存放当前独立集中的点void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++;}bool dfs(int u, int c) { // 二分图染色 color[u] = c; cnt[c]++; for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; if (color[j] == -1) { if (!dfs(j, !c)) return false; } else if (color[j] == c) return false; } return true;}void dfs2(int u, int father) { // 计算f数组 int t = v.size(); for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; if (j == father) continue; dfs2(j, u); } if (!t) { // u是根节点，若选它，则其所有子节点都不能选 f[u] = cnt[1]; for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; f[u] = max(f[u], cnt[1] - f[j]); } } else { v.push_back(u); // 将u加入当前独立集 f[u] = cnt[color[u] == 0]; // 以u为根节点的子树中选或不选u的最大权值和 for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; if (j == father) continue; f[u] += f[j]; } v.pop_back(); // 将u移出当前独立集 f[u] = max(f[u], f[father]); // u不选，其子节点都可选 }}int main() { int T; scanf("%d", &T); for (int C = 1; C <= T; C++) { int n, m; scanf("%d%d", &n, &m); memset(h, -1, sizeof h); idx = 0; for (int i = 0; i < m; i++) { int a, b; scanf("%d%d", &a, &b); add(a, b); add(b, a); } memset(color, -1, sizeof color); bool flag = true; int ans = 0; for (int i = 1; i <= n; i++) { if (color[i] == -1) { cnt[0]P1779 小胡同学的跳板
C++：
#include <iostream>#include <vector>#include <algorithm>using namespace std;int main() { int n, m; cin >> n >> m; vector<pair<int, int>> boards(n); // 记录每个跳板的位置和能够发射的距离 for (int i = 0; i < n; i++) { cin >> boards[i].first >> boards[i].second; } sort(boards.begin(), boards.end()); // 按照跳板的位置从小到大排序 int farthest = 0; // 记录当前位置下能够到达的最远距离 int idx = 0; // 记录当前使用的跳板的下标 int steps = 0; // 记录走的总步数 while (farthest < m) { int max_distance = farthest; // 记录能够到达的最远距离 while (idx < n && boards[idx].first <= farthest) { // 遍历当前能够到达的跳板，找到其中能够发射最远距离的跳板 max_distance = max(max_distance, boards[idx].first + boards[idx].second); idx++; } if (max_distance == farthest) { // 无法继续前进，退出循环 break; } steps++; farthest = max_distance; } if (farthest < m) { // 无法到达炸鸡店，输出-1 cout << "-1" << endl; } else { cout << steps << endl; } return 0;}P1790 小胡同学的连通图
C++：
#include <iostream>#include <vector>#include <queue>using namespace std;int main() { int n, m; cin >> n >> m; // 使用邻接表表示图 vector<vector<int>> graph(n + 1); for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; graph[u].push_back(v); graph[v].push_back(u); } vector<bool> visited(n + 1, false); // 标记节点是否被访问过 queue<int> q; // 队列用于BFS遍历 q.push(1); visited[1] = true; while (!q.empty()) { int u = q.front(); q.pop(); for (int v : graph[u]) { if (!visited[v]) { q.push(v); visited[v] = true; } } } for (int i = 1; i <= n; i++) { if (!visited[i]) { // 存在未被访问到的节点，说明不是连通图 cout << "No" << endl; return 0; } } cout << "Yes" << endl; return 0;}P1793 求解迷宫问题
C++：
#include <iostream>#include <vector>using namespace std;const int N = 8; // 迷宫的大小vector<vector<char>> maze(N, vector<char>(N)); // 保存迷宫的二维数组vector<vector<int>> path(N, vector<int>(N, 0)); // 保存路径的二维数组，0表示未访问过，1表示已访问过bool found = false; // 是否已经找到一条路径void dfs(int x, int y) { if (x < 0 || x >= N || y < 0 || y >= N) { // 当前位置越界 return; } if (maze[x][y] == 'X' || path[x][y] == 1) { // 当前位置是障碍，或者已经被访问过 return; } if (x == N - 1 && y == N - 1) { // 已经到达出口 found = true; path[x][y] = 1; return; } // 标记当前位置已经被访问 path[x][y] = 1; dfs(x - 1, y); // 左 if (found) { // 已经找到一条路径，返回 return; } dfs(x, y + 1); // 上 if (found) { // 已经找到一条路径，返回 return; } dfs(x + 1, y); // 右 if (found) { // 已经找到一条路径，返回 return; } dfs(x, y - 1); // 下 if (found) { // 已经找到一条路径，返回 return; } // 回溯，将当前位置标记为未访问 path[x][y] = 0;}int main() { // 读入迷宫 for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { cin >> maze[i][j]; } } dfs(0, 0); // 从入口开始DFS遍历 // 输出路径 for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (path[i][j] == 1) { cout << "O"; } else { cout << " "; } } cout << endl; } return 0;}P1794 求解好多鱼问题
C++：
#include <iostream>#include <vector>#include <cmath>using namespace std;int main() { int minSize, maxSize, n; cin >> minSize >> maxSize >> n; vector<int> fishSize(n); for (int i = 0; i < n; i++) { cin >> fishSize[i]; } int count = 0; for (int i = minSize; i <= maxSize; i++) { bool safe = true; for (int j = 0; j < n; j++) { if ((i >= fishSize[j] * 2 && i <= fishSize[j] * 100) || (fishSize[j] >= i * 2 && fishSize[j] <= i * 100)) { // i能吃掉fishSize[j]，或者fishSize[j]能吃掉i，i不安全 safe = false; break; } } if (safe) { count++; } } cout << count << endl; return 0;}P1795 求解图的 m 着色问题
C++：
#include <iostream>#include <vector>using namespace std;int n, k, m;vector<vector<int>> graph; // 无向连通图vector<int> color; // 各顶点的颜色int count = 0; // 符合要求的着色方案数// 检查某个顶点的着色是否合法bool check(int v, int c) { for (int i = 0; i < graph[v].size(); i++) { int neighbor = graph[v][i]; if (color[neighbor] == c) { return false; } } return true;}// 递归枚举所有着色方案void dfs(int v) { if (v == n) { // 所有顶点都已着色，该方案符合要求 count++; return; } // 尝试所有可能的颜色 for (int c = 1; c <= m; c++) { if (check(v, c)) { // 该颜色能用于该顶点，继续递归下一个顶点 color[v] = c; dfs(v + 1); color[v] = 0; // 回溯 } }}int main() { cin >> n >> k >> m; // 初始化图 graph.resize(n); for (int i = 0; i < k; i++) { int u, v; cin >> u >> v; u--; v--; graph[u].push_back(v); graph[v].push_back(u); } // 初始化顶点颜色 color.resize(n); // 从第一个顶点开始递归枚举所有着色方案 dfs(0); cout << count << endl; return 0;}P1801 二叉排序树
C++：
#include <iostream>using namespace std;// 二叉树节点struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}};// 插入节点void insert(TreeNode* root, int val) { if (root->val == val) return; // 值已存在，无需插入 if (val < root->val) { if (root->left == nullptr) { root->left = new TreeNode(val); } else { insert(root->left, val); } } else { if (root->right == nullptr) { root->right = new TreeNode(val); } else { insert(root->right, val); } }}// 查询节点int search(TreeNode* root, int val, string& path) { if (root == nullptr) return 0; // 值不存在 if (val == root->val) return 1; // 值存在 if (val < root->val) { path += "<-"; return search(root->left, val, path) + 1; // 继续在左子树查找 } else { path += "->"; return search(root->right, val, path) + 1; // 继续在右子树查找 }}int main() { int n; cin >> n; TreeNode* root = nullptr; for (int i = 0; i < n; i++) { int opt, x; cin >> opt >> x; string path = ""; if (opt == 1) { if (root == nullptr) { root = new TreeNode(x); } else { insert(root, x); } } else { int count = search(root, x, path) - 1; cout << path << endl << count << endl; } } return 0;}P1809 wzy的跑步
C++：
#include <iostream>#include <vector>#include <algorithm>using namespace std;int main() { int n, m, k; cin >> n >> m >> k; vector<int> puddles(m); for (int i = 0; i < m; i++) { cin >> puddles[i]; } sort(puddles.begin(), puddles.end()); // 按照位置排序 int pos = 1, ans = 0; while (pos < n) { int nextPos = pos + k; while (nextPos >= pos) { // 在范围 [pos+1, pos+k] 内找到最后一个没有水坑的位置 auto it = lower_bound(puddles.begin(), puddles.end(), nextPos); if (it == puddles.begin()) { break; } it--; if (*it < pos) { break; } nextPos = *it + k; } if (nextPos == pos) { // 无法前进 cout << "-1" << endl; return 0; } ans += 1; pos = nextPos; } cout << ans << endl; return 0;}P1825 东方香霖堂
C++：
#include <iostream>#include <algorithm>using namespace std;int main() { int n, k; cin >> n >> k; int a[n]; for (int i = 0; i < n; i++) { cin >> a[i]; } sort(a, a + n); int cnt = 0; for (int i = 0; i < n; i++) { if (a[i] <= k) { cnt += 1; k -= a[i]; } else { break; } } cout << cnt << endl; return 0;}P1826 荷取的基站布局
C++：
#include <iostream>#include <cstring>using namespace std;const int N = 15, MOD = 1e9 + 7;int n;bool placed[N][N]; // 标记第 i 行第 j 列是否已放置基站int ans = 0;void dfs(int x, int y, int k) { if (y == n) { // 换行 y = 0; x += 1; } if (x == n) { // 达到最后一个方格 if (k == n) { // 找到一个合法布局方案 ans = (ans + 1) % MOD; } return; } bool canPlace = true; // 判断当前方格能否放置基站 if (placed[x][y]) { // 当前方格已经放置了基站 canPlace = false; } if (x > 0 && placed[x - 1][y]) { // 上面的方格已经放置了基站 canPlace = false; } if (y > 0 && placed[x][y - 1]) { // 左边的方格已经放置了基站 canPlace = false; } if (canPlace) { // 可以放置基站 placed[x][y] = true; dfs(x, y + 1, k + 1); placed[x][y] = false; } dfs(x, y + 1, k); // 不放置基站}int main() { cin >> n; dfs(0, 0, 0); cout << ans << endl; return 0;}P1837 切出最好吃的蛋糕
C++：
#include <iostream>#include <cstring>using namespace std;const int N = 110;int n;int s[N][N]; // 二维前缀和数组int main() { cin >> n; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { int x; cin >> x; s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + x; } } int ans = -1e9; for (int i = 1; i <= n; i++) { // 枚举矩形左上角的位置 for (int j = 1; j <= n; j++) { for (int k = i; k <= n; k++) { // 枚举矩形右下角的位置 for (int l = j; l <= n; l++) { int sum = s[k][l] - s[k][j - 1] - s[i - 1][l] + s[i - 1][j - 1]; // 子矩形的和 ans = max(ans, sum); // 更新最大值 } } } } cout << ans << endl; return 0;}P1849 乌龟棋
C++：
#include <iostream>#include <vector>#include <algorithm>#include <unordered_set>using namespace std;int main(){ int n, m; cin >> n >> m; // 读入格子的分数 vector<int> scores(n); for (int i = 0; i < n; ++i) { cin >> scores[i]; } // 读入卡片 vector<int> cards(m); for (int i = 0; i < m; ++i) { cin >> cards[i]; } // 将卡片按数字从大到小排序 sort(cards.rbegin(), cards.rend()); // 已使用的卡片 unordered_set<int> used_cards; // 可用的卡片 vector<int> available_cards; // 初始化可用的卡片列表 for (int i = 0; i < m; ++i) { available_cards.push_back(cards[i]); } // 从起点开始 int position = 0; int total_score = scores[0]; // 当还没到达终点时 while (position < n - 1) { // 找到可以使用的最大卡片 int max_card = -1; for (int i = 0; i < available_cards.size(); ++i) { if (used_cards.count(available_cards[i]) == 0) { max_card = available_cards[i]; break; } } // 使用最大卡片 used_cards.insert(max_card); available_cards.erase(find(available_cards.begin(), available_cards.end(), max_card)); position += max_card; total_score += scores[position]; } cout << total_score << endl; return 0;}P1851 成熟的数列
C++：
#include <iostream>#include <unordered_map>#include <vector>using namespace std;int main(){ int x, y, z; cin >> x >> y >> z; // 计算数列 vector<int> sequence(z + 1); sequence[0] = x; sequence[1] = y; unordered_map<int, int> seen; seen[x] = 0; seen[y] = 1; int cycle_length = -1; int cycle_start = -1; for (int i = 2; i <= z; ++i) { int a = sequence[i - 2]; int b = sequence[i - 1]; int c = a + sequence[(i / 2) + (i / 4)]; sequence[i] = c; if (seen.count(c) != 0) { cycle_length = i - seen[c]; cycle_start = seen[c]; break; } seen[c] = i; } // 处理查询 int n; cin >> n; int max_seen = -1; unordered_map<int, int> recent; for (int i = 0; i < n; ++i) { int s; cin >> s; // 如果数列已经超过了查询数，查询数不在数列中 if (z >= s) { if (seen.count(s) != 0) { cout << seen[s] << endl; continue; } if (cycle_length != -1 && s > sequence[cycle_start + cycle_length - 1]) { cout << -1 << endl; continue; } } // 如果查询数在数列之外，计算数列的一部分 int start = max(max_seen, 0); int end = min(s, z); for (int j = start; j <= end; ++j) { int a = sequence[j]; recent[a] = j; } max_seen = max(max_seen, end); // 检查查询数是否在计算出的数列中 if (recent.count(s) != 0) { cout << recent[s] << endl; } else { cout << -1 << endl; } } return 0;}P1852 舰长的礼物
C++：
#include <iostream>#include <vector>#include <algorithm>#include <numeric>using namespace std;const double EPS = 1e-8;int main(){ int n, k; cin >> n >> k; // 读入护心毛长度并求出平均值 vector<double> L(n); double sum_L = 0; for (int i = 0; i < n; ++i) { cin >> L[i]; sum_L += L[i]; } double avg = sum_L / k; // 二分查找最大长度 double left = 0, right = avg; double ans = -1; while (right - left >= EPS) { double mid = (left + right) / 2; int cnt = accumulate(L.begin(), L.end(), 0, [&](int s, double l) { return s + static_cast<int>(l / mid); }); if (cnt >= k) { ans = mid; left = mid; } else { right = mid; } } // 输出答案 if (ans != -1) { printf("%.2f\n", ans); } else { cout << 0 << endl; } return 0;}P1853 守望者的逃离
C++：
#include <iostream>#include <cmath>using namespace std;int main(){ int n, s, m, t; cin >> n >> s >> m >> t; // 若无法直接到达终点则先回到起点 if (n * 60 + s > 17 * t) { n = 0; s = 0; } int time = 0; while (time < t) { // 1. 尽量使用闪现 if (m >= 10 && s + 60 <= n * 60 + s && s + 60 <= 17 * t) { s += 60; m -= 10; } else { // 2. 如果无法使用闪现且距离终点超过当前时间能走的最远距离，则加速跑步 int max_dist = min(17 * (t - time), n * 60 + s + 17 * (t - time)); if (s + 1 < max_dist) { s += 1; } // 3. 否则只能原地休息 else if (m + 4 <= 1000) { m += 4; } } // 更新时间 ++time; } // 输出结果 if (n * 60 + s >= 17 * t) { cout << "Yes" << endl << time << endl; } else { cout << "No" << endl << n * 60 + s << endl; } return 0;}P1855 接水问题
C++：
#include<bits/stdc++.h>using namespace std;const int MAXN=1e4+5;int n,m,ans=0;int cnt[MAXN];//每个同学还需要接水的量queue<int> q[MAXN];//队列模拟每个龙头接水情况int main(){ cin>>n>>m; for(int i=1;i<=n;++i) { int w; cin>>w; cnt[i]=w; q[i%m].push(i); } while(1) { bool flag=1;//标记是否全部同学都接完水了 for(int i=0;i<m;++i)//遍历每个龙头 { if(q[i].empty()) continue;//如果该龙头上没有同学了 int cur=q[i].front(); flag=0; --cnt[cur]; q[i].pop(); if(cnt[cur]==0)//如果该同学接完水了 { if(q[(i+1)%m].empty())//下一个龙头空着，直接接上 q[(i+1)%m].push(cur); else//否则，入队等待 { q[(i+2)%m].push(cur); i++; } } } if(flag) break;//如果全部同学都接完水了，退出循环 ++ans;//每一秒都要加1 } cout<<ans<<endl; return 0;}P1857 孤独摇滚
C++：波门
P1859 单词接龙
C++：
#include<bits/stdc++.h>using namespace std;int n;string s[25];char c;bool vis[25];int dfs(int u,string str)//深搜{ int res=str.size(); for(int i=1;i<=n;++i) { if(vis[i]) continue;//i已经被访问过了，跳过 vis[i]=1;//标记i为已访问 for(int j=1;j<s[i].size();++j)//枚举i的所有后缀 { string suffix=s[i].substr(j); if(suffix==str)//如果u和i可以拼接在一起 { res=max(res,dfs(i,s[i])+str.size());//更新答案 break; } } vis[i]=0;//回溯 } return res;}int main(){ cin>>n; for(int i=1;i<=n;++i) cin>>s[i]; cin>>c; int ans=0; for(int i=1;i<=n;++i) { if(s[i][0]==c)//如果s[i]以c开头 { vis[i]=1;//标记i为已访问 ans=max(ans,dfs(i,s[i]));//更新答案 vis[i]=0;//回溯 } } cout<<ans<<endl; return 0;}