品牌网站建设策,百度怎么发布自己的广告,洛阳网站设计公司,莱芜庞允盟第1题#xff1a;书架 John最近买了一个书架用来存放奶牛养殖书籍#xff0c;但书架很快被存满了#xff0c;只剩最顶层有空余。 John共有N头奶牛(1 ≤ N ≤ 20,000)#xff0c;每头奶牛有自己的高度Hi(1 ≤ Hi ≤ 10,000)#xff0c;N头奶牛的总高度为S。书架高度为B(1 ≤…
第1题书架 John最近买了一个书架用来存放奶牛养殖书籍但书架很快被存满了只剩最顶层有空余。 John共有N头奶牛(1 ≤ N ≤ 20,000)每头奶牛有自己的高度Hi(1 ≤ Hi ≤ 10,000)N头奶牛的总高度为S。书架高度为B(1 ≤ B ≤ S 2,000,000,007). 为了到达书架顶层奶牛可以踩着其他奶牛的背像叠罗汉一样直到他们的总高度不低于书架高度。当然若奶牛越多则危险性越大。为了帮助John到达书架顶层找出使用奶牛数目最少的解决方案吧。 时间限制10000 内存限制65536 输入 第1行空格隔开的整数N和B 第2~N1行第i1行为整数Hi 输出 能达到书架高度所使用奶牛的最少数目 样例输入 6 40 6 18 11 13 19 11 样例输出 3 以下是使用贪心算法来解决书架问题的C语言代码
#include stdio.h
#include stdlib.h#define MAX_N 20000int compare(const void* a, const void* b) {return *(int*)a - *(int*)b;
}int minCows(int heights[MAX_N], int n, int b) {qsort(heights, n, sizeof(int), compare); // 将奶牛的高度排序int sum 0;int count 0;for (int i n - 1; i 0; i--) {sum heights[i];count;if (sum b) {break;}}return count;
}int main() {int n, b;int heights[MAX_N];// 读取输入scanf(%d %d, n, b);for (int i 0; i n; i) {scanf(%d, heights[i]);}// 使用贪心算法求解最少使用的奶牛数目int minCowsCount minCows(heights, n, b);// 输出结果printf(%d\n, minCowsCount);return 0;
}该算法使用贪心算法的思想通过将奶牛的高度进行排序并从最高的奶牛开始逐个累加奶牛的高度直到总高度不低于书架高度B为止。首先使用快速排序算法对奶牛的高度进行排序。然后从最高的奶牛开始累加其高度并记录使用的奶牛数目。如果累加的总高度不低于书架高度B则停止累加。最后返回使用的奶牛数目作为答案。
第2题棋盘问题 在一个给定形状的棋盘形状可能是不规则的上面摆放棋子棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列请编程求解对于给定形状和大小的棋盘摆放k个棋子的所有可行的摆放方案C。 时间限制1000 内存限制65536 输入 输入含有多组测试数据。 每组数据的第一行是两个正整数n k用一个空格隔开表示了将在一个n*n的矩阵内描述棋盘以及摆放棋子的数目。 n 8 , k n 当为-1 -1时表示输入结束。 随后的n行描述了棋盘的形状每行有n个字符其中 # 表示棋盘区域 . 表示空白区域数据保证不出现多余的空白行或者空白列。 输出 对于每一组数据给出一行输出输出摆放的方案数目C 数据保证C2^31。 样例输入 2 1 #. .# 4 4 …# …#. .#… #… -1 -1 样例输出 2 1 以下是使用回溯法来解决棋盘问题的C语言代码
#include stdio.h
#include stdbool.h#define MAX_N 8int count 0; // 记录可行的摆放方案数bool isValid(char board[MAX_N][MAX_N], int row, int col, int n) {// 检查同一行是否已经有棋子for (int c 0; c col; c) {if (board[row][c] Q) {return false;}}// 检查左上方对角线是否已经有棋子for (int r row, c col; r 0 c 0; r--, c--) {if (board[r][c] Q) {return false;}}// 检查左下方对角线是否已经有棋子for (int r row, c col; r n c 0; r, c--) {if (board[r][c] Q) {return false;}}return true;
}void backtrack(char board[MAX_N][MAX_N], int col, int n, int k) {if (col n) {if (k 0) {count;}return;}for (int row 0; row n; row) {if (board[row][col] # isValid(board, row, col, n)) {board[row][col] Q;backtrack(board, col 1, n, k - 1);board[row][col] #;}}backtrack(board, col 1, n, k);
}int chessboard(int n, int k, char board[MAX_N][MAX_N]) {count 0;backtrack(board, 0, n, k);return count;
}int main() {int n, k;char board[MAX_N][MAX_N];while (scanf(%d %d, n, k) 2) {if (n -1 k -1) {break;}for (int i 0; i n; i) {scanf(%s, board[i]);}int result chessboard(n, k, board);printf(%d\n, result);}return 0;
}该算法使用回溯法的思想通过递归地尝试在每个位置放置棋子同时检查放置的位置是否满足要求。首先定义isValid函数用于检查某个位置是否合法即同一行、同一列以及对角线上没有其他棋子。然后使用backtrack函数进行回溯搜索从左到右、从上到下依次尝试在每个位置放置棋子。如果当前位置合法就将棋子放置在该位置并继续在下一列进行回溯搜索。如果当前位置不合法则继续在下一行尝试。当回溯到最后一列时如果已经放置了k个棋子则找到了一个可行的摆放方案将计数器加1。最后调用chessboard函数进行求解并输出可行的摆放方案数目C。
第3题课程表 现在你总共有n门课需要选记为0到n-1。在选修某些课程之前需要一些先修课程。例如想要学习课程0你需要先完成课程1我们用一个匹配来表示他们[0, 1]。给定课程总量以及它们的先决条件判断是否可能完成所有课程的学习 时间限制1000 内存限制65536 输入 多组数据。每组数据第一行是n和mn表示有n门课程m表示有m组依赖关系接下来的m行是依赖关系的具体信息a b表示第a门课程依赖第b门课程。 0n 10000 m 4000 两组数据之间可能有空行 输出 对每组数据能完成输出 True不能完成输出 False 样例输入 2 1 1 0 2 2 1 0 0 1 样例输出 True False 提示 示例2解释 总共有2门课程。学习课程1之前你需要先完成课程0并且学习课程0之前你还应先完成课程1。这是不可能的。 对于课程表问题使用搜索剪枝技术是一个有效的方法。我们可以使用深度优先搜索DFS来遍历课程的依赖关系并在搜索过程中进行剪枝以提高效率。
以下是使用搜索剪枝技术来解决课程表问题的C语言代码
#include stdio.h
#include stdbool.h#define MAX_N 1000
#define MAX_M 4000bool dfs(int course, int numCourses, int prerequisites[MAX_M][2], int numPrerequisites, bool visited[MAX_N], bool path[MAX_N]) {visited[course] true; // 标记当前课程为已访问path[course] true; // 将当前课程加入遍历路径中// 遍历当前课程的后续课程for (int i 0; i numPrerequisites; i) {if (prerequisites[i][1] course) {int nextCourse prerequisites[i][0];// 判断是否存在环路即当前课程在当前的遍历路径中if (path[nextCourse]) {return false;}// 如果后续课程未访问则继续进行深度优先搜索if (!visited[nextCourse]) {if (!dfs(nextCourse, numCourses, prerequisites, numPrerequisites, visited, path)) {return false;}}}}path[course] false; // 将当前课程从遍历路径中移除return true;
}bool canFinish(int numCourses, int prerequisites[MAX_M][2], int numPrerequisites) {bool visited[MAX_N] {false}; // 记录课程是否已访问bool path[MAX_N] {false}; // 记录当前的遍历路径// 对每门课程进行深度优先搜索for (int i 0; i numCourses; i) {if (!visited[i]) {if (!dfs(i, numCourses, prerequisites, numPrerequisites, visited, path)) {return false;}}}return true;
}int main() {int numCourses, numPrerequisites;int prerequisites[MAX_M][2];while (scanf(%d %d, numCourses, numPrerequisites) 2) {if (numCourses 0 numPrerequisites 0) {break;}for (int i 0; i numPrerequisites; i) {scanf(%d %d, prerequisites[i][0], prerequisites[i][1]);}bool result canFinish(numCourses, prerequisites, numPrerequisites);printf(%s\n, result ? True : False);}return 0;
}该算法使用深度优先搜索DFS进行遍历通过递归地搜索课程的依赖关系。首先定义dfs函数进行深度优先搜索其中course表示当前的课程visited用于记录课程是否已访问path用于记录当前的遍历路径。在搜索过程中首先将当前课程标记为已访问并将其加入遍历路径中。然后遍历当前课程的后续课程如果发现后续课程已经在当前的遍历路径中则表示存在环路返回false。如果后续课程未访问则继续进行深度优先搜索。最后将当前课程从遍历路径中移除并返回true表示搜索完成。在canFinish函数中对每门课程进行深度优先搜索如果存在环路则返回false如果所有课程都能够完成搜索返回true。最后调用canFinish函数进行求解并输出结果。
第4题拯救公主 多灾多难的公主又被大魔王抓走啦国王派遣了第一勇士阿福去拯救她。 身为超级厉害的术士同时也是阿福的好伙伴你决定祝他一臂之力。你为阿福提供了一张大魔王根据地的地图上面标记了阿福和公主所在的位置以及一些不能够踏入的禁区。你还贴心地为阿福制造了一些传送门通过一个传送门可以瞬间转移到任意一个传送门当然阿福也可以选择不通过传送门瞬移。传送门的位置也被标记在了地图上。此外你还查探到公主所在的地方被设下了结界需要集齐K种宝石才能打开。当然你在地图上也标记出了不同宝石所在的位置。 你希望阿福能够带着公主早日凯旋。于是在阿福出发之前你还需要为阿福计算出他最快救出公主的时间。 地图用一个R×C的字符矩阵来表示。字符S表示阿福所在的位置字符E表示公主所在的位置字符#表示不能踏入的禁区字符$表示传送门字符.表示该位置安全数字字符0至4表示了宝石的类型。阿福每次可以从当前的位置走到他上下左右四个方向上的任意一个位置但不能走出地图边界。阿福每走一步需要花费1个单位时间从一个传送门到达另一个传送门不需要花费时间。当阿福走到宝石所在的位置时就视为得到了该宝石不需要花费额外时间。 时间限制1000 内存限制65536 输入 第一行是一个正整数T1 T 10表示一共有T组数据。 每一组数据的第一行包含了三个用空格分开的正整数R、C2 R, C 200和K表示地图是一个R×C的矩阵而阿福需要集齐K种宝石才能够打开拘禁公主的结界。 接下来的R行描述了地图的具体内容每一行包含了C个字符。字符含义如题目描述中所述。保证有且仅有一个S和E。$的数量不超过10个。宝石的类型在数字0至4范围内即不会超过5种宝石。 输出 对于每一组数据输出阿福救出公主所花费的最少单位时间。若阿福无法救出公主则输出“oop!”只输出引号里面的内容不输出引号。每组数据的输出结果占一行。 样例输入 1 7 8 2 … …S…#0. .##…1… .0#… …1#… …##E… …1… 样例输出 11 根据题目要求我们可以使用贪心算法来解决这个问题。贪心算法的思想是每一步都选择当前最优的解决方案希望最终能够得到全局最优解。
下面是使用贪心算法解决该问题的C语言代码示例
#include stdio.h
#include stdlib.h
#include string.h#define MAX_ROWS 200
#define MAX_COLS 200int minTime; // 最少单位时间
int gemsCollected; // 已经收集到的宝石数量
char map[MAX_ROWS][MAX_COLS];
int visited[MAX_ROWS][MAX_COLS];
int rows, cols, requiredGems;
int startRow, startCol, endRow, endCol; // 起始位置和目标位置的行列坐标
int gems[MAX_ROWS][MAX_COLS]; // 记录宝石的类型// 计算两点之间的曼哈顿距离
int manhattanDistance(int row1, int col1, int row2, int col2) {return abs(row1 - row2) abs(col1 - col2);
}// 贪心算法
void greedy(int row, int col, int time) {// 边界条件判断if (row 0 || row rows || col 0 || col cols || visited[row][col] || map[row][col] #)return;// 标记当前位置为已访问visited[row][col] 1;// 到达目标位置更新最少单位时间if (row endRow col endCol) {if (gemsCollected requiredGems) {if (time minTime || minTime -1)minTime time;}visited[row][col] 0; // 恢复当前位置为未访问状态return;}// 如果当前位置是宝石则增加宝石数量if (gems[row][col] ! -1)gemsCollected;// 向四个方向进行搜索greedy(row - 1, col, time 1); // 上greedy(row 1, col, time 1); // 下greedy(row, col - 1, time 1); // 左greedy(row, col 1, time 1); // 右// 如果当前位置是宝石则减少宝石数量if (gems[row][col] ! -1)gemsCollected--;// 恢复当前位置为未访问状态visited[row][col] 0;
}int main() {int numCases;scanf(%d, numCases);while (numCases--) {scanf(%d %d %d, rows, cols, requiredGems);// 初始化minTime -1;gemsCollected 0;// 读取地图数据for (int i 0; i rows; i) {scanf(%s, map[i]);for (int j 0; j cols; j) {visited[i][j] 0;if (map[i][j] S) {startRow i;startCol j;} else if (map[i][j] E) {endRow i;endCol j;} else if (map[i][j] 0 map[i][j] 4) {gems[i][j] map[i][j] - 0;} else {gems[i][j] -1;}}}// 计算起始位置到每个宝石的曼哈顿距离int gemDistances[5];memset(gemDistances, 0, sizeof(gemDistances));for (int i 0; i rows; i) {for (int j 0; j cols; j) {if (gems[i][j] ! -1) {int distance manhattanDistance(startRow, startCol, i, j);if (gemDistances[gems[i][j]] 0 || distance gemDistances[gems[i][j]]) {gemDistances[gems[i][j]] distance;}}}}// 根据宝石的曼哈顿距离进行排序for (int i 0; i requiredGems; i) {int minDistance -1;int minGem -1;for (int j 0; j 5; j) {if (gemDistances[j] ! 0 (minDistance -1 || gemDistances[j] minDistance)) {minDistance gemDistances[j];minGem j;}}gemDistances[minGem] 0;for (int j 0; j rows; j) {for (int k 0; k cols; k) {if (gems[j][k] minGem) {gems[j][k] i;}}}}// 使用贪心算法搜索最短路径greedy(startRow, startCol, 0);// 输出结果if (minTime ! -1) {printf(%d\n, minTime);} else {printf(oop!\n);}}return 0;
}这个代码使用了深度优先搜索和贪心算法来解决问题首先计算起始位置到每个宝石的曼哈顿距离然后按照宝石的距离进行排序然后使用贪心算法进行搜索直到达到目标位置并且收集到足够数量的宝石。如果无法救出公主则输出oop!。
请注意这只是一个示例代码可能还有一些边界情况没有考虑到你可以根据实际情况进行修改和优化。
