SWUST oj算法分析与设计 实验4

贪心的奶牛题目描述xlow有一群奶牛一共m头要带它们去牧场放牧。牧场上有一排距离不等的木桩共有n个nm。现在xlow需要把奶牛都拴在木桩上一头奶牛一桩让奶牛在木桩周围吃草。不过xlow的奶牛和普通的奶牛也很不一样它们很聪明并且很贪心还不喜欢看到别的奶牛比自己多占便宜。为了能每头奶牛都能吃到一样多的草拴奶牛的绳子都必须一样的长。xlow也知道它们的贪心所以也想办法尽可能满足它们希望绳子能尽可能地长。但同时不能让同一地方的草能同时被两只以上的奶牛吃到这样它们会打架抢地盘的并且那样就会不公平了就会有奶牛吃的比其它的奶牛要少。输入描述第一行依次有两个整数n,k其中2kn10000接下来一行有n个整数代表木桩的位置范围从-1e9到1e9输出描述输出距离最近的两只奶牛之间的最大距离示例 1输入5 3 2 5 1 10 7输出4#include bits/stdc.h using namespace std; int n, k; vectorint 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_mapchar, int id; for (int i 0; i n; i) id[s[i]] i; // 用邻接矩阵存图初始化为一个大数表示无穷大 const int INF 1e9; vectorvectorint g(n, vectorint(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 算法 vectorbool vis(n, false); // 标记顶点是否已加入生成树 vectorint minDist(n, INF); // 记录每个顶点到当前生成树的最短距离 vectorint 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(1n100)。第二行为一个字符串包含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; vectorint w(n); for (int i 0; i n; i) cin w[i]; // 每个组权值、包含的原始字符索引、这些字符当前的编码初始为空 vectorint weight w; vectorvectorint groups(n); // groups[i] 存储该组包含的字符索引 vectorstring 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]; vectorint 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; vectorTask 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); vectorint 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表示障碍逃跑起点为左上终点为右下输出描述逃跑线路见输出示例(请注意xy轴方向)如果没有路可以逃,则输出: 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]; // 标记是否访问过 pairint, 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() { queuepairint, 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; } // 回溯路径从终点往回走到起点 vectorpairint, 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列 vectorstring 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坐标, 当前步数 queuetupleint, int, int q; // 访问标记 vectorvectorbool visited(n, vectorbool(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; vectorpairint, 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) { vectorint 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(20mn0)求出所有满足以下方程的正整数数列 i1,i2,...,in使i1i2...inm且i1i2...in。例如当n4, m8时将得到如下5 个数列5 1 1 14 2 1 13 3 1 13 2 2 12 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; vectorint 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 umin(maxv,left-(n-pos-1)); for(int iu;i1;i--){ seq[pos]i; bfs(pos1,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 能否到达 tn 是节点编号的上限0 ~ n-1 bool canReach(int s, int t, int n) { if (s t) return true; bool vis[MAXN] {false}; queueint 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 中需要知道节点编号范围这里用 maxNode1 作为上界因为节点从0开始 } return 0; }