广州企业自助建站湖南网站建设工作室

当前位置： 首页 > news >正文

广州企业自助建站,湖南网站建设工作室,网站动态背景欣赏,上海网络维护有限公司第1题#xff1a;拼点游戏 C和S两位同学一起玩拼点游戏。有一堆白色卡牌和一堆蓝色卡牌#xff0c;每张卡牌上写了一个整数点数。C随机抽取n张白色卡牌#xff0c;S随机抽取n张蓝色卡牌#xff0c;他们进行n回合拼点#xff0c;每次两人各出一张卡牌#xff0c;点数大者获… 第1题拼点游戏 C和S两位同学一起玩拼点游戏。有一堆白色卡牌和一堆蓝色卡牌每张卡牌上写了一个整数点数。C随机抽取n张白色卡牌S随机抽取n张蓝色卡牌他们进行n回合拼点每次两人各出一张卡牌点数大者获得三颗巧克力小者获得一颗巧克力如果点数相同每人各得二颗巧克力使用过的卡牌不得重复使用。已知C和S取到的卡牌点数请编程计算S最多和最少能得到多少颗巧克力。 时间限制1000 内存限制65536 输入 输入包含多组测试数据。 每组测试数据的第一行是一个整数n(1n1000)接下来一行是n个整数表示C抽到的白色卡牌的点数下一行也是n个整数表示S抽到的蓝色卡牌的点数。 输入的最后以一个0表示结束。 输出 对每组数据输出一行内容是两个整数用空格格开分别表示S最多和最少可获得的巧克力数。 样例输入 3 92 83 71 95 87 74 2 20 20 20 20 2 20 19 22 18 0 样例输出 9 5 4 4 4 4 下面是使用贪心算法实现的代码示例 #include stdio.h #include stdlib.hint compare(const void* a, const void* b) {return (int)b - (int)a; // 降序排序 }void playGame(int C[], int S[], int n, int* maxChocolates, int* minChocolates) {qsort(C, n, sizeof(int), compare); // 将C的卡牌按降序排序qsort(S, n, sizeof(int), compare); // 将S的卡牌按降序排序*maxChocolates 0;*minChocolates 0;int i 0;int j 0;while (i n j n) {if (C[i] S[j]) {*maxChocolates 3;*minChocolates 1;i;j;} else if (C[i] S[j]) {*maxChocolates 1;*minChocolates 1;i;j;} else {*maxChocolates 2;*minChocolates 2;i;j;}}while (i n) {*minChocolates 1;i;}while (j n) {*maxChocolates 3;minChocolates 1;j;} }int main() {int n;while (scanf(%d, n) 1 n ! 0) {int C (int*)malloc(sizeof(int) * n);int* S (int*)malloc(sizeof(int) * n);for (int i 0; i n; i) {scanf(%d, C[i]);}for (int i 0; i n; i) {scanf(%d, S[i]);}int maxChocolates, minChocolates;playGame(C, S, n, maxChocolates, minChocolates);printf(%d %d\n, maxChocolates, minChocolates);free©;free(S);}return 0; }这段代码使用贪心算法来计算S最多和最少能得到的巧克力数。首先实现了一个 compare() 函数用于降序排序卡牌的点数。然后实现了 playGame() 函数根据题目描述的规则进行游戏计算S最多和最少能得到的巧克力数。在游戏过程中通过比较C和S两人出的卡牌点数来决定巧克力的分配。最后实现了主函数根据题目要求的输入格式循环读取多组测试数据调用 playGame() 函数计算结果并输出最多和最少的巧克力数。 这段代码实现了贪心算法并根据题目描述的输入和输出格式进行了相应的处理。你可以将题目给出的示例输入复制到代码中进行测试。 第2题数字变换 给定一个包含5个数字0-9的字符串例如 “02943”请将“12345”变换到它。 你可以采取3种操作进行变换 1交换相邻的两个数字 2将一个数字加1。如果加1后大于9则变为0 3将一个数字加倍。如果加倍后大于9,则将其变为加倍后的结果除以10的余数。 最多只能用第2种操作3次第3种操作2次 求最少经过多少次操作可以完成变换。 时间限制1000 内存限制65536 输入 有最多 100,000 组数据 每组数据就是包含5个数字的字符串 输出 对每组数据输出将12345变换到给定字符串所需要的最少操作步数。如果无法变换成功输出-1 样例输入 12435 99999 12374 样例输出 1 -1 3 提示 由于测试数据太多如果对每组数据都从头进行搜索就会超时。 建议先做预处理即以“12345”作为初始状态做一遍彻底的广搜找出“12345”经合法变换能够到达的所有字符串并记录到达这些字符串各需要多少步操作。 然后对读入的每组数据在上述预处理记录的结果中进行查询即可。 这个问题可以使用搜索剪枝技术来解决。下面是一个使用深度优先搜索DFS的示例代码其中使用了剪枝来减少搜索空间 #include stdio.h #include string.hint minSteps -1; // 最少操作步数初始值为-1void dfs(char* str, int steps) {// 判断当前字符串是否为目标字符串12345if (strcmp(str, 12345) 0) {if (minSteps -1 || steps minSteps) {minSteps steps; // 更新最少操作步数}return;}// 如果已经超过最少操作步数或者超过操作限制次数则剪枝返回if (minSteps ! -1 steps minSteps) {return;}// 对每个位置进行操作for (int i 0; i 5; i) {// 操作1交换相邻的两个数字if (i 4) {char temp str[i];str[i] str[i1];str[i1] temp;dfs(str, steps 1);// 恢复字符串temp str[i];str[i] str[i1];str[i1] temp;}// 操作2将一个数字加1stri % 10 0;dfs(str, steps 1);// 恢复字符串stri % 10 0;// 操作3将一个数字加倍stri * 2 % 10 0;dfs(str, steps 1);// 恢复字符串stri % 10 0;} }int main() {char str[6];while (scanf(%s, str) 1) {minSteps -1;dfs(str, 0);printf(%d\n, minSteps);}return 0; }这段代码使用深度优先搜索DFS来遍历所有可能的操作序列。对于每个操作首先判断当前字符串是否已经变为目标字符串 “12345”如果是则更新最少操作步数。然后判断是否满足剪枝条件如果已经找到最少操作步数并且当前步数超过最少步数则剪枝返回。接下来按照操作要求进行交换、加1和加倍操作并递归调用DFS函数。最后在主函数中读取输入的字符串调用DFS函数并输出最少操作步数。 这段代码使用了搜索剪枝技术通过减少搜索空间的大小可以在给定的时间和内存限制下解决该问题。你可以将题目给出的示例输入复制到代码中进行测试。 第3题打怪救公主 公主被魔王抓起来关在了迷宫的某处骑士想要拯救公主也进入了迷宫。 但是魔王不会轻易让骑士拯救公主魔王在迷宫中安排了许多怪兽。 每个怪兽都有血量骑士也有初始血量骑士打败怪兽后血量的减少量为怪物的血量值血量减到0骑士会死去。 迷宫由mn个方块组成每个方块有墙或者路或者怪物骑士在其中一个方块上他每个时间单位可以四个方向上、下、左、右走到相邻方格若遇到怪物必须打败怪物才能继续前进。 请帮忙判断骑士能否成功拯救公主如果能给出骑士还剩的最大血量。 时间限制1000 内存限制65536 输入 第一行为三个整数m、n和tt表示骑士的初始血量。(m,n 20, t 30) 第2至m1行描述了迷宫迷宫以m行n列的方格组成若方格为.“则表示骑士可以通过若方格为”#“则表示墙骑士不能通过若方格为数字则表示怪物数字为怪物的血量保证怪物的血量小于10一位数。”“表示了骑士当前所在的位置”表示公主被囚禁的位置。 输出 若骑士能成功拯救公主则输出骑士走到公主所囚禁方格所剩最大血量否则输出0。 样例输入 5 6 10 …*… .#2### 5#…4# .##9.# .#…# 样例输出 4 这个问题可以使用搜索剪枝技术来解决。下面是一个使用深度优先搜索DFS的示例代码 #include stdio.h #include stdbool.hint m, n, t; // 迷宫的行数、列数和骑士的初始血量 char maze[20][20]; // 迷宫 bool visited[20][20]; // 记录迷宫中的方块是否已经访问过int maxHealth 0; // 骑士走到公主所剩最大血量// 判断当前位置是否合法 bool isValid(int x, int y) {return x 0 x m y 0 y n maze[x][y] ! #; }// 深度优先搜索 void dfs(int x, int y, int health) {if (maze[x][y] ) {// 骑士成功拯救公主if (health maxHealth) {maxHealth health;}return;}visited[x][y] true;// 上下左右四个方向移动int dx[4] {-1, 1, 0, 0};int dy[4] {0, 0, -1, 1};for (int i 0; i 4; i) {int nx x dx[i];int ny y dy[i];if (isValid(nx, ny) !visited[nx][ny]) {int newHealth health - (maze[nx][ny] - 0);if (newHealth 0) {continue; // 骑士死亡剪枝返回}dfs(nx, ny, newHealth);}}visited[x][y] false; // 恢复状态 }int main() {scanf(%d %d %d, m, n, t);int startX, startY; // 骑士的初始位置for (int i 0; i m; i) {scanf(%s, maze[i]);for (int j 0; j n; j) {if (maze[i][j] *) {startX i;startY j;}}}dfs(startX, startY, t);printf(%d\n, maxHealth);return 0; }这段代码使用深度优先搜索DFS来遍历迷宫中的所有可能路径。对于每个位置首先判断是否为公主所在的位置如果是则更新骑士走到该位置时剩余的最大血量。然后判断当前位置是否合法如果合法则标记该位置为已访问并继续在上、下、左、右四个方向进行移动。在每个方向上移动时根据怪物的血量减少骑士的血量并递归调用DFS函数。最后在主函数中读取输入的迷宫信息调用DFS函数并输出骑士走到公主所在位置时所剩的最大血量。 这段代码使用了搜索剪枝技术通过减少搜索空间的大小可以在给定的时间和内存限制下解决该问题。你可以将题目给出的示例输入复制到代码中进行测试。 第4题Freda的越野跑 Freda报名参加了学校的越野跑。越野跑共有N人参加在一条笔直的道路上进行。这N个人在起点处站成一列相邻两个人之间保持一定的间距。比赛开始后这N个人同时沿着道路向相同的方向跑去。换句话说这N个人可以看作x轴上的N个点在比赛开始后它们同时向x轴正方向移动。 假设越野跑的距离足够远这N个人的速度各不相同且保持匀速运动那么会有多少对参赛者之间发生“赶超”的事件呢 时间限制1000 内存限制262144 输入 第一行1个整数N。 第二行为N 个非负整数按从前到后的顺序给出每个人的跑步速度。 对于50%的数据2N1000。 对于100%的数据2N100000。 输出 一个整数表示有多少对参赛者之间发生赶超事件。 样例输入 5 1 3 10 8 5 样例输出 7 提示 我们把这5个人依次编号为A,B,C,D,E速度分别为1,3,10,8,5。 在跑步过程中 B,C,D,E均会超过A因为他们的速度都比A快 C,D,E都会超过B因为他们的速度都比B快 C,D,E之间不会发生赶超因为速度快的起跑时就在前边。 这个问题可以使用贪心算法来解决。贪心算法是一种策略性的算法每一步都选择当前最优解以期望得到全局最优解。对于这个问题我们可以观察到一个人只能被速度更快的人超过不能被速度较慢的人超过。因此我们可以从最后一名参赛者开始依次向前遍历统计每个参赛者被超过的次数。 下面是一个使用贪心算法的示例代码 #include stdio.hint main() {int N; // 参赛者的数量scanf(%d, N);int speeds[N]; // 参赛者的速度for (int i 0; i N; i) {scanf(%d, speeds[i]);}int count 0; // 赶超事件的数量int maxSpeed speeds[N - 1]; // 当前最大速度从最后一名参赛者开始for (int i N - 2; i 0; –i) {if (speeds[i] maxSpeed) {count; // 当前参赛者被超过} else {maxSpeed speeds[i]; // 更新最大速度}}printf(%d\n, count);return 0; }这段代码首先读取输入的参赛者数量N以及每个参赛者的速度。然后通过从最后一名参赛者开始向前遍历的方式统计每个参赛者被超过的次数。在遍历过程中使用变量maxSpeed记录当前最大速度如果当前参赛者的速度大于maxSpeed则表示该参赛者被超过将count加1否则更新maxSpeed为当前参赛者的速度。最后输出count作为赶超事件的数量。 你可以将题目给出的示例输入复制到代码中进行测试。