微信网站作用,自己做网站还是用博客,中国企业500强排行榜完整榜单,山西大学物理电子工程学院研招网C/C编程#xff08;1~8级#xff09;全部真题・点这里 第1题#xff1a;道路 N个以 1 … N 标号的城市通过单向的道路相连:。每条道路包含两个参数#xff1a;道路的长度和需要为该路付的通行费#xff08;以金币的数目来表示#xff09; Bob and Alice 过去住在城市 1.在… C/C编程1~8级全部真题・点这里 第1题道路 N个以 1 … N 标号的城市通过单向的道路相连:。每条道路包含两个参数道路的长度和需要为该路付的通行费以金币的数目来表示 Bob and Alice 过去住在城市 1.在注意到Alice在他们过去喜欢玩的纸牌游戏中作弊后Bob和她分手了并且决定搬到城市N。他希望能够尽可能快的到那但是他囊中羞涩。我们希望能够帮助Bob找到从1到N最短的路径前提是他能够付的起通行费。 时间限制1000 内存限制65536 输入 第一行包含一个整数K, 0 K 10000, 代表Bob能够在他路上花费的最大的金币数。第二行包含整数N 2 N 100, 指城市的数目。第三行包含整数R, 1 R 10000, 指路的数目. 接下来的R行每行具体指定几个整数S, D, L 和 T来说明关于道路的一些情况这些整数之间通过空格间隔: S is 道路起始城市, 1 S N D is 道路终点城市, 1 D N L is 道路长度, 1 L 100 T is 通行费 (以金币数量形式度量), 0 T 100 注意不同的道路可能有相同的起点和终点。 输出 输入结果应该只包括一行即从城市1到城市N所需要的最小的路径长度花费不能超过K个金币。如果这样的路径不存在结果应该输出-1。 样例输入 5 6 7 1 2 2 3 2 4 3 3 3 4 2 4 1 3 4 1 4 6 2 1 3 5 2 0 5 4 3 2 样例输出 11 这个问题可以使用Dijkstra算法来解决用于找到从城市1到城市N的最短路径。
以下是一个解决道路问题的C语言程序
#include stdio.h
#include stdbool.h
#include limits.h#define MAX_N 100
#define MAX_R 100// 定义道路结构
typedef struct {int dest;int length;int toll;
} Road;int dijkstra(int K, int N, int R, Road roads[][MAX_R]) {int distance[MAX_N];bool visited[MAX_N];int i, j;// 初始化距离数组和访问标记数组for (i 1; i N; i) {distance[i] INT_MAX;visited[i] false;}// 设置起点城市1的距离为0distance[1] 0;// 执行N-1次迭代for (i 1; i N; i) {int minDistance INT_MAX;int minIndex -1;// 找到距离最小且未被访问的城市for (j 1; j N; j) {if (!visited[j] distance[j] minDistance) {minDistance distance[j];minIndex j;}}if (minIndex -1) {break; // 所有城市都已访问退出循环}visited[minIndex] true;// 更新与当前城市相邻的城市的距离for (j 0; j R; j) {Road road roads[minIndex][j];if (road.dest ! -1 distance[minIndex] road.length K distance[minIndex] road.length road.toll distance[road.dest]) {distance[road.dest] distance[minIndex] road.length road.toll;}}}return distance[N];
}int main() {int K, N, R;scanf(%d %d %d, K, N, R);Road roads[MAX_N][MAX_R];int i, j;for (i 1; i N; i) {for (j 0; j R; j) {roads[i][j].dest -1; // 初始化道路目的地为-1表示无效}}for (i 0; i R; i) {int S, D, L, T;scanf(%d %d %d %d, S, D, L, T);for (j 0; j R; j) {if (roads[S][j].dest -1) {roads[S][j].dest D;roads[S][j].length L;roads[S][j].toll T;break;}}}int result dijkstra(K, N, R, roads);if (result INT_MAX) {printf(-1\n);} else {printf(%d\n, result);}return 0;
}在这个解决方案中我们首先读取输入的金币数K、城市数N和道路数R。
然后我们创建一个大小为MAX_N×MAX_R的二维数组roads用于存储道路的信息。
接下来我们初始化roads数组的每个元素的目的地为-1表示无效。然后我们根据输入的道路信息将相应的目的地、长度和通行费存储在roads数组中。
然后我们调用dijkstra函数进行Dijkstra算法的执行。该函数接受金币数K、城市数N、道路数R和roads数组作为参数返回从城市1到城市N的最短路径长度。
在dijkstra函数中我们首先初始化距离数组distance和访问标记数组visited。然后我们设置起点城市1的距离为0。
接下来我们进行N-1次迭代。在每次迭代中我们找到距离最小且未被访问的城市将其标记为已访问并更新与该城市相邻的城市的距离。我们只更新满足以下条件的城市未被访问、从当前城市到相邻城市的距离不超过K并且经过该道路的通行费加上当前城市的距离小于相邻城市的当前距离。
最后我们返回距离数组中城市N的距离作为最终结果。如果距离数组中城市N的值为INT_MAX表示不存在满足条件的路径输出-1否则输出该值。
综上所述这个C语言程序可以根据输入的金币数、城市数和道路信息计算出从城市1到城市N的最短路径长度并输出结果。
第2题Rainbow的商店 Rainbow开了一家商店在一次进货中获得了N个商品。 已知每个商品的利润和过期时间。 Rainbow每天只能卖一个商品并且过期商品不能再卖。 Rainbow也可以选择在每天出售哪个商品并且一定可以卖出。 由于这些限制Rainbow需要制定一份合理的售卖计划。请你计算一下Rainbow最终可以获得的最大收益。 时间限制1000 内存限制262144 输入 第一行两个整数N。 接下来N行每行两个整数分别表示每个商品的利润、过期时间。 1N,利润,时间10000。 输出 输出一个整数表示Rainbow最终可以获得的最大收益。 样例输入 7 20 1 2 1 10 3 100 2 8 2 5 20 50 10 样例输出 185 提示 第1天卖出20 第2天卖出100 第3天卖出10 第4天卖出50实际上只要在第10天卖就可以 第5天卖出5实际上只要在第20天前卖就可以 总计185 其它2件商品由于过期、每天只能卖一个的限制在最优策略下应该不出售。 这个问题可以使用动态规划来解决。我们可以定义一个状态数组dp其中dp[i]表示在第i天能够获得的最大收益。
以下是一个解决Rainbow商店问题的C语言程序
#include stdio.h#define MAX_N 100int maxProfit(int N, int profits[], int expiration[]) {int dp[MAX_N 1] {0};int i, j;for (i 1; i N; i) {int maxProfit profits[i]; // 假设卖出当前商品for (j 1; j i; j) {if (i - j expiration[j] dp[j] profits[i] maxProfit) {maxProfit dp[j] profits[i]; // 更新最大收益}}dp[i] maxProfit;}return dp[N];
}int main() {int N;scanf(%d, N);int profits[MAX_N];int expiration[MAX_N];int i;for (i 1; i N; i) {scanf(%d %d, profits[i], expiration[i]);}int result maxProfit(N, profits, expiration);printf(%d\n, result);return 0;
}在这个解决方案中我们首先读取输入的商品数量N。
然后我们创建两个数组profits和expiration分别用于存储商品的利润和过期时间。
接下来我们使用循环读取每个商品的利润和过期时间并将它们存储在相应的数组中。
然后我们调用maxProfit函数计算Rainbow最终可以获得的最大收益。该函数接受商品数量N、利润数组profits和过期时间数组expiration作为参数返回最大收益。
在maxProfit函数中我们定义一个状态数组dp并初始化为0。然后我们进行迭代计算每一天的最大收益。
对于第i天我们假设卖出当前商品将其利润加到当前最大收益中。然后我们遍历第i天之前的每一天j如果卖出第j天的商品可以在第i天之前卖出并且卖出第j天的商品加上当前商品的利润可以得到更大的收益就更新最大收益。
最后我们返回dp[N]作为最终结果即Rainbow最终可以获得的最大收益。
综上所述这个C语言程序可以根据输入的商品利润和过期时间计算出Rainbow最终可以获得的最大收益并输出结果。
第3题冰阔落 老王喜欢喝冰阔落。 初始时刻桌面上有n杯阔落编号为1到n。老王总想把其中一杯阔落倒到另一杯中这样他一次性就能喝很多很多阔落假设杯子的容量是足够大的。 有m 次操作每次操作包含两个整数x与y。 若原始编号为x 的阔落与原始编号为y的阔落已经在同一杯请输出Yes否则我们将原始编号为y 所在杯子的所有阔落倒往原始编号为x 所在的杯子并输出No。 最后老王想知道哪些杯子有冰阔落。 时间限制10000 内存限制65536 输入 有多组测试数据少于 5 组。 每组测试数据第一行两个整数 n, m (n, m50000)。接下来 m 行每行两个整数 x, y (1x, yn)。 输出 每组测试数据前 m 行输出 “Yes” 或者 “No”。 第 m1 行输出一个整数表示有阔落的杯子数量。 第 m2 行有若干个整数从小到大输出这些杯子的编号。 样例输入 3 2 1 2 2 1 4 2 1 2 4 3 样例输出 No Yes 2 1 3 No No 2 1 4 这个问题可以使用并查集Disjoint Set来解决。我们可以创建一个数组parent用于记录每个杯子所属的集合。
以下是一个解决冰阔落 I问题的C语言程序
#include stdio.h#define MAX_N 50000int parent[MAX_N 1]; // 并查集数组int find(int x) {if (parent[x] x) {return x;}return parent[x] find(parent[x]); // 路径压缩
}void merge(int x, int y) {int px find(x);int py find(y);if (px ! py) {parent[py] px;}
}int main() {int n, m;while (scanf(%d %d, n, m) 2) {int i;for (i 1; i n; i) {parent[i] i; // 初始化并查集}for (i 1; i m; i) {int x, y;scanf(%d %d, x, y);if (find(x) find(y)) {printf(Yes\n);} else {printf(No\n);merge(x, y); // 合并两个杯子所属的集合}}int count 0;printf(%d\n, n); // 输出杯子数量初始假设所有杯子都有阔落for (i 1; i n; i) {if (parent[i] i) {printf(%d , i); // 输出有阔落的杯子编号count;}}printf(\n);}return 0;
}在这个解决方案中我们使用一个循环读取多组测试数据。
对于每组测试数据我们首先读取杯子的数量n和操作次数m。
然后我们创建一个大小为n的并查集数组parent并将每个杯子初始化为属于自己的集合。
接下来我们进行m次操作。对于每次操作我们读取两个杯子的编号x和y。
如果x和y已经在同一个集合中即它们属于同一杯阔落则输出Yes。
如果x和y不在同一个集合中我们将原始编号为y所在杯子的所有阔落倒入原始编号为x所在的杯子并输出No。然后我们将这两个杯子所属的集合合并。
完成m次操作后我们统计有阔落的杯子数量并输出这些杯子的编号。
综上所述这个C语言程序可以根据输入的阔落杯子编号和操作输出每次操作的结果以及最后有阔落的杯子数量和编号。
第4题青蛙的约会 两只青蛙在网上相识了它们聊得很开心于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上于是它们约定各自朝西跳直到碰面为止。可是它们出发之前忘记了一件很重要的事情既没有问清楚对方的特征也没有约定见面的具体位置。不过青蛙们都是很乐观的它们觉得只要一直朝着某个方向跳下去总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙你被要求写一个程序来判断这两只青蛙是否能够碰面会在什么时候碰面。 我们把这两只青蛙分别叫做青蛙A和青蛙B并且规定纬度线上东经0度处为原点由东往西为正方向单位长度1米这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x青蛙B的出发点坐标是y。青蛙A一次能跳m米青蛙B一次能跳n米两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。 时间限制1000 内存限制65536 输入 输入只包括一行5个整数xymnL其中x≠y 20000000000 m、n 20000000000 L 2100000000。 输出 输出碰面所需要的跳跃次数如果永远不可能碰面则输出一行Impossible 样例输入 1 2 3 4 5 样例输出 4 这个问题可以通过求解一元线性同余方程来解决。线性同余方程的一般形式为ax ≡ b (mod m)其中a、b、m为已知整数x为未知数。在这个问题中我们需要求解的是 (x mt) ≡ (y nt) (mod L)其中t为正整数表示跳了多少次。
以下是一个解决青蛙的约会问题的C语言程序
#include stdio.hlong long gcd(long long a, long long b) {if (b 0) {return a;}return gcd(b, a % b);
}int main() {long long x, y, m, n, L;scanf(%lld %lld %lld %lld %lld, x, y, m, n, L);long long diff y - x;long long lcm m * n / gcd(m, n);if (diff % gcd(m, n) ! 0) {printf(Impossible\n);} else {diff (diff % L L) % L; // 防止diff为负数long long ans diff / gcd(m, n) % (L / gcd(m, n));printf(%lld\n, ans);}return 0;
}在这个解决方案中我们首先读取输入的x、y、m、n和L。
我们计算出差值diff y - x并计算m和n的最小公倍数lcm m * n / gcd(m, n)。
如果diff不是gcd(m, n)的倍数则说明两只青蛙永远不会碰面输出Impossible。
否则我们将diff取模L并确保结果为非负数。然后我们计算答案ans diff / gcd(m, n) % (L / gcd(m, n))。这里我们将结果除以gcd(m, n)以确保ans是最小非负整数。
最后我们输出答案ans表示两只青蛙碰面所需要的跳跃次数。
综上所述这个C语言程序可以根据输入的参数计算出两只青蛙碰面所需要的跳跃次数。如果永远不可能碰面则输出Impossible。
