贪心的奶牛
题目描述
xlow有一群奶牛，一共m头，要带它们去牧场放牧。
牧场上有一排距离不等的木桩，共有n个，n>=m。
现在xlow需要把奶牛都拴在木桩上，一头奶牛一桩，让奶牛在木桩周围吃草。
不过，xlow的奶牛和普通的奶牛也很不一样，它们很聪明，并且很贪心，
还不喜欢看到别的奶牛比自己多占便宜。
为了能每头奶牛都能吃到一样多的草，拴奶牛的绳子都必须一样的长。
xlow也知道它们的贪心，所以也想办法尽可能满足它们，
希望绳子能尽可能地长。但同时，不能让同一地方的草，
能同时被两只以上的奶牛吃到，这样它们会打架抢地盘的，
并且那样就会不公平了，就会有奶牛吃的比其它的奶牛要少。
输入描述
第一行依次有两个整数n,k，其中2<=k<=n<=10000，
接下来一行有n个整数，代表木桩的位置，范围从-1e9到+1e9
输出描述
输出距离最近的两只奶牛之间的最大距离
示例 1
输入：
5 3 2 5 1 10 7输出：
4#include <bits/stdc++.h> using namespace std; int n, k; vector<int> pos; bool check(int d) { int cnt = 1; int last = pos[0]; for (int i = 1; i < n; i++) { if (pos[i] - last >= d) { cnt++; last = pos[i]; if (cnt >= k) return 1; } } return cnt >= k; } int main() { cin >> n >> k; pos.resize(n); for (int i = 0; i < n; i++) cin >> pos[i]; sort(pos.begin(), pos.end()); int lo = 0; int hi = pos.back() - pos[0]; while (lo < hi) { int mid = lo + (hi - lo + 1) / 2; if (check(mid)) { lo = mid; } else hi = mid - 1; } cout << lo << endl; }求最小生成树(Prim算法）
题目描述
给定一个无向带权图，图中的顶点为字符型，权值为不超过 100 的整数。在编辑器中已经给出了部分代码，请使用 Prim 算法求出该图的最小生成树。
输入格式
第一行为一个整数n，表示图中顶点的个数。
第二行为一个整数e，表示边的条数。
第三行为一个长度为n的字符串，表示所有顶点（仅包含大写字母）。
接下来e行，每行包含一个字符（顶点）、另一个字符（顶点）以及一个整数（边权），表示一条无向边及其权值。
输出格式
按 Prim 算法求得的顺序输出最小生成树中的边，每条边用形如(U,V)的格式表示，边与边之间无空格。
示例 1
输入：
6 10 ABCDEF A B 6 A C 1 A D 5 B C 5 C D 5 B E 3 E C 6 C F 4 F D 2 E F 6输出：
(A,C)(C,F)(F,D)(C,B)(B,E)#include <bits/stdc++.h> using namespace std; int main() { int n, e; cin >> n >> e; string s; cin >> s; // 记录每个顶点对应的编号 unordered_map<char, int> id; for (int i = 0; i < n; i++) id[s[i]] = i; // 用邻接矩阵存图，初始化为一个大数（表示无穷大） const int INF = 1e9; vector<vector<int>> g(n, vector<int>(n, INF)); for (int i = 0; i < e; i++) { char u, v; int w; cin >> u >> v >> w; int ui = id[u], vi = id[v]; g[ui][vi] = g[vi][ui] = min(g[ui][vi], w); // 防止重边取最小 } // 以下为 Prim 算法 vector<bool> vis(n, false); // 标记顶点是否已加入生成树 vector<int> minDist(n, INF); // 记录每个顶点到当前生成树的最短距离 vector<int> parent(n, -1); // 记录生成树中每个顶点的父节点（用于输出边） // 从顶点 0 开始（即 s[0] 对应的顶点） vis[0] = true; minDist[0] = 0; // 初始化 minDist：把从 0 出发的边距离填进去 for (int v = 0; v < n; v++) { if (g[0][v] < INF) { minDist[v] = g[0][v]; parent[v] = 0; } } cout << " "; // 开头一个空格，与原格式一致 for (int cnt = 1; cnt < n; cnt++) { // 1. 在未访问的顶点中，找距离当前生成树最近的点 u int u = -1; int best = INF; for (int i = 0; i < n; i++) { if (!vis[i] && minDist[i] < best) { best = minDist[i]; u = i; } } // 2. 将 u 加入生成树 vis[u] = true; // 输出这条边 (父节点, u) cout << "(" << s[parent[u]] << "," << s[u] << ")"; // 3. 更新其他未访问顶点到生成树的最短距离 for (int v = 0; v < n; v++) { if (!vis[v] && g[u][v] < minDist[v]) { minDist[v] = g[u][v]; parent[v] = u; } } } cout << endl; return 0; }哈夫曼编码
题目描述
根据给定的叶结点字符及其对应的权值，进行哈夫曼编码。
输入描述
第一行为叶子结点的数目n(1<=n<=100)。第二行为一个字符串，包含n个字符，每个字符对应一个叶子结点，第三行为每个叶子结点的概率（即权值），要求根据各叶结点构造哈夫曼值，并进行哈夫曼编码。构造哈夫曼树的原则是选两个权值最小的，构造一个父结点，其中最小的结点为左孩子，次小的为右孩子，如果选中的两个结点权值相等，则取排在前一个位置的为左孩子。编码原则是左孩子为0，右孩子为1。
输出描述
根据字符出现的次序，每个字符用一行输出其哈夫曼编码。
示例 1
输入：
8 abcdefgh 5 29 7 8 14 23 3 11输出：
0001 10 1110 1111 110 01 0000 001#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; string chars; cin >> chars; vector<int> w(n); for (int i = 0; i < n; i++) cin >> w[i]; // 每个组：权值、包含的原始字符索引、这些字符当前的编码（初始为空） vector<int> weight = w; vector<vector<int>> groups(n); // groups[i] 存储该组包含的字符索引 vector<string> code(n); // 每个字符的最终编码（动态更新） for (int i = 0; i < n; i++) groups[i] = {i}; // 当还有多于 1 个组时，合并 while (groups.size() > 1) { // 1. 找权值最小的两个组的下标 int min1 = 0, min2 = 1; if (weight[min1] > weight[min2]) swap(min1, min2); for (size_t i = 2; i < weight.size(); i++) { if (weight[i] < weight[min1]) { min2 = min1; min1 = i; } else if (weight[i] < weight[min2]) { min2 = i; } } // 2. 合并：新组权值 = 两权值和，字符列表合并 int newWeight = weight[min1] + weight[min2]; vector<int> newGroup = groups[min1]; newGroup.insert(newGroup.end(), groups[min2].begin(), groups[min2].end()); // 3. 更新编码：给第一个组的所有字符加 "0"，第二个组加 "1" for (int idx : groups[min1]) code[idx] = "0" + code[idx]; for (int idx : groups[min2]) code[idx] = "1" + code[idx]; // 4. 删除原来的两个组，加入新组 // 为了让删除方便，把要保留的组挪到前面，然后 pop_back if (min1 > min2) swap(min1, min2); groups.erase(groups.begin() + min2); groups.erase(groups.begin() + min1); weight.erase(weight.begin() + min2); weight.erase(weight.begin() + min1); groups.push_back(newGroup); weight.push_back(newWeight); } // 按原始顺序输出每个字符的编码 for (int i = 0; i < n; i++) { cout << code[i] << endl; } return 0; }Task Scheduling
题目描述
一个单位时间任务是恰好需要一个单位时间完成的任务。给定一个单位时间任务的有限集S。关于S 的一个时间表用于描述S 中单位时间任务的执行次序。时间表中第1 个任务从时间0 开始执行直至时间1 结束，第2 个任务从时间1 开始执行至时间2 结束，…，第n个任务从时间n-1 开始执行直至时间n结束。
具有截止时间和误时惩罚的单位时间任务时间表问题可描述如下：
(1) n 个单位时间任务的集合S={1,2,…,n}；
(2) 任务i的截止时间 di ,1≤i≤n,1≤ di ≤n，即要求任务i 在时间di 之前结束；
(3) 任务i 的误时惩罚 wi ,1≤i≤n,即任务i 未在时间 di 之前结束将招致 wi 的惩罚；
若按时完成则无惩罚。
任务时间表问题要求确定S 的一个时间表（最优时间表）使得总误时惩罚达到最小。
输入描述
第一行是正整数n，表示任务数。接下来的2行中，每行有n个正整数，分别表示各任务的截止时间和误时惩罚。
输出描述
最小总误时惩罚。
示例 1
输入：
7 4 2 4 3 1 4 6 70 60 50 40 30 20 10输出：
50#include <bits/stdc++.h> using namespace std; struct Task { int deadline, penalty; }; bool cmp(Task a, Task b) { return a.penalty > b.penalty; } int main() { int n; cin >> n; vector<Task> tasks(n); for (int i = 0; i < n; ++i) cin >> tasks[i].deadline; for (int i = 0; i < n; ++i) cin >> tasks[i].penalty; sort(tasks.begin(), tasks.end(), cmp); vector<int> slot(n + 1, 0); // 0表示空闲，1表示占用 int totalPenalty = 0; for (auto &t : tasks) { int pos = t.deadline; while (pos > 0 && slot[pos] == 1) { --pos; } if (pos > 0) { slot[pos] = 1; // 安排在此时间点 } else { totalPenalty += t.penalty; } } cout << totalPenalty << endl; return 0; }小偷跑了
题目描述
近期东六宿舍楼小偷很聪明，他们总是能寻找到偷窃后逃跑的路线，为了抓到他们，我们需要知道他们逃跑的路线，请你帮忙找出他们逃跑的路线（为简单化问题，我们保证最多只有一条逃跑路径，且起点为( 0 , 0 )，终点( 4 , 4)为，不能斜线逃跑,若终点有人拦截，也为逃跑失败）。
输入描述
一个5*5矩阵，用空格隔开
0表示可行走路径，1表示障碍，逃跑起点为左上，终点为右下
输出描述
逃跑线路，见输出示例(请注意x，y轴方向)如果没有路可以逃,则输出: "No Way!"(不含冒号和引号)
示例 1
输入：
0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 0 0 0 0输出：
(0,0) (0,1) (0,2) (0,3) (0,4) (1,4) (2,4) (3,4) (4,4)#include <bits/stdc++.h> using namespace std; // 定义方向数组：上下左右 const int dx[4] = {1, -1, 0, 0}; const int dy[4] = {0, 0, 1, -1}; int maze[5][5]; // 存储迷宫 bool vis[5][5]; // 标记是否访问过 pair<int, int> pre[5][5]; // 记录每个点的前一个点（用于路径回溯） // 检查坐标是否合法且可走 bool isValid(int x, int y) { return x >= 0 && x < 5 && y >= 0 && y < 5 && maze[x][y] == 0 && !vis[x][y]; } void bfs() { queue<pair<int, int>> q; q.push({0, 0}); vis[0][0] = true; pre[0][0] = {-1, -1}; // 起点的前驱设为无效 while (!q.empty()) { auto [x, y] = q.front(); q.pop(); // 到达终点 if (x == 4 && y == 4) { return; } // 尝试四个方向 for (int i = 0; i < 4; ++i) { int nx = x + dx[i]; int ny = y + dy[i]; if (isValid(nx, ny)) { vis[nx][ny] = true; pre[nx][ny] = {x, y}; q.push({nx, ny}); } } } } int main() { // 读入迷宫 for (int i = 0; i < 5; ++i) { for (int j = 0; j < 5; ++j) { cin >> maze[i][j]; } } // 如果起点或终点是障碍，直接无路 if (maze[0][0] == 1 || maze[4][4] == 1) { cout << "No Way!" << endl; return 0; } // 初始化 memset(vis, false, sizeof(vis)); bfs(); // 检查终点是否被访问到 if (!vis[4][4]) { cout << "No Way!" << endl; return 0; } // 回溯路径：从终点往回走到起点 vector<pair<int, int>> path; int x = 4, y = 4; while (!(x == -1 && y == -1)) { // 当到达起点的前驱(-1,-1)时停止 path.push_back({x, y}); auto p = pre[x][y]; x = p.first; y = p.second; } // 此时path是从终点到起点的顺序，需要反转 reverse(path.begin(), path.end()); // 输出路径 for (auto [px, py] : path) { cout << "(" << py << "," << px << ")" << endl; } return 0; }做一名聪明的CS玩家
题目描述
作为计算机学院的学生，CS应该是大家都很熟悉的一款游戏。那么如果你是一个真正的CS玩家，不如来试下这道题目吧。
当你在CSing的时候，什么事情最让你郁闷呢，估计就是当你与敌人刚要开战的时候，发现自己没有子弹了吧^_^。这个时候最聪明的选择就是赶快回到老家去买子弹继续战斗。那么怎样回到老家需要的时间最短呢？？
输入描述
输入的第一行有两个整数N,M分别表示的是地图的宽和长(1 =< M =< N <= 100)，接下来的N行分别输入CS地图的具体情况。‘@’表示的是你现在所在的位置,‘#’表示的你老家的位置，‘X’表示的是敌人可能出现的位置，虽然是可能出现的位置，但是没有子弹的你显然不愿意冒险走这个位置，即使要节省时间。 ‘*’表示的是你可以放心走过的安全位置。
输出描述
求出在保证安全的条件下从‘@’到老家‘#’所需要的最小时间并且输出，假设每走一步需要一个单位的时间，且你只能向上下左右四个方向走，并且不能走出CS地图的范围。如果通过安全的位置点无法到达老家，则输出“GAME OVER”
示例 1
输入：
5 5 ***XX *@XXX **XX# ***X* *****输出：
8#include <bits/stdc++.h> using namespace std; int n, m; // n行 m列 vector<string> grid; // 存储地图 int sx, sy, ex, ey; // 起点(sx,sy) 终点(ex,ey) // 四个方向：上、下、左、右 int dx[4] = {-1, 1, 0, 0}; int dy[4] = {0, 0, -1, 1}; int bfs() { // 队列元素：x坐标, y坐标, 当前步数 queue<tuple<int, int, int>> q; // 访问标记 vector<vector<bool>> visited(n, vector<bool>(m, false)); q.push({sx, sy, 0}); visited[sx][sy] = true; while (!q.empty()) { auto [x, y, step] = q.front(); q.pop(); // 到达终点 if (x == ex && y == ey) { return step; } // 四个方向尝试 for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; // 边界检查 if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; // 不能走 'X'，也不能走已经访问过的位置 if (grid[nx][ny] == 'X') continue; if (visited[nx][ny]) continue; visited[nx][ny] = true; q.push({nx, ny, step + 1}); } } // 不可达 return -1; } int main() { cin >> n >> m; // 注意：输入第一行是 n(行数) m(列数) grid.resize(n); for (int i = 0; i < n; i++) { cin >> grid[i]; // 查找起点和终点 for (int j = 0; j < m; j++) { if (grid[i][j] == '@') { sx = i; sy = j; } else if (grid[i][j] == '#') { ex = i; ey = j; } } } int ans = bfs(); if (ans == -1) { cout << "GAME OVER" << endl; } else { cout << ans << endl; } return 0; }Arbiter
题目描述
Arbiter出自暴雪公司星际争霸游戏，是神族中的强大魔法部队，拥有撕裂时空的能力。
驾驶Arbiter的执政官还可以通过撕裂时空，迅速把一支部队从一个星球传送到另一个星球。在广泛用Arbiter进行传送的同时，一名仲裁员的队长KMXS发现了一个严重的问题，
在使用Arbiter传送后，有些人会发生严重的精神障碍。通过研究，他找到了原因，当一个人从一个星球使用Arbiter传送到另一个星球时，他的手性会改变，（从左手性变成右手性，或者从右手性变成左手性），如果一个人通过长途跋涉最终回到他自己的星球时，他的手性可能会与出发时相反，这将导致严重的精神障碍，甚至死亡。
KMXS拥有星球之间的航道图。他需要禁止最少数目的航道，以致无论一个人从哪里出发，当他回到自己的星球，会是安全的。KMXS请求你的帮助。
输入描述
第一行输入一个整数 T，表示测试用例的数目。 0 < T <= 10
每个用例的第一行有两个整数 N 和 M，表示星球的数目和航道的数目。0 < N <= 15, 0 <= M <= 300
随后的 M 行表示航道，每个 (u, v) 代表在星球 u 和星球 v 之间有一条双向的航道（u 不等于 v）。0 <= u, v < N
输出描述
每个测试用例输出一行，用一个整数表示KMXS为了要避免人们精神错乱， 必须禁止的最少航道数目。
示例 1
输入：
1 3 3 0 1 1 2 2 0输出：
1#include <bits/stdc++.h> using namespace std; int main() { int T; cin >> T; while (T--) { int N, M; cin >> N >> M; vector<pair<int, int>> edges(M); for (int i = 0; i < M; ++i) { int u, v; cin >> u >> v; edges[i] = {u, v}; } int max_valid = 0; // 固定节点0的颜色为0，枚举其他N-1个节点的颜色 for (int mask = 0; mask < (1 << (N - 1)); ++mask) { vector<int> color(N, 0); // 节点0已经是0 for (int i = 1; i < N; ++i) { color[i] = (mask >> (i - 1)) & 1; } int valid = 0; for (auto &e : edges) { int u = e.first, v = e.second; if (color[u] != color[v]) { ++valid; } } if (valid > max_valid) max_valid = valid; } int ans = M - max_valid; cout << ans << endl; } return 0; }Special array
题目描述
输入n和m(20>=m>=n>0)求出所有满足以下方程的正整数数列 i1,i2,...,in，使i1+i2+...+in=m，且i1>=i2...>=in。例如：当n=4, m=8时，将得到如下5 个数列：
5 1 1 1
4 2 1 1
3 3 1 1
3 2 2 1
2 2 2 2
输入描述
输入只有一行，包含每个数列的元素个数n和数列元素的和m。
输出描述
按照字典逆序输出所有的数列，每个数列输出一行，每个数列元素用一个空格分开。
示例 1
输入：
4 8输出：
5 1 1 1 4 2 1 1 3 3 1 1 3 2 2 1 2 2 2 2#include <bits/stdc++.h> using namespace std; int n, m; vector<int> seq; // 存储当前构造的序列 // pos: 当前要填的位置索引（0~n-1） // maxVal: 当前位置允许的最大值（保证非递增） // sumLeft: 剩余需要分配的和 void dfs(int pos, int maxv, int 里eft) { if (pos == n) { // 已经填完所有位置 if (left == 0) { // 且和正好用完 for (int i = 0; i < n; ++i) { cout << seq[i] << " \n"[i == n - 1]; // 最后一个数后换行 } } return; } // 计算当前数的上限： // 不能超过前一个数（maxVal），也不能超过 sumLeft - (剩余位置数)， // 因为后面每个位置至少为 1，所以要留出足够多的和给后面。 int u=min(maxv,left-(n-pos-1)); for(int i=u;i>=1;i--){ seq[pos]=i; bfs(pos+1,i,left-i); } } int main() { cin >> n >> m; seq.resize(n); // 第一个位置最大值不能超过 m - (n-1)（后面 n-1 个至少是 1） // 但直接传 m 作为 maxVal 也可以，因为 upper 会进一步限制 dfs(0, m, m); return 0; }单向公路
题目描述
某个地区有许多城镇，但并不是每个城镇都跟其他城镇有公路连接，且有公路的并不都能双向行驶。现在我们把这些城镇间的公路分布及允许的行驶方向告诉你，你需要编程解决通过公路是否可以从一个城镇到达另一个城镇。（我们规定，城镇自己跟自己可互相到达，即A可到达A).
输入描述
第一行只有一个数N,下面将跟着2N行数据. 在前N行数据中,对于每行数据,最开头一个数字number,表明这一行总共有number个数,number的下一个数为i,代表编号为i的那个城镇.这行余下的就是跟i有公路连接的城镇的(编号)名单，且只能从城镇i驶向其他城镇。如 4 1 2 3，表明:此行有4个数,跟城镇1有公路连接的城镇是编号为2和3的城镇.是从1连到2 和3 ,不能从2 和3 连到1. 在后N行数据中,每行由两个数字组成a,b(表示城镇的编号). 对于每个输入的数有如下关系 0 <= input_number <= 1000 .
输出描述
对于输入数据中的每个a,b,判断是否可以从城镇a通过公路到达城镇b,如果可以,输出Yes;否则输出No.
示例 1
输入：
3 4 1 2 3 3 4 5 3 5 8 1 2 1 8 4 8输出：
Yes No Yes#include <bits/stdc++.h> using namespace std; const int MAXN = 1001; int graph[MAXN][MAXN]; // 邻接矩阵 // BFS 判断从 s 能否到达 t，n 是节点编号的上限（0 ~ n-1） bool canReach(int s, int t, int n) { if (s == t) return true; bool vis[MAXN] = {false}; queue<int> q; q.push(s); vis[s] = true; // 【关键修复】起始节点标记已访问 while (!q.empty()) { int cur = q.front(); q.pop(); for (int i = 0; i < n; ++i) { if (graph[cur][i] && !vis[i]) { if (i == t) return true; vis[i] = true; q.push(i); } } } return false; } int main() { int N; cin >> N; // 第一行：N int maxNode = 0; // 读取前 N 行：每个城镇的出边 for (int i = 0; i < N; ++i) { int number, u; cin >> number >> u; maxNode = max(maxNode, u); // 后面有 number-2 个城镇编号 for (int j = 0; j < number - 2; ++j) { int v; cin >> v; graph[u][v] = 1; // 有向边 u -> v maxNode = max(maxNode, v); } } // 读取后 N 行：查询 for (int i = 0; i < N; ++i) { int a, b; cin >> a >> b; maxNode = max({maxNode, a, b}); // 确保节点范围包含查询点 cout << (canReach(a, b, maxNode + 1) ? "Yes" : "No") << endl; // 注意：BFS 中需要知道节点编号范围，这里用 maxNode+1 作为上界（因为节点从0开始） } return 0; }
