经常做飞机网站,做跨境电商被骗了,做网站的北京,荣耀手机商城第1题#xff1a;最长上升子序列 一个数的序列bi#xff0c;当b1 b2 … bS的时候#xff0c;我们称这个序列是上升的。对于给定的一个序列(a1, a2, …, aN)#xff0c;我们可以得到一些上升的子序列(ai1, ai2, …, aiK)#xff0c;这里1 i1 i2 最长上升子序列 一个数的序列bi当b1 b2 … bS的时候我们称这个序列是上升的。对于给定的一个序列(a1, a2, …, aN)我们可以得到一些上升的子序列(ai1, ai2, …, aiK)这里1 i1 i2 … iK N。比如对于序列(1, 7, 3, 5, 9, 4, 8)有它的一些上升子序列如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4比如子序列(1, 3, 5, 8). 你的任务就是对于给定的序列求出最长上升子序列的长度。 时间限制11000 内存限制65536 输入 输入的第一行是序列的长度N (1 N 1000)。第二行给出序列中的N个整数这些整数的取值范围都在0到10000。 输出 最长上升子序列的长度。 样例输入 7 1 7 3 5 9 4 8 样例输出 4 要解决最长上升子序列的问题可以使用动态规划的方法。
以下是使用C语言实现的代码
#include stdio.h
#include stdlib.hint max(int a, int b) {return (a b) ? a : b;
}int longestIncreasingSubsequence(int arr[], int n) {int dp[1001] {0};int maxLen 1;for (int i 0; i n; i) {dp[i] 1;for (int j 0; j i; j) {if (arr[i] arr[j]) {dp[i] max(dp[i], dp[j] 1);}}maxLen max(maxLen, dp[i]);}return maxLen;
}int main() {int n;scanf(%d, n);int arr[1001];for (int i 0; i n; i) {scanf(%d, arr[i]);}int longestLen longestIncreasingSubsequence(arr, n);printf(%d\n, longestLen);return 0;
}该代码使用一个一维数组dp来记录以每个位置上的元素为结尾的最长上升子序列的长度。
首先将dp数组的初始值全部设为1因为任意单个元素本身就是一个长度为1的上升子序列。
然后从第二个位置开始遍历数组中的每个元素对于每个元素再次遍历它之前的元素如果找到比当前元素小的元素说明可以将当前元素加入到以该元素结尾的子序列中更新dp数组的值。
最后遍历dp数组找到最大的值即为最长上升子序列的长度。
第2题神奇的口袋 有一个神奇的口袋总的容积是40用这个口袋可以变出一些物品这些物品的总体积必须是40。John现在有n个想要得到的物品每个物品的体积分别是a1a2……an。John可以从这些物品中选择一些如果选出的物体的总体积是40那么利用这个神奇的口袋John就可以得到这些物品。现在的问题是John有多少种不同的选择物品的方式。 时间限制10000 内存限制65536 输入 输入的第一行是正整数n (1 n 20)表示不同的物品的数目。接下来的n行每行有一个1到40之间的正整数分别给出a1a2……an的值。 输出 输出不同的选择物品的方式的数目。 样例输入 3 20 20 20 样例输出 3 要解决神奇的口袋问题可以使用递归的方法进行求解。
以下是使用C语言实现的代码
#include stdio.hint count 0;void magicalPocket(int items[], int n, int idx, int sum) {if (sum 0) {count;return;}if (idx n || sum 0) {return;}magicalPocket(items, n, idx 1, sum - items[idx]);magicalPocket(items, n, idx 1, sum);
}int main() {int n;scanf(%d, n);int items[21];for (int i 0; i n; i) {scanf(%d, items[i]);}magicalPocket(items, n, 0, 40);printf(%d\n, count);return 0;
}该代码使用递归函数magicalPocket来尝试不同的选择物品的方式。
递归函数的参数包括物品数组items、物品数量n、当前处理的物品索引idx和目标总体积sum。
函数首先判断如果目标总体积为0则表示找到一种选择方式将count计数器加1并返回。
然后判断如果当前处理的物品索引为n或目标总体积小于0则返回。
接下来递归调用函数分为两种情况选择当前物品或不选择当前物品。
选择当前物品时递归调用函数并更新目标总体积为sum - items[idx]同时将物品索引加1。
不选择当前物品时递归调用函数并保持目标总体积为sum同时将物品索引加1。
最后主函数调用magicalPocket函数并输出count计数器的值即为不同的选择物品的方式的数目。
第3题滑雪 Michael喜欢滑雪百这并不奇怪 因为滑雪的确很刺激。可是为了获得速度滑的区域必须向下倾斜而且当你滑到坡底你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9 一个人可以从某个点滑向上下左右相邻四个点之一当且仅当高度减小。在上面的例子中一条可滑行的滑坡为24-17-16-1。当然25-24-23-…-3-2-1更长。事实上这是最长的一条。 时间限制1000 内存限制65536 输入 输入的第一行表示区域的行数R和列数C(1 R,C 100)。下面是R行每行有C个整数代表高度h0h10000。 输出 输出最长区域的长度。 样例输入 5 5 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9 样例输出 25 要解决滑雪问题可以使用动态规划的方法。
以下是使用C语言实现的代码
#include stdio.h
#include stdbool.hint max(int a, int b) {return (a b) ? a : b;
}int longestSlide(int grid[][100], int R, int C, int r, int c, int dp[][100]) {if (dp[r][c] ! -1) {return dp[r][c];}int directions[4][2] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};int maxLen 1;for (int i 0; i 4; i) {int newRow r directions[i][0];int newCol c directions[i][1];if (newRow 0 newRow R newCol 0 newCol C grid[newRow][newCol] grid[r][c]) {maxLen max(maxLen, longestSlide(grid, R, C, newRow, newCol, dp) 1);}}dp[r][c] maxLen;return maxLen;
}int main() {int R, C;scanf(%d %d, R, C);int grid[100][100];int dp[100][100];for (int i 0; i R; i) {for (int j 0; j C; j) {scanf(%d, grid[i][j]);dp[i][j] -1;}}int maxLength 0;for (int i 0; i R; i) {for (int j 0; j C; j) {maxLength max(maxLength, longestSlide(grid, R, C, i, j, dp));}}printf(%d\n, maxLength);return 0;
}该代码使用一个二维数组dp来记录从每个位置开始的最长滑坡的长度以避免重复计算。
首先将dp数组的初始值全部设为-1表示尚未计算。
然后遍历输入的区域二维数组对于每个位置(r, c)调用longestSlide函数进行递归计算以该位置为起点的最长滑坡长度。
在longestSlide函数中首先判断如果dp[r][c]已经计算过则直接返回其值。
然后定义四个方向的移动数组directions分别为上、下、左、右。
接下来遍历四个方向计算新的行和列的位置并判断新位置是否在合法范围内且高度小于当前位置的高度。
如果满足条件则递归调用longestSlide函数并更新maxLen的值。
最后将dp[r][c]设为maxLen并返回。
最后主函数遍历整个区域二维数组找到最大的滑坡长度并输出。
第4题删除数字 娇娇一年级了刚刚学会了识数和比大小。有一天她在黑板上写上了一串数字21254。接着她擦掉了第一个2发现剩下124都在自己的位置上即1在第1位2在第2位4在第4位。 娇娇希望擦掉某些数后剩下的数列中在自己位置上的数尽量多。她发现这个问题很有趣想知道最多能有几个数在自己的位置上请你帮帮她! 时间限制1000 内存限制65536 输入 第一行一个整数 TestNum( ≤ 10)表示测试数据的组数。 接下来每组数据有两行第一行一个整数n( ≤ 1000)第二行n个正整数(≤ 1000)。 输出 对于每组测试数据输出一个数表示答案。 样例输入 3 5 2 1 2 5 4 7 2 2 3 2 4 5 3 10 1 1 2 2 3 3 4 4 5 5 样例输出 3 4 5 提示 第一组测试数据擦掉第一个数1 2 4 有 3 个数在自己的位置上。 第二组测试数据擦掉第4个、第7个数2 3 4 5 有 4 个数在自己的位置上。 第三组测试数据每种相同的数擦掉一个1 2 3 4 5 有 5 个数在自己的位置上。 要解决删除数字的问题可以使用贪心算法的思路。
以下是使用C语言实现的代码
#include stdio.h
#include stdbool.hint max(int a, int b) {return (a b) ? a : b;
}int countNumbers(int numbers[], int n) {int count 0;for (int i 0; i n; i) {if (numbers[i] i 1) {count;}}return count;
}int maxCountNumbers(int numbers[], int n) {int maxCount 0;for (int i 0; i n; i) {int temp numbers[i];numbers[i] -1;maxCount max(maxCount, countNumbers(numbers, n));numbers[i] temp;}return maxCount;
}int main() {int TestNum;scanf(%d, TestNum);while (TestNum--) {int n;scanf(%d, n);int numbers[1000];for (int i 0; i n; i) {scanf(%d, numbers[i]);}int result maxCountNumbers(numbers, n);printf(%d\n, result);}return 0;
}该代码使用两个函数来解决问题。
首先countNumbers函数用于计算给定数字数组中有多少个数字在自己的位置上。
函数遍历数组对于每个位置i如果数字numbers[i]的值等于i 1则计数器count加1。
最后返回计数器count的值。
接下来maxCountNumbers函数用于找到删除数字后最多有多少个数字在自己的位置上。
函数遍历数组对于每个位置i将数字numbers[i]暂存到temp变量中并将该位置的值设为-1表示删除。
然后调用countNumbers函数计算删除数字后剩下的数字数组中有多少个数字在自己的位置上并更新最大值maxCount。
最后将该位置的值恢复为temp继续下一次循环。
最后主函数根据输入的测试组数循环读取每组测试数据并调用maxCountNumbers函数计算答案并输出。
