如有WA全是多组输入问题，请自行修改，或在评论区向我反馈，我会及时修改，如有注释不够详细等问题，也可联系我进行修改：
P1138 American Heritage
C++：
#include #include 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 <> inorder >> preorder; // 输入中序遍历和前序遍历postorder(0, inorder.size() - 1, 0, preorder.size() - 1); // 构造二叉树并输出后序遍历cout << endl;return 0;}C：
#include #include #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 #include using namespace std;const int N = 8;vector 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 > x;if (x == 1) { // 已经有皇后了pos[cnt++] = j; // 记录位置}}}backtrack(cnt); // 从第 cnt 行开始回溯cout << res << endl; // 输出摆法的种类数return 0;}C：
#include #include #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 #include #include 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数组为0for (int i = 1; i <= m; i++) {for (int j = 1; j > 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 #include #include #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数组为0for (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 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 #include using namespace std;const int N = 10010;int a[N], f[N];int main() {int n;cin >> n;for (int i = 1; i > 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 #include #include #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 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 #include 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 > 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 #include #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 #include #include using namespace std;const int MAXN = 20;int n;vector 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 > n) {if (cnt > 0) cout << endl; // 多组数据之间的分隔符cnt++;cout << "Case " << cnt << ":" << endl;path.clear(); // 清空存储当前素数环的vectormemset(used, false, sizeof(used));used[1] = true; // 素数环从1开始path.push_back(1);dfs(1);}return 0;}C:
#include #include #include #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 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 #include #include using namespace std;const int MAXN = 1005;int n, m;vector graph[MAXN];bool vis[MAXN];int ans = 0;void dfs(int u, int depth) {ans = max(ans, depth);for (int i = 0; i > n >> m) {memset(vis, false, sizeof(vis));ans = 0;for (int i = 1; i <= n; i++) {graph[i].clear();}for (int i = 0; i > 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 #include 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 > v[i] >> w[i];}// 初始化第0行和第0列的值为0memset(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 #include #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列的值为0memset(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 #include 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 > 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 #include #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 #include #include #include 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 edges[MAX_N]; // 采用邻接表存储图int main(){while (cin >> n) {// 输入数据for (int i = 0; i > time_a[i];}for (int i = 0; i > 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 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 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 #include #include using namespace std;const int MAX_N = 100;const int MAX_T = 1000;struct Item {int weight; // 金币的重量int value;// 金币的价值double unit_price;// 金币的单位价值bool operator other.unit_price;}};Item items[MAX_N];int n, T; // n表示金币的数量，T表示背包的承重量int main(){// 输入数据cin >> n >> T;for (int i = 0; i > 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 = 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 #include #include #include 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, vector<pair>, greater<pair>> 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 > 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 #include #include #include 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, vector<pair>, greater<pair>> 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 #include #include using namespace std;struct MoonCake {int t, b, h;// t为进食时间，b为过期时间，h为快乐值};int main() {int n, T;cin >> n >> T;vector cakes(n);for (int i = 0; i > 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> dp(n + 1, vector(T + 1));for (int i = 1; i <= n; i++) {for (int j = 1; 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 #include using namespace std;const int MOD = 998244353;int main() {int n;cin >> n;vector a(n);for (int i = 0; i > a[i];a[i]--;}// 计算出所有S(A)等于A的药材集合的数量vector dp(n + 1);dp[0] = 1;for (int i = 1; i = 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 <= 0; j--) {if (j > 0) {dp[j] = (dp[j] + dp[j - 1]) % MOD;}}}return 0;}P1719 Let’s play a game!
C++：
#include #include 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 a(n);for (int i = 0; i > a[i];}// 计算所有元素为k的下标vector 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 > b) ^ mask);// 判断是否满足所有元素均为kbool flag = true;for (int j = 0; j > b) != (idx[j] >> b)) {flag = false;break;}}if (flag) {ans = min(ans, cnt);}}}cout << ans << endl;return 0;}P1740 Ink on paper
C++：
#include #include #include #include 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 x(n), y(n);for (int i = 0; i > x[i] >> y[i];}// 最短路径数组vector d(n, INF);// 最小堆，存储待处理的点priority_queue<pair, vector<pair>, greater<pair>> pq;// 初始点为第一个点，距离为0d[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 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 #include #include #include 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 W.dis;}};bool vis[N];int dis[N];int dijkstra(int s, int t) { // s为起点，t为终点priority_queue q; // 小根堆memset(vis, false, sizeof(vis));memset(dis, 0x3f, sizeof(dis));dis[s] = 0; // 起点距离为0q.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); // 样例编号加1while (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 #include #include 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 > 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 #include #include #include #include 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 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 #include #include 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 #include #include #include 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 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 #include #include using namespace std;int main() {int n, m;cin >> n >> m;vector<pair> boards(n); // 记录每个跳板的位置和能够发射的距离for (int i = 0; i > 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) {// 无法到达炸鸡店，输出-1cout << "-1" << endl;} else {cout << steps << endl;}return 0;}P1790 小胡同学的连通图
C++：
#include #include #include using namespace std;int main() {int n, m;cin >> n >> m;// 使用邻接表表示图vector<vector> graph(n + 1);for (int i = 0; i > u >> v;graph[u].push_back(v);graph[v].push_back(u);}vector visited(n + 1, false); // 标记节点是否被访问过queue 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 #include using namespace std;const int N = 8; // 迷宫的大小vector<vector> maze(N, vector(N)); // 保存迷宫的二维数组vector<vector> path(N, vector(N, 0)); // 保存路径的二维数组，0表示未访问过，1表示已访问过bool found = false; // 是否已经找到一条路径void dfs(int x, int y) {if (x = N || 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 > 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 #include #include using namespace std;int main() {int minSize, maxSize, n;cin >> minSize >> maxSize >> n;vector fishSize(n);for (int i = 0; i > fishSize[i];}int count = 0;for (int i = minSize; i <= maxSize; i++) {bool safe = true;for (int j = 0; j = fishSize[j] * 2 && i = 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 #include using namespace std;int n, k, m;vector<vector> graph;// 无向连通图vector 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 > n >> k >> m;// 初始化图graph.resize(n);for (int i = 0; i > 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 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 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 val) {path += "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 > 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 #include #include using namespace std;int main() {int n, m, k;cin >> n >> m >> k;vector puddles(m);for (int i = 0; i > puddles[i];}sort(puddles.begin(), puddles.end());// 按照位置排序int pos = 1, ans = 0;while (pos = 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 #include using namespace std;int main() {int n, k;cin >> n >> k;int a[n];for (int i = 0; i > 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 #include 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 #include 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 > 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 #include #include #include using namespace std;int main(){int n, m;cin >> n >> m;// 读入格子的分数vector scores(n);for (int i = 0; i > scores[i];}// 读入卡片vector cards(m);for (int i = 0; i > cards[i];}// 将卡片按数字从大到小排序sort(cards.rbegin(), cards.rend());// 已使用的卡片unordered_set used_cards;// 可用的卡片vector 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 #include #include using namespace std;int main(){int x, y, z;cin >> x >> y >> z;// 计算数列vector sequence(z + 1);sequence[0] = x;sequence[1] = y;unordered_map seen;seen[x] = 0;seen[y] = 1;int cycle_length = -1;int cycle_start = -1;for (int i = 2; i > n;int max_seen = -1;unordered_map recent;for (int i = 0; i > s;// 如果数列已经超过了查询数，查询数不在数列中if (z >= s) {if (seen.count(s) != 0) {cout << seen[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 #include #include #include using namespace std;const double EPS = 1e-8;int main(){int n, k;cin >> n >> k;// 读入护心毛长度并求出平均值vector L(n);double sum_L = 0;for (int i = 0; i > 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(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 #include 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 = 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 = 17 * t) {cout << "Yes" << endl << time << endl;} else {cout << "No" << endl << n * 60 + s << endl;}return 0;}P1855 接水问题
C++：
#includeusing namespace std;const int MAXN=1e4+5;int n,m,ans=0;int cnt[MAXN];//每个同学还需要接水的量queue q[MAXN];//队列模拟每个龙头接水情况int main(){cin>>n>>m;for(int i=1;i>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<P1857 孤独摇滚
C++：波门
P1859 单词接龙
C++：
#includeusing 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>n;for(int i=1;i>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<