乐山网站公众号建设,wordpress微电影模板,先做网站先备案,品牌策划公司和品牌设计公司第1题#xff1a;怪盗基德的滑翔翼 怪盗基德是一个充满传奇色彩的怪盗#xff0c;专门以珠宝为目标的超级盗窃犯。而他最为突出的地方#xff0c;就是他每次都能逃脱中村警部的重重围堵#xff0c;而这也很大程度上是多亏了他随身携带的便于操作的滑翔翼。 有一天#xff…
第1题怪盗基德的滑翔翼 怪盗基德是一个充满传奇色彩的怪盗专门以珠宝为目标的超级盗窃犯。而他最为突出的地方就是他每次都能逃脱中村警部的重重围堵而这也很大程度上是多亏了他随身携带的便于操作的滑翔翼。 有一天怪盗基德像往常一样偷走了一颗珍贵的钻石不料却被柯南小朋友识破了伪装而他的滑翔翼的动力装置也被柯南踢出的足球破坏了。不得已怪盗基德只能操作受损的滑翔翼逃脱。 假设城市中一共有N幢建筑排成一条线每幢建筑的高度各不相同。初始时怪盗基德可以在任何一幢建筑的顶端。他可以选择一个方向逃跑但是不能中途改变方向因为中森警部会在后面追击。因为滑翔翼动力装置受损他只能往下滑行即只能从较高的建筑滑翔到较低的建筑。他希望尽可能多地经过不同建筑的顶部这样可以减缓下降时的冲击力减少受伤的可能性。请问他最多可以经过多少幢不同建筑的顶部包含初始时的建筑 输入 输入数据第一行是一个整数KK 100代表有K组测试数据。 每组测试数据包含两行第一行是一个整数N(N 100)代表有N幢建筑。第二行包含N个不同的整数每一个对应一幢建筑的高度h0 h 10000按照建筑的排列顺序给出。 输出 对于每一组测试数据输出一行包含一个整数代表怪盗基德最多可以经过的建筑数量。 样例输入 3 8 300 207 155 299 298 170 158 65 8 65 158 170 298 299 155 207 300 10 2 1 3 4 5 6 7 8 9 10 样例输出 6 6 9 以下是使用C语言编写的解决方案可以计算出怪盗基德最多可以经过的建筑数量
#include stdio.hint maxBuildings(int buildings[], int n) {int maxCount 0;int count 0;for (int i 0; i n; i) {count 1; // 当前建筑高度肯定满足条件int currHeight buildings[i];// 向左寻找更高的建筑for (int j i - 1; j 0; j--) {if (buildings[j] currHeight) {count;currHeight buildings[j];}}// 向右寻找更高的建筑currHeight buildings[i];for (int j i 1; j n; j) {if (buildings[j] currHeight) {count;currHeight buildings[j];}}if (count maxCount) {maxCount count;}}return maxCount;
}int main() {int K;scanf(%d, K);while (K--) {int N;scanf(%d, N);int buildings[N];for (int i 0; i N; i) {scanf(%d, buildings[i]);}int maxCount maxBuildings(buildings, N);printf(%d\n, maxCount);}return 0;
}该解决方案使用一个函数maxBuildings来计算怪盗基德最多可以经过的建筑数量。对于每幢建筑该函数会向左和向右搜索更高的建筑统计经过的建筑数量并记录最大值。
在主函数中首先读取测试数据的数量K。然后通过循环读取每组测试数据的建筑数量N和建筑高度。调用maxBuildings函数计算最多经过的建筑数量并输出结果。
第2题数字组合 有n个正整数找出其中和为t(t也是正整数)的可能的组合方式。如 n5,5个数分别为1,2,3,4,5t5 那么可能的组合有514和523和55三种组合方式。 输入 输入的第一行是两个正整数n和t用空格隔开其中1n20,表示正整数的个数t为要求的和(1t1000) 接下来的一行是n个正整数用空格隔开。 输出 和为t的不同的组合方式的数目。 样例输入 5 5 1 2 3 4 5 样例输出 3 以下是使用C语言编写的解决方案可以计算出和为t的可能组合方式的数量
#include stdio.hint countCombinations(int numbers[], int n, int t) {// 创建一个二维数组来存储组合数目int dp[n 1][t 1];// 初始化数组for (int i 0; i n; i) {for (int j 0; j t; j) {if (j 0) {// 当目标和为0时有一种组合方式即不选择任何数字dp[i][j] 1;} else {// 其他情况初始化为0dp[i][j] 0;}}}// 动态规划计算组合数目for (int i 1; i n; i) {for (int j 1; j t; j) {if (numbers[i - 1] j) {// 当当前数字大于目标和时无法选择该数字组合数目与上一个数字相同dp[i][j] dp[i - 1][j];} else {// 当前数字可选或不选计算两种情况的组合数目之和dp[i][j] dp[i - 1][j] dp[i - 1][j - numbers[i - 1]];}}}return dp[n][t];
}int main() {int n, t;scanf(%d %d, n, t);int numbers[n];for (int i 0; i n; i) {scanf(%d, numbers[i]);}int numCombinations countCombinations(numbers, n, t);printf(%d\n, numCombinations);return 0;
}该解决方案使用动态规划来计算和为t的组合方式的数量。首先创建一个二维数组dp其中dp[i][j]表示使用前i个数字组成和为j的组合数目。
然后通过两层循环遍历数组进行动态规划计算。如果当前数字大于目标和j则无法选择该数字组合数目与上一个数字的组合数目相同否则当前数字可选或不选计算两种情况的组合数目之和。
最后返回dp[n][t]作为结果即和为t的组合方式的数量。
在主函数中首先读取输入的正整数个数n和目标和t。然后通过循环读取n个正整数。调用countCombinations函数计算组合方式的数量并输出结果。
第3题带通配符的字符串匹配 通配符是一类键盘字符当我们不知道真正字符或者不想键入完整名字时常常使用通配符代替一个或多个真正字符。通配符有问号(?)和星号()等其中“?”可以代替一个字符而“”可以代替零个或多个字符。 你的任务是给出一个带有通配符的字符串和一个不带通配符的字符串判断他们是否能够匹配。 例如1?456 可以匹配 12456、13456、1a456但是却不能够匹配23456、1aa456277?8可以匹配 24457798、237708、27798。 输入 输入有两行每行为一个不超过20个字符的字符串第一行带通配符第二行不带通配符 输出 如果两者可以匹配就输出“matched”否则输出“not matched” 样例输入 1456? 11111114567 样例输出 matched 以下是使用C语言编写的解决方案可以判断带通配符的字符串和不带通配符的字符串是否匹配
#include stdio.h
#include stdbool.h
#include string.hbool isMatched(char wildcard[], char str[]) {int m strlen(wildcard);int n strlen(str);// 创建一个二维数组来存储匹配结果bool dp[m 1][n 1];// 初始化数组memset(dp, false, sizeof(dp));// 空字符串与空通配符匹配dp[0][0] true;// 处理空通配符与非空字符串的匹配for (int j 1; j n; j) {dp[0][j] false;}// 处理非空通配符与空字符串的匹配for (int i 1; i m; i) {if (wildcard[i - 1] *) {dp[i][0] dp[i - 1][0];}}// 动态规划计算匹配结果for (int i 1; i m; i) {for (int j 1; j n; j) {if (wildcard[i - 1] ? || wildcard[i - 1] str[j - 1]) {// 当前字符匹配dp[i][j] dp[i - 1][j - 1];} else if (wildcard[i - 1] *) {// 当前字符为*dp[i][j] dp[i - 1][j] || dp[i][j - 1];} else {// 当前字符不匹配dp[i][j] false;}}}return dp[m][n];
}int main() {char wildcard[21];char str[21];fgets(wildcard, sizeof(wildcard), stdin);fgets(str, sizeof(str), stdin);// 去除字符串末尾的换行符wildcard[strcspn(wildcard, \n)] \0;str[strcspn(str, \n)] \0;if (isMatched(wildcard, str)) {printf(matched\n);} else {printf(not matched\n);}return 0;
}该解决方案使用动态规划来判断带通配符的字符串和不带通配符的字符串是否匹配。首先创建一个二维数组dp其中dp[i][j]表示通配符字符串的前i个字符与不带通配符字符串的前j个字符是否匹配。
然后通过三层循环遍历通配符字符串和不带通配符字符串进行动态规划计算。根据通配符字符的情况判断当前字符是否匹配以及是否可以使用通配符*来匹配。
最后返回dp[m][n]作为匹配结果如果为true则表示匹配否则表示不匹配。
在主函数中通过fgets函数分别读取带通配符的字符串和不带通配符的字符串并使用strcspn函数去除字符串末尾的换行符。调用isMatched函数判断字符串是否匹配并输出结果。
第4题股票买卖 最近越来越多的人都投身股市阿福也有点心动了。谨记着“股市有风险入市需谨慎”阿福决定先来研究一下简化版的股票买卖问题。 假设阿福已经准确预测出了某只股票在未来 N 天的价格他希望买卖两次使得获得的利润最高。为了计算简单起见利润的计算方式为卖出的价格减去买入的价格。 同一天可以进行多次买卖。但是在第一次买入之后必须要先卖出然后才可以第二次买入。 现在阿福想知道他最多可以获得多少利润。 输入 输入的第一行是一个整数 T (T 50) 表示一共有 T 组数据。 接下来的每组数据第一行是一个整数 N (1 N 100, 000) 表示一共有 N 天。第二行是 N 个被空格分开的整数表示每天该股票的价格。该股票每天的价格的绝对值均不会超过 1,000,000 。 输出 对于每组数据输出一行。该行包含一个整数表示阿福能够获得的最大的利润。 样例输入 3 7 5 14 -2 4 9 3 17 6 6 8 7 4 1 -2 4 18 9 5 2 样例输出 28 2 0 提示对于第一组样例阿福可以第 1 次在第 1 天买入价格为 5 然后在第 2 天卖出价格为 14 。第 2 次在第 3 天买入价格为 -2 然后在第 7 天卖出价格为 17 。一共获得的利润是 (14 - 5) (17 - (-2)) 28 对于第二组样例阿福可以第 1 次在第 1 天买入价格为 6 然后在第 2 天卖出价格为 8 。第 2 次仍然在第 2 天买入然后在第 2 天卖出。一共获得的利润是 8 - 6 2 对于第三组样例由于价格一直在下跌阿福可以随便选择一天买入之后迅速卖出。获得的最大利润为 0 以下是使用C语言编写的解决方案可以计算阿福能够获得的最大利润
#include stdio.h
#include stdlib.h
#include limits.hint maxProfit(int prices[], int n) {int* leftProfit (int*)malloc(sizeof(int) * n);int* rightProfit (int*)malloc(sizeof(int) * n);// 计算从左侧开始的最大利润int minPrice prices[0];leftProfit[0] 0;for (int i 1; i n; i) {leftProfit[i] (prices[i] - minPrice) leftProfit[i - 1] ? (prices[i] - minPrice) : leftProfit[i - 1];minPrice prices[i] minPrice ? prices[i] : minPrice;}// 计算从右侧开始的最大利润int maxPrice prices[n - 1];rightProfit[n - 1] 0;for (int i n - 2; i 0; i--) {rightProfit[i] (maxPrice - prices[i]) rightProfit[i 1] ? (maxPrice - prices[i]) : rightProfit[i 1];maxPrice prices[i] maxPrice ? prices[i] : maxPrice;}// 找到两次交易的最大利润int maxProfit 0;for (int i 0; i n; i) {int profit leftProfit[i] rightProfit[i];maxProfit profit maxProfit ? profit : maxProfit;}free(leftProfit);free(rightProfit);return maxProfit;
}int main() {int T;scanf(%d, T);while (T--) {int N;scanf(%d, N);int* prices (int*)malloc(sizeof(int) * N);for (int i 0; i N; i) {scanf(%d, prices[i]);}int result maxProfit(prices, N);printf(%d\n, result);free(prices);}return 0;
}该解决方案使用动态规划的思想来计算阿福能够获得的最大利润。首先创建两个数组leftProfit和rightProfit分别存储从左侧开始和从右侧开始的最大利润。
对于从左侧开始的最大利润我们从左到右遍历价格数组维护一个最小价格变量minPrice并计算当前价格与最小价格之间的利润更新leftProfit[i]。同时更新最小价格。
对于从右侧开始的最大利润我们从右到左遍历价格数组维护一个最大价格变量maxPrice并计算最大价格与当前价格之间的利润更新rightProfit[i]。同时更新最大价格。
然后遍历价格数组计算第一次和第二次交易的最大利润之和找到其中的最大值。
在主函数中首先读取整数T表示有T组数据。然后对于每组数据读取整数N并动态分配一个大小为N的整数数组来存储每天的股票价格。调用maxProfit函数计算最大利润并输出结果。
