江蘇運營網(wǎng)站建設(shè)業(yè)務(wù)免費建站哪個最好
第1題:攔截導(dǎo)彈
某國為了防御敵國的導(dǎo)彈襲擊, 發(fā)展出一種導(dǎo)彈攔截系統(tǒng)。 但是這種導(dǎo)彈攔截系統(tǒng)有一個缺陷: 雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度,但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。 某天, 雷達(dá)捕捉到敵國的導(dǎo)彈來襲。 由于該系統(tǒng)還在試用階段, 所以只有一套系統(tǒng), 因此有可能不能攔截所有的導(dǎo)彈。
輸入導(dǎo)彈依次飛來的高度(雷達(dá)給出的高度數(shù)據(jù)是不大于 30000 的正整數(shù)) , 計算這套系統(tǒng)最多能攔截多少導(dǎo)彈。
時間限制: 1000
內(nèi)存限制: 65536
輸入
第一行是一個整數(shù) N(不超過 15) , 表示導(dǎo)彈數(shù)。 第二行包含 N 個整數(shù), 為導(dǎo)彈依次飛來的高度(雷達(dá)給出的高度數(shù)據(jù)是不大于 30000的正整數(shù)) 。
輸出
一個整數(shù), 表示最多能攔截的導(dǎo)彈數(shù)。
樣例輸入
8
389 207 155 300 299 170 158 65
樣例輸出
6
要解決攔截導(dǎo)彈的問題,可以使用動態(tài)規(guī)劃的方法。
以下是使用C語言實現(xiàn)的代碼:
#include <stdio.h>#define MAX_MISSILES 15int max(int a, int b) {return (a > b) ? a : b;
}int missileInterception(int missiles[], int n) {int dp[MAX_MISSILES] = {0};int maxInterceptions = 0;for (int i = 0; i < n; i++) {dp[i] = 1;for (int j = 0; j < i; j++) {if (missiles[i] <= missiles[j]) {dp[i] = max(dp[i], dp[j] + 1);}}maxInterceptions = max(maxInterceptions, dp[i]);}return maxInterceptions;
}int main() {int n;scanf("%d", &n);int missiles[MAX_MISSILES];for (int i = 0; i < n; i++) {scanf("%d", &missiles[i]);}int maxInterceptions = missileInterception(missiles, n);printf("%d\n", maxInterceptions);return 0;
}
該代碼使用一個一維數(shù)組dp來保存狀態(tài),其中dp[i]表示以第i個導(dǎo)彈為結(jié)尾的最大攔截導(dǎo)彈數(shù)。
首先,初始化dp數(shù)組的所有元素為1,表示每個導(dǎo)彈都可以單獨攔截。然后,遍歷導(dǎo)彈數(shù)組,對于每個導(dǎo)彈missiles[i],在之前的導(dǎo)彈中查找高度小于等于當(dāng)前導(dǎo)彈的導(dǎo)彈missiles[j],如果找到,則更新dp[i]為dp[j]+1,表示以導(dǎo)彈missiles[i]結(jié)尾的最大攔截導(dǎo)彈數(shù)。最后,找到dp數(shù)組中的最大值即為所求的最多能攔截的導(dǎo)彈數(shù)。
第2題:神奇的數(shù)列
一個正整數(shù)數(shù)列, 可以將它切割成若干個數(shù)據(jù)段, 每個數(shù)據(jù)段由值相同的相鄰元素構(gòu)成。 該數(shù)列的神奇之處在于, 每次切除一個數(shù)據(jù)段后,該數(shù)據(jù)段前后的元素自動連接在一起成為鄰居。 例如從數(shù)列“2 8 9 77 6 9 4” 中切除數(shù)據(jù)段“7 7 ” 后, 余下的元素會構(gòu)成數(shù)列“2 8 9 6 94”
請問若要將該數(shù)列切割成若干個數(shù)據(jù)段, 則至少會切出來幾個數(shù)據(jù)段?
樣例: 按下列順序切割數(shù)列“2 8 9 7 7 6 9 4” , 只要切割成 6 段
切割出“7 7” , 余下 “2 8 9 6 9 4”
切割出 “6” , 余下 “2 8 9 9 4”
切割出 “9 9” , 余下 “2 8 4”
切割出 “2” , 余下 “8 4”
切割出 “8” , 余下 “4”
時間限制: 1000
內(nèi)存限制: 65536
輸入
第一行是一個整數(shù), 示共有多少組測試數(shù)據(jù)。 每組測試數(shù)據(jù)的輸入包括兩行: 第一行是整數(shù) N, N<=200,表示數(shù)列的長度, 第二行是 N 個正整數(shù)。
輸出
每個測試案例的輸出占一行, 是一個整數(shù)。 格式是: Case n: x n 是測試數(shù)據(jù)組編號, x 是答案
樣例輸入
2
8
2 8 9 7 7 6 9 4
16
2 8 9 7 7 6 9 4 4 2 8 4 2 7 6 9
樣例輸出
Case 1: 6
Case 2: 11
要解決神奇的數(shù)列問題,可以使用貪心算法。
以下是使用C語言實現(xiàn)的代碼:
#include <stdio.h>#define MAX_LENGTH 200int min(int a, int b) {return (a < b) ? a : b;
}int countSegments(int sequence[], int n) {int segments = 1;for (int i = 1; i < n; i++) {if (sequence[i] != sequence[i - 1]) {segments++;}}return segments;
}int main() {int t;scanf("%d", &t);for (int i = 1; i <= t; i++) {int n;scanf("%d", &n);int sequence[MAX_LENGTH];for (int j = 0; j < n; j++) {scanf("%d", &sequence[j]);}int segments = countSegments(sequence, n);printf("Case %d: %d\n", i, segments);}return 0;
}
該代碼使用一個循環(huán)遍歷數(shù)列,對于每個數(shù)列元素sequence[i],如果它與前一個元素sequence[i-1]不相等,則將段數(shù)segments加1。最后,segments的值即為所求的切割數(shù)據(jù)段的數(shù)量。
第3題:硬幣
宇航員 Bob 有一天來到火星上, 他有收集硬幣的習(xí)慣。 于是他將火星上所有面值的硬幣都收集起來了, 一共有 n 種, 每種只有一個: 面值分別為 a1,a2… an。 Bob 在機場看到了一個特別喜歡的禮物, 想買來送給朋友 Alice, 這個禮物的價格是 X 元。 Bob 很想知道為了買這個禮物他的哪些硬幣是必須被使用的, 即 Bob 必須放棄收集好的哪些硬幣種類。 飛機場不提供找零, 只接受恰好 X 元。
時間限制: 1000
內(nèi)存限制: 262144
輸入
第一行包含兩個正整數(shù) n 和 x。 (1 <= n <= 200, 1 <= x <= 10000) 第二行從小到大為 n 個正整數(shù) a1, a2, a3 … an (1 <= ai <= 10000)
輸出
第一行是一個整數(shù), 即有多少種硬幣是必須被使用的。 第二行是這些必須使用的硬幣的面值(從小到大排列) 。
樣例輸入
5 18
1 2 3 5 10
樣例輸出
2
5 10
提示
輸入數(shù)據(jù)將保證給定面值的硬幣中至少有一種組合能恰好能夠支付 X元。 如果不存在必須被使用的硬幣, 則第一行輸出 0, 第二行輸出空行。
要解決硬幣問題,可以使用動態(tài)規(guī)劃的方法。
以下是使用C語言實現(xiàn)的代碼:
#include <stdio.h>
#include <stdbool.h>#define MAX_COINS 200
#define MAX_AMOUNT 10000bool dp[MAX_AMOUNT + 1] = {false};void findCoins(int coins[], int n, int amount) {dp[0] = true;for (int i = 0; i < n; i++) {for (int j = amount; j >= coins[i]; j--) {if (dp[j - coins[i]]) {dp[j] = true;}}}
}int main() {int n, amount;scanf("%d %d", &n, &amount);int coins[MAX_COINS];for (int i = 0; i < n; i++) {scanf("%d", &coins[i]);}findCoins(coins, n, amount);int count = 0;for (int i = 1; i <= amount; i++) {if (dp[i]) {count++;}}printf("%d\n", count);for (int i = 1; i <= amount; i++) {if (dp[i]) {printf("%d ", i);}}printf("\n");return 0;
}
該代碼使用一個布爾數(shù)組dp來保存狀態(tài),其中dp[i]表示是否存在一種硬幣組合,可以湊出金額i。
首先,將dp[0]設(shè)置為true,表示金額為0時不需要使用任何硬幣。然后,遍歷硬幣數(shù)組coins,對于每個硬幣coins[i],從amount向前遍歷到coins[i],如果存在一種硬幣組合可以湊出金額j-coins[i],則說明存在一種硬幣組合可以湊出金額j,將dp[j]設(shè)置為true。
最后,統(tǒng)計dp數(shù)組中為true的元素個數(shù),即為必須被使用的硬幣種類的數(shù)量。并輸出這些必須使用的硬幣面值。
第4題:公共子序列
我們稱序列 Z = < z1, z2, …, zk >是序列 X = < x1, x2, …, xm >的子序列當(dāng)且僅當(dāng)存在 嚴(yán)格上升 的序列< i1, i2, …, ik >, 使得對 j = 1, 2, … ,k, 有xij = zj。 比如 Z = < a, b, f, c > 是 X = < a, b, c, f, b, c >的子序列。 現(xiàn)在給出兩個序列 X 和 Y, 你的任務(wù)是找到 X 和 Y 的最大公共子序列, 也就是說要找到一個最長的序列 Z, 使得 Z 既是 X 的子序列也是 Y 的子序列。
時間限制: 3000
內(nèi)存限制: 65536
輸入
輸入包括多組測試數(shù)據(jù)。 每組數(shù)據(jù)包括一行, 給出兩個長度不超過200 的字符串, 表示兩個序列。 兩個字符串之間由若干個空格隔開。
輸出
對每組輸入數(shù)據(jù), 輸出一行, 給出兩個序列的最大公共子序列的長度。
樣例輸入
abcfbc abfcab
programming contest
abcd mnp
樣例輸出
4
2
0
要解決最大公共子序列問題,可以使用動態(tài)規(guī)劃的方法。
以下是使用C語言實現(xiàn)的代碼:
#include <stdio.h>
#include <string.h>#define MAX_LENGTH 200int max(int a, int b) {return (a > b) ? a : b;
}int longestCommonSubsequence(char X[], char Y[], int m, int n) {int dp[MAX_LENGTH + 1][MAX_LENGTH + 1];for (int i = 0; i <= m; i++) {for (int j = 0; j <= n; j++) {if (i == 0 || j == 0) {dp[i][j] = 0;} else if (X[i - 1] == Y[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);}}}return dp[m][n];
}int main() {char X[MAX_LENGTH + 1];char Y[MAX_LENGTH + 1];while (scanf("%s %s", X, Y) != EOF) {int m = strlen(X);int n = strlen(Y);int length = longestCommonSubsequence(X, Y, m, n);printf("%d\n", length);}return 0;
}
該代碼使用一個二維數(shù)組dp來保存狀態(tài),其中dp[i][j]表示序列X的前i個字符和序列Y的前j個字符的最大公共子序列的長度。
首先,將dp[i][0]和dp[0][j]都設(shè)置為0,表示當(dāng)一個序列的長度為0時,最大公共子序列的長度為0。
然后,從1到m和1到n的循環(huán)遍歷,如果X[i-1]等于Y[j-1],則說明X的第i個字符和Y的第j個字符相同,將dp[i][j]設(shè)置為dp[i-1][j-1]的值加1,表示當(dāng)前字符可以加入最大公共子序列。
如果X[i-1]不等于Y[j-1],則說明X的第i個字符和Y的第j個字符不相同,需要在X的前i-1個字符和Y的前j個字符的最大公共子序列和X的前i個字符和Y的前j-1個字符的最大公共子序列之間取最大值,即dp[i-1][j]和dp[i][j-1]的最大值。
最后,dp[m][n]即為X和Y的最大公共子序列的長度。