1 PTA-演算法設計與分析-AC原題 2 7-1 最大子列和問題 (20分) 3 給定K個整陣列成的序列{ N1, N2, ..., NK }，“連續子列”被定義為{ Ni, Ni+1, ..., Nj }，其中 1≤i≤j≤K，“最大子列和”則被定義為所有連續子列元素的和中最大者，例如給定序列{ -2, 11, -4, 13, -5, -2 }，其連續子列{ 11, -4, 13 }有最大的和20，現要求你撰寫程式，計算給定整數序列的最大子列和， 4 本題旨在測驗各種不同的演算法在各種資料情況下的表現，各組測驗資料特點如下： 5 ? 資料1：與樣例等價，測驗基本正確性； 6 ? 資料2：102個隨機整數； 7 ? 資料3：103個隨機整數； 8 ? 資料4：104個隨機整數； 9 ? 資料5：105個隨機整數； 10 輸入格式: 11 輸入第1行給出正整數K (≤100000)；第2行給出K個整數，其間以空格分隔， 12 輸出格式: 13 在一行中輸出最大子列和，如果序列中所有整數皆為負數，則輸出0， 14 輸入樣例: 15 16 6 17 -2 11 -4 13 -5 -2 18 輸出樣例: 19 20 20 21 22 作者: DS課程組 23 單位: 浙江大學 24 時間限制: 50000 ms 25 記憶體限制: 64 MB 26 代碼長度限制: 16 KB 27 題目詳情 28 29 7-2 求素數個數 (30分) 30 求素數的個數，本題要求撰寫一個程式，求1~n的素數個數， 要求至少給出兩種解法，對于相同的n，給出這兩種解法的結果，通過相關資料進行測驗，目的是通過對比同一問題不同解法的絕對執行時間體會如何設計“好”的演算法， 31 輸入格式: 32 輸入在一行中給出1個整數n(<= 10 000 000)， 33 輸出格式: 34 對每一組輸入，在一行中輸出1~n的素數個數， 35 輸入樣例1: 36 37 5 38 輸出樣例1: 39 40 3 41 輸入樣例2: 42 43 14 44 輸出樣例2: 45 46 6 47 48 作者: 李廷元 49 單位: 中國民用航空飛行學院 50 時間限制: 200 ms 51 記憶體限制: 64 MB 52 代碼長度限制: 16 KB 53 題目詳情 54 7-3 統計字符 (20分) 55 統計一個給定字串中指定的字符出現的次數， 56 輸入格式: 57 測驗輸入包含若干測驗用例，每個測驗用例包含2行，第1行為一個長度不超過5的字串，第2行為一個長度不超過80的字串，注意這里的字串包含空格，即空格也可能是要求被統計的字符之一，當讀到'#'時輸入結束，相應的結果不要輸出， 58 輸出格式: 59 對每個測驗用例，統計第1行中字串的每個字符在第2行字串中出現的次數，按如下格式輸出： c n0 60 c1 n1 61 c2 n2 62 ... 63 其中ci是第1行中第i個字符，ni是ci出現的次數， 64 輸入樣例: 65 66 I 67 THIS IS A TEST 68 i ng 69 this is a long test string 70 # 71 輸出樣例: 72 73 I 2 74 i 3 75 5 76 n 2 77 g 2 78 樣例解釋: 79 第2個測驗用例中，空格也是被統計的字符之一， 80 作者: 李廷元 81 單位: 中國民用航空飛行學院 82 時間限制: 400 ms 83 記憶體限制: 64 MB 84 代碼長度限制: 16 KB 85 題目詳情 86 87 7-4 禮尚往來 (20分) 88 吉哥還是那個吉哥,那個江湖人稱“嘰嘰哥”的基哥，每當節日來臨，女友眾多的嘰嘰哥總是能從全國各地的女友那里收到各種禮物，有禮物收到當然值得高興，但回禮確是件麻煩的事！無論多麻煩，總不好意思收禮而不回禮，那也不是嘰嘰哥的風格，現在，即愛面子又摳門的嘰嘰哥想出了一個絕妙的好辦法：他準備將各個女友送來的禮物合理分配，再回送不同女友，這樣就不用再花錢買禮物了！假設嘰嘰哥的n個女友每人送他一個禮物（每個人送的禮物都不相同），現在他需要合理安排，再回送每個女友一份禮物，重點是，回送的禮物不能是這個女友之前送他的那個禮物，不然，嘰嘰哥可就攤上事了，攤上大事了......現在，嘰嘰哥想知道總共有多少種滿足條件的回送禮物方案呢？ 89 輸入格式: 90 輸入資料第一行是個正整數T，表示總共有T組測驗資料（T <= 100）； 每組資料包含一個正整數n，表示嘰嘰哥的女友個數為n( 1 <= n <= 100 )， 91 輸出格式: 92 請輸出可能的方案數，因為方案數可能比較大，請將結果對1000000007 取模后再輸出，（提示：在遞推程序中，不斷求余防止資料太大導致資料溢位，） 每組輸出占一行， 93 輸入樣例: 94 95 3 96 1 97 2 98 4 99 100 輸出樣例: 101 102 0 103 1 104 9 105 106 107 作者: hcx11333 108 單位: 山東大學（威海） 109 時間限制: 1000 ms 110 記憶體限制: 64 MB 111 代碼長度限制: 16 KB 112 題目詳情 113 114 7-5 找單詞 (20分) 115 假設有x1個字母A， x2個字母B,..... x26個字母Z，同時假設字母A的價值為1，字母B的價值為2,..... 字母Z的價值為26，那么，對于給定的字母，可以找到多少價值<=50的單詞呢？單詞的價值就是組成一個單詞的所有字母的價值之和，比如，單詞ACM的價值是1+3+14=18，單詞HDU的價值是8+4+21=33，(組成的單詞與排列順序無關，比如ACM與CMA認為是同一個單詞）， 116 輸入格式: 117 輸入首先是一個整數N，代表測驗實體的個數， 然后包括N行資料，每行包括26個<=20的整數x1,x2,.....x26. 118 輸出格式: 119 對于每個測驗實體，請輸出能找到的總價值<=50的單詞數,每個實體的輸出占一行， 120 輸入樣例: 121 122 2 123 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 124 9 2 6 2 10 2 2 5 6 1 0 2 7 0 2 2 7 5 10 6 10 2 10 6 1 9 125 126 輸出樣例: 127 在這里給出相應的輸出，例如： 128 129 7 130 379297 131 132 133 作者: hcx11333 134 單位: 山東大學（威海） 135 時間限制: 1000 ms 136 記憶體限制: 64 MB 137 代碼長度限制: 16 KB 138 題目詳情 139 140 7-6 求最大元素值 (30分) 141 n個元素的陣列的最大元素可以用遞回計算出來， 定義方法：int max(int x, int y) 它回傳x和y兩個整數中的較大值， 試用遞回撰寫方法：int arraymax(int[] a, int n) 它使用遞回回傳陣列a的最大元素值， 終止條件：n==2 遞回步驟：arraymax=max(max(a[0],...,a[n-2]), a[n-1]) 142 輸入格式: 143 第一行的第一個元素是輸入元素個數n (1<n<=30)，第二個元素之后是輸入n個元素； 144 輸出格式: 145 按格式要求輸出相鄰兩個元素的最大值，例如輸出的第一項是a[0]和a[1]之間的最大值；第二項為之前的最大值與a[2]之間的最大值，依次類推，直到最后輸出n個元素陣列的最大元素值， 146 輸入樣例: 147 148 5 1 3 2 5 3 149 輸出樣例: 150 151 max(1,3)=3 max(3,2)=3 max(3,5)=5 max(5,3)=5 5 152 153 作者: 林華 154 單位: 廣東外語外貿大學 155 000題目詳情 156 157 7-7 求最大公約數 (30分) 158 使用輾轉相除法和遞回求兩個正整數m和n的最大公約數， 159 輸入格式: 160 輸入兩個正整數m,n， 161 輸出格式: 162 按要求輸出輾轉相除程序及最終結果，輸出結果之間空格分隔， 163 輸入樣例: 164 165 21 35 166 輸出樣例: 167 168 gcd(21,35) gcd(35,21) gcd(21,14) gcd(14,7) 7 169 170 作者: 林華 171 單位: 廣東外語外貿大學 172 000題目詳情 173 174 7-8 找第k小的數 (20分) 175 設計一個平均時間為O(n)的演算法，在n(1<=n<=1000)個無序的整數中找出第k小的數， 176 提示：函式int partition(int a[],int left,int right)的功能是根據a[left]~a[right]中的某個元素x（如a[left])對a[left]~a[right]進行劃分，劃分后的x所在位置的左段全小于等于x,右段全大于等于x,同時利用x所在的位置還可以計算出x是這批資料按升非降序排列的第幾個數，因此可以編制int find(int a[],int left,int right,int k)函式，通過呼叫partition函式獲得劃分點，判斷劃分點是否第k小，若不是，遞回呼叫find函式繼續在左段或右段查找， 177 輸入格式: 178 輸入有兩行： 179 第一行是n和k，0<k<=n<=10000 180 第二行是n個整數 181 輸出格式: 182 輸出第k小的數 183 輸入樣例: 184 在這里給出一組輸入，例如： 185 186 10 4 187 2 8 9 0 1 3 6 7 8 2 188 輸出樣例: 189 在這里給出相應的輸出，例如： 190 191 2 192 193 作者: 陳曉梅 194 單位: 廣東外語外貿大學 195 時間限制: 400 ms 196 記憶體限制: 64 MB 197 代碼長度限制: 16 KB 198 題目詳情 199 200 7-9 求逆序對數目 (20分) 201 注意：本問題演算法的時間復雜度要求為O(nlogn), 否則得分無效 202 題目來源：http://poj.org/problem?id=1804 Background Raymond Babbitt drives his brother Charlie mad. Recently Raymond counted 246 toothpicks spilled all over the floor in an instant just by glancing at them. And he can even count Poker cards. Charlie would love to be able to do cool things like that, too. He wants to beat his brother in a similar task. 203 Problem Here's what Charlie thinks of. Imagine you get a sequence of N numbers. The goal is to move the numbers around so that at the end the sequence is ordered. The only operation allowed is to swap two adjacent numbers. Let us try an example: Start with: 2 8 0 3 swap (2 8) 8 2 0 3 swap (2 0) 8 0 2 3 swap (2 3) 8 0 3 2 swap (8 0) 0 8 3 2 swap (8 3) 0 3 8 2 swap (8 2) 0 3 2 8 swap (3 2) 0 2 3 8 swap (3 8) 0 2 8 3 swap (8 3) 0 2 3 8 204 So the sequence (2 8 0 3) can be sorted with nine swaps of adjacent numbers. However, it is even possible to sort it with three such swaps: Start with: 2 8 0 3 swap (8 0) 2 0 8 3 swap (2 0) 0 2 8 3 swap (8 3) 0 2 3 8 205 The question is: What is the minimum number of swaps of adjacent numbers to sort a given sequence?Since Charlie does not have Raymond's mental capabilities, he decides to cheat. Here is where you come into play. He asks you to write a computer program for him that answers the question in O(nlogn). Rest assured he will pay a very good prize for it. 206 輸入格式: 207 The first line contains the length N (1 <= N <= 1000) of the sequence； The second line contains the N elements of the sequence (each element is an integer in [-1000000, 1000000]). All numbers in this line are separated by single blanks. 208 輸出格式: 209 Print a single line containing the minimal number of swaps of adjacent numbers that are necessary to sort the given sequence. 210 輸入樣例: 211 在這里給出一組輸入，例如： 212 213 6 214 -42 23 6 28 -100 65537 215 輸出樣例: 216 在這里給出相應的輸出，例如： 217 218 5 219 220 作者: 陳曉梅 221 單位: 廣東外語外貿大學 222 時間限制: 400 ms 223 記憶體限制: 64 MB 224 代碼長度限制: 16 KB 225 題目詳情 226 227 7-10 裝箱問題 (20分) 228 假設有N項物品，大小分別為s1、s2、…、si、…、sN，其中si為滿足1≤si≤100的整數，要把這些物品裝入到容量為100的一批箱子（序號1-N）中，裝箱方法是：對每項物品, 順序掃描箱子，把該物品放入足以能夠容下它的第一個箱子中，請寫一個程式模擬這種裝箱程序，并輸出每個物品所在的箱子序號，以及放置全部物品所需的箱子數目， 229 輸入格式： 230 輸入第一行給出物品個數N（≤1000）；第二行給出N個正整數si（1≤si≤100，表示第i項物品的大小）， 231 輸出格式： 232 按照輸入順序輸出每個物品的大小及其所在的箱子序號，每個物品占1行，最后一行輸出所需的箱子數目， 233 輸入樣例： 234 235 8 236 60 70 80 90 30 40 10 20 237 輸出樣例： 238 239 60 1 240 70 2 241 80 3 242 90 4 243 30 1 244 40 5 245 10 1 246 20 2 247 5 248 249 作者: DS課程組 250 單位: 浙江大學 251 時間限制: 400 ms 252 記憶體限制: 64 MB 253 代碼長度限制: 16 KB 254 題目詳情 255 256 7-11 汽車加油問題 (20分) 257 題目來源：王曉東《演算法設計與分析》 258 一輛汽車加滿油后可行駛 n公里，旅途中有若干個加油站，設計一個有效演算法，指出應 在哪些加油站停靠加油，使沿途加油次數最少， 259 輸入格式: 260 第一行有 2 個正整數n和 k（k<=1000 )，表示汽車加滿油后可行駛n公里，且旅途中有 k個加油站， 第二行有 k+1 個整數，表示第 k 個加油站與第k-1 個加油站之間的距離， 第 0 個加油站表示出發地，汽車已加滿油， 第 k+1 個加油站表示目的地， 261 輸出格式: 262 輸出最少加油次數，如果無法到達目的地，則輸出“No Solution!”， 263 輸入樣例: 264 265 7 7 266 1 2 3 4 5 1 6 6 267 輸出樣例: 268 269 4 270 271 作者: 陳曉梅 272 單位: 廣東外語外貿大學 273 時間限制: 400 ms 274 記憶體限制: 64 MB 275 代碼長度限制: 16 KB 276 題目詳情 277 278 7-12 會場安排問題 (20分) 279 題目來源：王曉東《演算法設計與分析》 280 假設要在足夠多的會場里安排一批活動，并希望使用盡可能少的會場，設計一個有效的 貪心演算法進行安排，（這個問題實際上是著名的圖著色問題，若將每一個活動作為圖的一個 頂點，不相容活動間用邊相連，使相鄰頂點著有不同顏色的最小著色數，相應于要找的最小 會場數，） 281 輸入格式: 282 第一行有 1 個正整數k，表示有 k個待安排的活動， 接下來的 k行中，每行有 2個正整數，分別表示 k個待安排的活動開始時間和結束時間，時間 以 0 點開始的分鐘計， 283 輸出格式: 284 輸出最少會場數， 285 輸入樣例: 286 287 5 288 1 23 289 12 28 290 25 35 291 27 80 292 36 50 293 輸出樣例: 294 在這里給出相應的輸出，例如： 295 296 3 297 298 作者: 陳曉梅 299 單位: 廣東外語外貿大學 300 時間限制: 400 ms 301 記憶體限制: 64 MB 302 代碼長度限制: 16 KB 303 題目詳情 304 305 7-13 最優合并問題 (20分) 306 題目來源：王曉東《演算法設計與分析》 307 給定k 個排好序的序列, 用 2 路合并演算法將這k 個序列合并成一個序列， 假設所采用的 2 路合并演算法合并 2 個長度分別為m和n的序列需要m+n-1 次比較，試設 計一個演算法確定合并這個序列的最優合并順序，使所需的總比較次數最少， 為了進行比較，還需要確定合并這個序列的最差合并順序，使所需的總比較次數最多， 308 輸入格式: 309 第一行有 1 個正整數k，表示有 k個待合并序列， 第二行有 k個正整數，表示 k個待合并序列的長度， 310 輸出格式: 311 輸出最多比較次數和最少比較次數， 312 輸入樣例: 313 在這里給出一組輸入，例如： 314 315 4 316 5 12 11 2 317 輸出樣例: 318 在這里給出相應的輸出，例如： 319 320 78 52 321 322 作者: 陳曉梅 323 單位: 廣東外語外貿大學 324 時間限制: 400 ms 325 記憶體限制: 64 MB 326 代碼長度限制: 16 KB 327 題目詳情 328 329 7-14 看電影 (20分) 330 終于到周末了，明明是特別喜歡看電影，他想在一天內盡量多的看到完整的多部電影， 現在他把他喜歡的電影的播放時間表給你，希望你能幫他合理安排， 331 輸入格式: 332 輸入包含多組測驗資料，每組輸入的第一行是一個整數n（n<=100），表示明明喜歡的電影的總數， 接下來n行，每行輸入兩個整數si和ei（1<=i<=n），表示第i個電影的開始和結束時間，為了簡化問題，每個時間都用一個正整數表示， 當n=0時，輸入結束， 333 輸出格式: 334 對于每組輸入，輸出能完整看到的電影的個數， 335 輸入樣例: 336 在這里給出一組輸入，例如： 337 338 12 339 1 3 340 3 4 341 0 7 342 3 8 343 15 19 344 15 20 345 10 15 346 8 18 347 6 12 348 5 10 349 4 14 350 2 9 351 0 352 輸出樣例: 353 在這里給出相應的輸出，例如： 354 355 5 356 357 作者: 投訓勇 358 單位: 河北科技大學 359 時間限制: 1000 ms 360 記憶體限制: 32 MB 361 代碼長度限制: 16 KB 362 題目詳情 363 364 7-15 最近距離 (30分) 365 在一個游戲中，玩家處于一個如下所示12行12列的迷宮： 366 0,1,0,0,0,1,1,1,0,1,0,1 367 0,0,0,1,0,0,0,0,1,0,0,1 368 0,1,0,1,0,1,1,1,0,1,0,0 369 0,1,0,0,0,0,0,1,0,0,1,1 370 0,0,0,0,1,0,0,0,0,0,0,0 371 0,0,1,0,0,0,1,0,0,0,1,0 372 0,0,1,0,0,0,0,0,1,0,0,0 373 1,0,0,1,0,1,0,0,0,1,0,1 374 0,0,1,0,1,0,1,0,1,0,0,0 375 0,0,0,0,0,1,0,0,0,1,1,0 376 0,0,0,0,0,1,0,0,0,0,0,0 377 0,1,0,1,0,0,0,1,0,1,0,0 378 其中迷宮由0,1組成，0表示道路，1表示障礙物， 379 現在要根據玩家和游戲中被攻擊的虛擬boss所在位置，給玩家以最近距離的提示， 380 最近距離：即玩家走到boss所走的最少步數，（注：路線中的一步是指從一個坐標點走到其上下左右相鄰坐標點，） 381 輸入格式: 382 輸入4個整數a,b,c,d（即玩家和虛擬boss在迷宮中的坐標位置分別為(a,b) 、(c,d)）， 其中 0<=a,b,c,d<12， 383 輸出格式: 384 輸出在迷宮中從(a,b)出發到達(c,d)的最少步數，如果(a,b)永遠無法到達(c,d)則輸出10000， 385 輸入樣例: 386 在這里給出一組輸入，例如： 387 388 0 0 11 11 389 輸出樣例: 390 在這里給出相應的輸出，例如： 391 392 22 393 394 作者: 高見元 395 單位: 湖北經濟學院 396 時間限制: 1000 ms 397 記憶體限制: 64 MB 398 代碼長度限制: 16 KB 399 題目詳情 400 401 7-16 子集和問題 (30分) 402 設集合S={x1,x2,…,xn}是一個正整數集合，c是一個正整數，子集和問題判定是否存在S的一個子集S1，使S1中的元素之和為c，試設計一個解子集和問題的回溯法， 403 輸入格式: 404 輸入資料第1行有2個正整數n和c，n表示S的大小，c是子集和的目標值，接下來的1行中，有n個正整數，表示集合S中的元素， 是子集和的目標值，接下來的1 行中，有n個正整數，表示集合S中的元素， 405 輸出格式: 406 輸出子集和問題的解，以空格分隔，最后一個輸出的后面有空格，當問題無解時，輸出“No Solution!”， 407 輸入樣例: 408 在這里給出一組輸入，例如： 409 410 5 10 411 2 2 6 5 4 412 輸出樣例: 413 在這里給出相應的輸出，例如： 414 415 2 2 6 416 417 作者: 陳曉梅 418 單位: 廣東外語外貿大學 419 時間限制: 400 ms 420 記憶體限制: 64 MB 421 代碼長度限制: 16 KB 422 題目詳情 423 424 7-17 最佳調度問題 (35分) 425 假設有n（n<=20）個任務由k（k<=20）個可并行作業的機器完成，完成任務i需要的時間為ti， 試設計一個演算法，對任意給定的整數n和k，以及完成任務i 需要的時間為ti ，i=1~n，計算完成這n個任務的最佳調度，使得完成全部任務的時間最早， 426 輸入格式: 427 輸入資料的第一行有2 個正整數n和k，第2 行的n個正整數是完成n個任務需要的時間， 428 輸出格式: 429 將計算出的完成全部任務的最早時間輸出到螢屏， 430 輸入樣例: 431 在這里給出一組輸入，例如： 432 433 7 3 434 2 14 4 16 6 5 3 435 輸出樣例: 436 在這里給出相應的輸出，例如： 437 438 17 439 440 作者: 陳曉梅 441 單位: 廣東外語外貿大學 442 時間限制: 400 ms 443 記憶體限制: 64 MB 444 代碼長度限制: 16 KB 445 題目詳情 446 447 7-18 找零錢*** (20分) 448 收銀員現有 n 張面值分別為 v1,v2,...,vn 的紙幣，若找零金額為 m，則一共有多少種找零方法？ 449 注：0<n≤1000，0<v1,v2,...,vn≤10000，0<m≤10000 450 輸入格式 451 n v1,v2,...,vn m 452 輸出格式 453 若有解，則輸出全部找零方案，每輸出一種 若無解，則輸出“None” 454 輸入樣例1 455 456 6 457 3 1 4 3 2 7 458 9 459 輸出樣例1 460 461 3 1 3 2 462 3 4 2 463 4 3 2 464 2 7 465 輸入樣例2 466 467 5 468 5 3 4 6 7 469 2 470 輸出樣例2 471 472 None 473 474 作者: 李祥 475 單位: 湖北經濟學院 476 時間限制: 400 ms 477 記憶體限制: 64 MB 478 代碼長度限制: 16 KB 479 題目詳情 480 481 7-19 作業分配問題 (20分) 482 設有n件作業分配給n個人，將作業i分配給第j個人所需的費用為cij ， 設計一個演算法，對于給定的作業費用，為每一個人都分配1 件不同的作業，并使總費用達到最小， 483 輸入格式: 484 輸入資料的第一行有1 個正整數n (1≤n≤20)，接下來的n行，每行n個數，表示作業費用， 485 輸出格式: 486 將計算出的最小總費用輸出到螢屏， 487 輸入樣例: 488 在這里給出一組輸入，例如： 489 490 3 491 10 2 3 492 2 3 4 493 3 4 5 494 輸出樣例: 495 在這里給出相應的輸出，例如： 496 497 9 498 499 作者: 陳曉梅 500 單位: 廣東外語外貿大學 501 時間限制: 400 ms 502 記憶體限制: 64 MB 503 代碼長度限制: 16 KB 504 題目詳情 505 506 7-20 單調遞增最長子序列 (20分) 507 設計一個O(n2)時間的演算法，找出由n個陣列成的序列的最長單調遞增子序列， 508 輸入格式: 509 輸入有兩行： 第一行：n，代表要輸入的數列的個數 第二行：n個數，數字之間用空格格開 510 輸出格式: 511 最長單調遞增子序列的長度 512 輸入樣例: 513 在這里給出一組輸入，例如： 514 515 5 516 1 3 5 2 9 517 輸出樣例: 518 在這里給出相應的輸出，例如： 519 520 4 521 522 作者: 陳曉梅 523 單位: 廣東外語外貿大學 524 時間限制: 400 ms 525 記憶體限制: 64 MB 526 代碼長度限制: 16 KB 527 題目詳情 528 529 7-21 回文串問題 (40分) 530 一個字串，如果從左到右讀和從右到左讀是完全一樣的，比如"aba"，我們稱其為回文串，現在給你一個字串，可在任意位置添加字符，求最少添加幾個字符，才能使其變成一個回文串， 531 輸入格式: 532 任意給定的一個字串，其長度不超過1000. 533 輸出格式: 534 能變成回文串所需添加的最少字符數， 535 輸入樣例: 536 在這里給出一組輸入，例如： 537 538 Ab3bd 539 540 Abb 541 輸出樣例: 542 在這里給出相應的輸出，例如： 543 544 2 545 546 1 547 548 作者: 高見元 549 單位: 湖北經濟學院 550 時間限制: 1000 ms 551 記憶體限制: 64 MB 552 代碼長度限制: 16 KB 553 題目詳情 554 555 7-22 最大子段和 (20分) 556 給定n個整數（可能為負數）組成的序列a[1],a[2],a[3],…,a[n]，求該序列如a[i]+a[i+1]+…+a[j]的子段和的最大值，當所給的整數均為負數時，定義子段和為0， 557 要求演算法的時間復雜度為O(n)， 558 輸入格式: 559 輸入有兩行： 560 第一行是n值（1<=n<=10000)； 561 第二行是n個整數， 562 輸出格式: 563 輸出最大子段和， 564 輸入樣例: 565 在這里給出一組輸入，例如： 566 567 6 568 -2 11 -4 13 -5 -2 569 輸出樣例: 570 在這里給出相應的輸出，例如： 571 572 20 573 574 作者: 陳曉梅 575 單位: 廣東外語外貿大學 576 時間限制: 400 ms 577 記憶體限制: 64 MB 578 代碼長度限制: 16 KB 579 題目詳情 580 581 7-23 整數拆分 (20分) 582 給定一個整數n，將其無序拆分成最大數為k的拆分數，（n,k不超出100） 要求：所有的拆分方案不重復， 如當n=4,k=4時，一共有5種拆分方案，拆分如下： 583 584 (1)4=1+1+1+1 585 (2)4=1+1+2 586 (3)4=1+3 587 (4)4=2+2 588 (5)4=4 589 輸入格式: 590 每一行輸入一組整數n,k，遇到鍵盤結束符^Z或檔案結束符EOF時結束輸入， 591 輸出格式: 592 按行輸出每組的拆分方案數， 593 輸入樣例: 594 595 4,4 596 5,4 597 輸出樣例: 598 599 5 600 6 601 602 作者: 張慶 603 單位: 集美大學 604 時間限制: 400 ms 605 記憶體限制: 64 MB 606 代碼長度限制: 16 KB 607 題目詳情 608 609 7-24 青蛙跳臺階 (30分) 610 一只青蛙一次可以跳上 1 級臺階，也可以跳上2 級，求該青蛙跳上一個n 級的臺階總共有多少種跳法， 611 輸入格式: 612 首先輸入數字n，代表接下來有n組輸入，50>=n>=0,然后每行一個數字，代表臺階數，數字為小于60的整數 613 輸出格式: 614 對每一組輸入，輸出青蛙的跳法， 615 輸入樣例: 616 617 3 618 1 619 2 620 3 621 輸出樣例: 622 623 1 624 2 625 3 626 627 作者: 房正華 628 單位: 青島工學院 629 時間限制: 400 ms 630 記憶體限制: 64 MB 631 代碼長度限制: 16 KB 632 題目詳情 633 634 7-25 朋友圈 (30分) 635 某學校有N個學生，形成M個俱樂部，每個俱樂部里的學生有著一定相似的興趣愛好，形成一個朋友圈，一個學生可以同時屬于若干個不同的俱樂部，根據“我的朋友的朋友也是我的朋友”這個推論可以得出，如果A和B是朋友，且B和C是朋友，則A和C也是朋友，請撰寫程式計算最大朋友圈中有多少人， 636 輸入格式: 637 輸入的第一行包含兩個正整數N（≤30000）和M（≤1000），分別代表學校的學生總數和俱樂部的個數，后面的M行每行按以下格式給出1個俱樂部的資訊，其中學生從1~N編號： 638 639 第i個俱樂部的人數Mi（空格）學生1（空格）學生2 … 學生Mi 640 641 輸出格式: 642 輸出給出一個整數，表示在最大朋友圈中有多少人， 643 輸入樣例: 644 645 7 4 646 3 1 2 3 647 2 1 4 648 3 5 6 7 649 1 6 650 輸出樣例: 651 652 4 653 654 作者: DS課程組 655 單位: 浙江大學 656 時間限制: 400 ms 657 記憶體限制: 64 MB 658 代碼長度限制: 16 KB 659 題目詳情 660 661 7-26 愿天下有情人都是失散多年的兄妹 (30分) 662 呵呵，大家都知道五服以內不得通婚，即兩個人最近的共同祖先如果在五代以內（即本人、父母、祖父母、曾祖父母、高祖父母）則不可通婚，本題就請你幫助一對有情人判斷一下，他們究竟是否可以成婚？ 663 輸入格式： 664 輸入第一行給出一個正整數 665 N 666 （2 ≤ 667 N 668 ≤104），隨后 669 N 670 行，每行按以下格式給出一個人的資訊： 671 672 本人ID 性別 父親ID 母親ID 673 其中 674 ID 675 是5位數字，每人不同；性別 676 M 677 代表男性、 678 F 679 代表女性，如果某人的父親或母親已經不可考，則相應的 680 ID 681 位置上標記為 682 -1 683 ， 684 接下來給出一個正整數 685 K 686 ，隨后 687 K 688 行，每行給出一對有情人的 689 ID 690 ，其間以空格分隔， 691 注意：題目保證兩個人是同輩，每人只有一個性別，并且血緣關系網中沒有亂倫或隔輩成婚的情況， 692 輸出格式： 693 對每一對有情人，判斷他們的關系是否可以通婚：如果兩人是同性，輸出 694 Never Mind 695 ；如果是異性并且關系出了五服，輸出 696 Yes 697 ；如果異性關系未出五服，輸出 698 No 699 ， 700 輸入樣例： 701 702 24 703 00001 M 01111 -1 704 00002 F 02222 03333 705 00003 M 02222 03333 706 00004 F 04444 03333 707 00005 M 04444 05555 708 00006 F 04444 05555 709 00007 F 06666 07777 710 00008 M 06666 07777 711 00009 M 00001 00002 712 00010 M 00003 00006 713 00011 F 00005 00007 714 00012 F 00008 08888 715 00013 F 00009 00011 716 00014 M 00010 09999 717 00015 M 00010 09999 718 00016 M 10000 00012 719 00017 F 012 720 000 F 110 00013 721 00019 F 11100 00018 722 00020 F 00015 11110 723 00021 M 11100 00020 724 00022 M 00016 -1 725 00023 M 10012 00017 726 00024 M 00022 10013 727 9 728 00021 00024 729 00019 00024 730 00011 00012 731 00022 00018 732 00001 00004 733 00013 00016 734 00017 00015 735 00019 00021 736 00010 00011 737 輸出樣例： 738 739 Never Mind 740 Yes 741 Never Mind 742 No 743 Yes 744 No 745 Yes 746 No 747 No 748 749 作者: 陳越 750 單位: 浙江大學 751 時間限制: 200 ms 752 記憶體限制: 64 MB 753 代碼長度限制: 16 KB 754 題目詳情 755 756 7-27 列出所有祖先結點 (20分) 757 對于給定的二叉樹，本題要求你按從上到下順序輸出指定結點的所有祖先結點， 758 輸入格式: 759 首先第一行給出一個正整數 N（≤10），為樹中結點總數，樹中的結點從 0 到 N?1 編號， 760 隨后 N 行，每行給出一個對應結點左右孩子的編號，如果某個孩子不存在，則在對應位置給出 "-"，編號間以 1 個空格分隔， 761 最后一行給出一個結點的編號i（0≤i≤N-1）， 762 輸出格式: 763 在一行中按規定順序輸出i的所有祖先結點的編號，編號間以 1 個空格分隔，行首尾不得有多余空格， 764 輸入樣例: 765 766 7 767 2 - 768 - 6 769 - - 770 0 5 771 - - 772 4 1 773 - - 774 4 775 輸出樣例: 776 777 3 5 778 779 作者: DS課程組 780 單位: 臨沂大學 781 時間限制: 400 ms 782 記憶體限制: 64 MB 783 代碼長度限制: 16 KB 784 題目詳情 785 786 7-28 深入虎穴 (35分) 787 著名的王牌間諜 007 需要執行一次任務，獲取敵方的機密情報，已知情報藏在一個地下迷宮里，迷宮只有一個入口，里面有很多條通路，每條路通向一扇門，每一扇門背后或者是一個房間，或者又有很多條路，同樣是每條路通向一扇門…… 他的手里有一張表格，是其他間諜幫他收集到的情報，他們記下了每扇門的編號，以及這扇門背后的每一條通路所到達的門的編號，007 發現不存在兩條路通向同一扇門， 788 內線告訴他，情報就藏在迷宮的最深處，但是這個迷宮太大了，他需要你的幫助 —— 請編程幫他找出距離入口最遠的那扇門， 789 輸入格式： 790 輸入首先在一行中給出正整數 N（<105），是門的數量，最后 N 行，第 i 行（1≤i≤N）按以下格式描述編號為 i 的那扇門背后能通向的門： 791 792 K D[1] D[2] ... D[K] 793 其中 794 K 795 是通道的數量，其后是每扇門的編號， 796 輸出格式： 797 在一行中輸出距離入口最遠的那扇門的編號，題目保證這樣的結果是唯一的， 798 輸入樣例： 799 800 13 801 3 2 3 4 802 2 5 6 803 1 7 804 1 8 805 1 9 806 0 807 2 11 10 808 1 13 809 0 810 0 811 1 12 812 0 813 0 814 輸出樣例： 815 816 12 817 818 作者: 陳越 819 單位: 浙江大學 820 時間限制: 400 ms 821 記憶體限制: 64 MB 822 代碼長度限制: 16 KB 823 題目詳情 824 825 7-29 城市間緊急救援 (25分) 826 作為一個城市的應急救援隊伍的負責人，你有一張特殊的全國地圖，在地圖上顯示有多個分散的城市和一些連接城市的快速道路，每個城市的救援隊數量和每一條連接兩個城市的快速道路長度都標在地圖上，當其他城市有緊急求助電話給你的時候，你的任務是帶領你的救援隊盡快趕往事發地，同時，一路上召集盡可能多的救援隊， 827 輸入格式: 828 輸入第一行給出4個正整數N、M、S、D，其中N（2≤N≤500）是城市的個數，順便假設城市的編號為0 ~ (N?1)；M是快速道路的條數；S是出發地的城市編號；D是目的地的城市編號， 829 第二行給出N個正整數，其中第i個數是第i個城市的救援隊的數目，數字間以空格分隔，隨后的M行中，每行給出一條快速道路的資訊，分別是：城市1、城市2、快速道路的長度，中間用空格分開，數字均為整數且不超過500，輸入保證救援可行且最優解唯一， 830 輸出格式: 831 第一行輸出最短路徑的條數和能夠召集的最多的救援隊數量，第二行輸出從S到D的路徑中經過的城市編號，數字間以空格分隔，輸出結尾不能有多余空格， 832 輸入樣例: 833 834 4 5 0 3 835 20 30 40 10 836 0 1 1 837 1 3 2 838 0 3 3 839 0 2 2 840 2 3 2 841 輸出樣例: 842 843 2 60 844 0 1 3 845 846 作者: 陳越 847 單位: 浙江大學 848 時間限制: 400 ms 849 記憶體限制: 64 MB 850 代碼長度限制: 16 KB 851 題目詳情 852 853 7-30 紅色警報 (25分) 854 戰爭中保持各個城市間的連通性非常重要，本題要求你撰寫一個報警程式，當失去一個城市導致國家被分裂為多個無法連通的區域時，就發出紅色警報，注意：若該國本來就不完全連通，是分裂的k個區域，而失去一個城市并不改變其他城市之間的連通性，則不要發出警報， 855 輸入格式： 856 輸入在第一行給出兩個整數 857 N 858 （0 < 859 N 860 ≤ 500）和 861 M 862 （≤ 5000），分別為城市個數（于是默認城市從0到 863 N 864 -1編號）和連接兩城市的通路條數，隨后 865 M 866 行，每行給出一條通路所連接的兩個城市的編號，其間以1個空格分隔，在城市資訊之后給出被攻占的資訊，即一個正整數 867 K 868 和隨后的 869 K 870 個被攻占的城市的編號， 871 注意：輸入保證給出的被攻占的城市編號都是合法的且無重復，但并不保證給出的通路沒有重復， 872 輸出格式： 873 對每個被攻占的城市，如果它會改變整個國家的連通性，則輸出 874 Red Alert: City k is lost! 875 ，其中 876 k 877 是該城市的編號；否則只輸出 878 City k is lost. 879 即可，如果該國失去了最后一個城市，則增加一行輸出 880 Game Over. 881 ， 882 輸入樣例： 883 884 5 4 885 0 1 886 1 3 887 3 0 888 0 4 889 5 890 1 2 0 4 3 891 輸出樣例： 892 893 City 1 is lost. 894 City 2 is lost. 895 Red Alert: City 0 is lost! 896 City 4 is lost. 897 City 3 is lost. 898 Game Over. 899 900 作者: 陳越 901 單位: 浙江大學 902 時間限制: 400 ms 903 記憶體限制: 64 MB 904 代碼長度限制: 16 KB 905 題目詳情 906 907 7-31 拯救007（升級版） (30分) 908 在老電影“007之生死關頭”（Live and Let Die）中有一個情節，007被毒販抓到一個鱷魚池中心的小島上，他用了一種極為大膽的方法逃脫 —— 直接踩著池子里一系列鱷魚的大腦袋跳上岸去！（據說當年替身演員被最后一條鱷魚咬住了腳，幸好穿的是特別加厚的靴子駁過一劫，） 909 設鱷魚池是長寬為100米的方形，中心坐標為 (0, 0)，且東北角坐標為 (50, 50)，池心島是以 (0, 0) 為圓心、直徑15米的圓，給定池中分布的鱷魚的坐標、以及007一次能跳躍的最大距離，你需要給他指一條最短的逃生路徑 —— 所謂“最短”是指007要跳躍的步數最少， 910 輸入格式： 911 首先第一行給出兩個正整數：鱷魚數量 N（≤100）和007一次能跳躍的最大距離 D，隨后 N 行，每行給出一條鱷魚的 (x,y) 坐標，注意：不會有兩條鱷魚待在同一個點上， 912 輸出格式： 913 如果007有可能逃脫，首先在第一行輸出007需要跳躍的最少步數，然后從第二行起，每行給出從池心島到岸邊每一步要跳到的鱷魚的坐標 (x,y)，如果沒可能逃脫，就在第一行輸出 0 作為跳躍步數，如果最短路徑不唯一，則輸出第一跳最近的那個解，題目保證這樣的解是唯一的， 914 輸入樣例 1： 915 916 17 15 917 10 -21 918 10 21 919 -40 10 920 30 -50 921 20 40 922 35 10 923 0 -10 924 -25 22 925 40 -40 926 -30 30 927 -10 22 928 0 11 929 25 21 930 25 10 931 10 10 932 10 35 933 -30 10 934 輸出樣例 1： 935 936 4 937 0 11 938 10 21 939 10 35 940 輸入樣例 2： 941 942 4 13 943 -12 12 944 12 12 945 -12 -12 946 12 -12 947 輸出樣例 2： 948 949 0 950 951 作者: 陳越 952 單位: 浙江大學 953 時間限制: 400 ms 954 記憶體限制: 64 MB 955 代碼長度限制: 16 KB 956 題目詳情 957 958 7-32 直搗黃龍 (30分) 959 本題是一部戰爭大片 —— 你需要從己方大本營出發，一路攻城略地殺到敵方大本營，首先時間就是生命，所以你必須選擇合適的路徑，以最快的速度占領敵方大本營，當這樣的路徑不唯一時，要求選擇可以沿途解放最多城鎮的路徑，若這樣的路徑也不唯一，則選擇可以有效殺傷最多敵軍的路徑， 960 輸入格式： 961 輸入第一行給出 2 個正整數 N（2 ≤ N ≤ 200，城鎮總數）和 K（城鎮間道路條數），以及己方大本營和敵方大本營的代號，隨后 N-1 行，每行給出除了己方大本營外的一個城鎮的代號和駐守的敵軍數量，其間以空格分隔，再后面有 K 行，每行按格式 962 城鎮1 城鎮2 距離 963 給出兩個城鎮之間道路的長度，這里設每個城鎮（包括雙方大本營）的代號是由 3 個大寫英文字母組成的字串， 964 輸出格式： 965 按照題目要求找到最合適的進攻路徑（題目保證速度最快、解放最多、殺傷最強的路徑是唯一的），并在第一行按照格式 966 己方大本營->城鎮1->...->敵方大本營 967 輸出，第二行順序輸出最快進攻路徑的條數、最短進攻距離、殲敵總數，其間以 1 個空格分隔，行首尾不得有多余空格， 968 輸入樣例： 969 970 10 12 PAT DBY 971 DBY 100 972 PTA 20 973 PDS 90 974 PMS 40 975 TAP 50 976 ATP 200 977 LNN 80 978 LAO 30 979 LON 70 980 PAT PTA 10 981 PAT PMS 10 982 PAT ATP 20 983 PAT LNN 10 984 LNN LAO 10 985 LAO LON 10 986 LON DBY 10 987 PMS TAP 10 988 TAP DBY 10 989 DBY PDS 10 990 PDS PTA 10 991 DBY ATP 10 992 輸出樣例： 993 994 PAT->PTA->PDS->DBY 995 3 30 210 996 997 作者: 陳越 998 單位: 浙江大學 999 時間限制: 150 ms 1000 記憶體限制: 64 MB 1001 代碼長度限制: 16 KB 1002 題目詳情 1003 1004 7-33 生化危機 (20分) 1005 人類正在經歷一場生化危機，許多城市已經被病毒侵襲，這些城市中的人們為了避免感染病毒，計劃開車逃往其他沒有被病毒入侵的城市（安全城市），有些城市之間有公路直達，有些沒有，雖然他們知道哪些城市是安全的，但是不知道有沒有一條安全路徑能夠到達安全城市（只有該路徑上經過的所有城市都是安全的，該路徑才是安全路徑），請你撰寫一個程式幫助他們判斷， 1006 輸入格式: 1007 輸入第一行為三個正整數，分別表示所有城市個數m（m<=100）、安全城市個數n（m<=50）、公路個數k（k<=100），隨后一行給出n個安全城市的編號，隨后k行，每一行給出兩個整數，表示連接一條公路的兩個城市編號，最后一行輸入兩個整數，分別表示當前所在城市s、目標城市d，每行整數之間都用空格分隔， 1008 輸出格式: 1009 若目標城市已被病毒入侵（非安全城市），輸出"The City i is not safe!"；若目標城市為安全城市且從當前所在城市能夠經過一條安全路徑到達目標城市，輸出"The city can arrive safely！"；若目標城市為安全城市但是從當前所在城市沒有一條安全路徑到達目標城市，輸出"The city can not arrive safely！"，i為目標城市編號， 1010 輸入樣例1: 1011 1012 5 2 5 1013 3 4 1014 0 1 1015 0 2 1016 0 4 1017 1 2 1018 2 4 1019 0 4 1020 輸出樣例1: 1021 1022 The city 4 can arrive safely! 1023 輸入樣例2: 1024 1025 5 2 5 1026 3 4 1027 0 1 1028 0 2 1029 0 4 1030 1 2 1031 2 4 1032 0 3 1033 輸出樣例2: 1034 1035 The city 3 can not arrive safely! 1036 輸入樣例3: 1037 1038 5 2 5 1039 3 4 1040 0 1 1041 0 2 1042 0 4 1043 1 2 1044 2 4 1045 0 1 1046 輸出樣例3: 1047 1048 The city 1 is not safe! 1049 1050 作者: DS課程組 1051 單位: 臨沂大學 1052 時間限制: 400 ms 1053 記憶體限制: 64 MB 1054 代碼長度限制: 16 KB 1055 題目詳情 1056 1057 7-34 孤島營救問題 (30分) 1058 1944 年，特種兵麥克接到國防部的命令，要求立即趕赴太平洋上的一個孤島，營救被敵軍俘虜的大兵瑞恩，瑞恩被關押在一個迷宮里，迷宮地形復雜，但幸好麥克得到了迷宮的地形圖，迷宮的外形是一個長方形， 其南北方向被劃分為 n 行，東西方向被劃分為 m 列，于是整個迷宮被劃分為 n×m 個單元，每一個單元的位置可用一個有序數對 (單元的行號, 單元的列號) 來表示，南北或東西方向相鄰的 2 個單元之間可能互通，也可能有一扇鎖著的門，或者是一堵不可逾越的墻，迷宮中有一些單元存放著鑰匙，并且所有的門被分成 p 類， 打開同一類的門的鑰匙相同，不同類門的鑰匙不同， 1059 大兵瑞恩被關押在迷宮的東南角，即 (n,m) 單元里，并已經昏迷，迷宮只有一個入口， 在西北角，也就是說，麥克可以直接進入 (1,1) 單元，另外，麥克從一個單元移動到另一個 相鄰單元的時間為 1，拿取所在單元的鑰匙的時間以及用鑰匙開門的時間可忽略不計， 1060 試設計一個演算法，幫助麥克以最快的方式到達瑞恩所在單元，營救大兵瑞恩， 1061 輸入格式: 1062 第一行有三個整數,分別表示n,m,p的值， 1063 第二行是一個整數k，表示迷宮中門和墻的總數， 1064 第 i+2 行 (1≤i≤k)，有 5 個整數， 依次為 xi1,yi1,xi2,yi2,gi :當 gi≥1 時，表示 (xi1,yi1) 單元 與 (xi2,yi2) 單元之間有一扇第 gi 類的門，當 gi=0 時， 表 示 (xi1,yi1) 單元與 (xi2,yi2) 單元之間有一堵不可逾越的墻， 1065 第 k+3 行是一個整數 s，表示迷宮中存放的鑰匙總數， 1066 第 k+3+j 行 (1≤j≤s) ，有 3 個整數，依次為 xi1,yi1,qi，表示第 j 把鑰匙存放在 (xi1,yi1) 單元里，并且第 j 把鑰匙是用來開啟第 qi 類門， 1067 輸入資料中同一行各相鄰整數之間用一個空格分隔， 1068 資料保證有 1069 ∣xi1?xi2∣+∣yi1?yi2∣=1,0≤gi≤p 1070 1≤qi≤p 1071 n,m,p≤10,k<150 1072 輸出格式: 1073 輸出麥克營救到大兵瑞恩的最短時間，如果問題無解，則輸出 ?1， 1074 輸入樣例: 1075 在這里給出一組輸入，例如： 1076 1077 4 4 9 1078 9 1079 1 2 1 3 2 1080 1 2 2 2 0 1081 2 1 2 2 0 1082 2 1 3 1 0 1083 2 3 3 3 0 1084 2 4 3 4 1 1085 3 2 3 3 0 1086 3 3 4 3 0 1087 4 3 4 4 0 1088 2 1089 2 1 2 1090 4 2 1 1091 輸出樣例: 1092 在這里給出相應的輸出，例如： 1093 1094 14 1095 1096 作者: 小黑 1097 單位: 臨沂大學 1098 時間限制: 4000 ms 1099 記憶體限制: 64 MB 1100 代碼長度限制: 16 KB 1101 題目詳情 1102 1103 7-35 編輯三角形 (30分) 1104 二維平面上有一個三角形，可以通過命令對其進行編輯， 其中命令 translate dx dy 是將三角形平移(dx,dy); 命令 rotate angle 是將三角形繞自己的中心位置(三個頂點的平均位置）旋轉angle（角度制）; 命令 scale ratio 是將三角形相對于自己的中心位置縮放ratio（例如1.0表示不縮放，2.0表示放大一倍，0.5表示縮小一倍）; 命令 undo 是撤銷剛才的一個編輯操作， 1105 輸入格式: 1106 第一行給出六個實數x0 y0 x1 y1 x2 y2 表示該三角形的三個頂點坐標，第二行給出正整數n (1=< n <=100)，表示命令個數，隨后n行給出具體的編輯命令， 1107 輸出格式: 1108 輸出被編輯后的三角形的三個頂點坐標，每個數之間用一個空格分割，最后一個數后面不要多加空格，所有實數保留3位小數， 1109 樣例: 1110 例如輸入1： 1111 1112 3.0 3.0 4.0 3.0 3.0 4.0 1113 1 1114 translate 1.5 -1.5 1115 輸出： 1116 1117 4.500 1.500 5.500 1.500 4.500 2.500 1118 例如輸入2： 1119 1120 3.0 3.0 4.0 3.0 3.0 4.0 1121 1 1122 rotate 90.0 1123 輸出： 1124 1125 3.667 3.000 3.667 400 2.667 3.000 1126 例如輸入3： 1127 1128 3.0 3.0 4.0 3.0 3.0 4.0 1129 1 1130 scale 0.5 1131 輸出： 1132 1133 3.167 3.167 3.667 3.167 3.167 3.667 1134 例如輸入4： 1135 1136 3.0 3.0 4.0 3.0 3.0 4.0 1137 4 1138 scale 0.5 1139 undo 1140 rotate 90.0 1141 translate 0.5 0.6 1142 輸出： 1143 1144 4.167 3.600 4.167 4.600 3.167 3.600 1145 1146 作者: dingzh 1147 單位: 金陵科技學院 1148 時間限制: 400 ms 1149 記憶體限制: 64 MB 1150 代碼長度限制: 16 KB 1151 題目詳情 1152 1153 7-36 角度與多邊形 (20分) 1154 給你一個角度 ang. 1155 你能否在一個正 n 邊形上找到三個頂點 a,b,c 使得 ∠abc =ang. 1156 1157 如果存在多個這樣的正多邊形，輸出最小的那個， 1158 如果不存在這個多邊形，請輸出 ?1. 1159 輸入格式: 1160 第一行包含一個正整數 T(1≤T≤180)，代表詢問的次數， 1161 接下來 T 行，每行給出一個角度 ang(1≤ang≤180). 1162 輸出格式: 1163 在一行里按要求輸出對應詢問的答案， 1164 輸入樣例: 1165 1166 1 1167 54 1168 輸出樣例: 1169 1170 10 1171 樣例解釋: 1172 樣例對應圖片上的情況 1173 作者: 小黑 1174 單位: 臨沂大學 1175 時間限制: 1000 ms 1176 記憶體限制: 64 MB 1177 代碼長度限制: 16 KB 1178 題目詳情 1179 1180 7-37 英文單詞排序 (30分) 1181 本題要求撰寫程式，輸入若干英文單詞，對這些單詞按長度從小到大排序后輸出，如果長度相同，按照輸入的順序不變， 1182 輸入格式： 1183 輸入為若干英文單詞，每行一個，以 1184 # 1185 作為輸入結束標志，其中英文單詞總數不超過20個，英文單詞為長度小于10的僅由小寫英文字母組成的字串， 1186 輸出格式： 1187 輸出為排序后的結果，每個單詞后面都額外輸出一個空格， 1188 輸入樣例： 1189 1190 blue 1191 red 1192 yellow 1193 green 1194 purple 1195 # 1196 輸出樣例： 1197 1198 red blue green yellow purple 1199 1200 作者: 張泳 1201 單位: 浙江大學城市學院 1202 時間限制: 400 ms 1203 記憶體限制: 64 MB 1204 代碼長度限制: 16 KB 1205 題目詳情 1206 1207 7-38 互評成績 (30分) 1208 學生互評作業的簡單規則是這樣定的：每個人的作業會被 1209 k 1210 個同學評審，得到 1211 k 1212 個成績，系統需要去掉一個最高分和一個最低分，將剩下的分數取平均，就得到這個學生的最后成績，本題就要求你撰寫這個互評系統的算分模塊， 1213 輸入格式： 1214 輸入第一行給出3個正整數 1215 N 1216 （3 < 1217 N 1218 ≤104，學生總數）、 1219 k 1220 （3 ≤ 1221 k 1222 ≤ 10，每份作業的評審數）、 1223 M 1224 （≤ 20，需要輸出的學生數），隨后 1225 N 1226 行，每行給出一份作業得到的 1227 k 1228 個評審成績（在區間[0, 100]內），其間以空格分隔， 1229 輸出格式： 1230 按非遞減順序輸出最后得分最高的 1231 M 1232 個成績，保留小數點后3位，分數間有1個空格，行首尾不得有多余空格， 1233 輸入樣例： 1234 1235 6 5 3 1236 88 90 85 99 60 1237 67 60 80 76 70 1238 90 93 96 99 99 1239 78 65 77 70 72 1240 88 88 88 88 88 1241 55 55 55 55 55 1242 輸出樣例： 1243 1244 87.667 88.000 96.000 1245 1246 作者: 陳越 1247 單位: 浙江大學 1248 時間限制: 300 ms 1249 記憶體限制: 64 MB 1250 代碼長度限制: 16 KB 1251 題目詳情 1252 1253 7-39 租用游艇問題 (20分) 1254 題目來源：王曉東，《演算法設計與分析》 1255 長江游艇俱樂部在長江上設定了n個游艇出租站1，2，…，n，游客可在這些游艇出租站租用游艇，并在下游的任何一個游艇出租站歸還游艇，游艇出租站i到游艇出租站j之間的租金為r(i,j),1<=i<j<=n，試設計一個演算法，計算出從游艇出租站1 到游艇出租站n所需的最少租金， 1256 輸入格式: 1257 第1 行中有1 個正整數n（n<=200），表示有n個游艇出租站，接下來的第1到第n-1 行，第i行表示第i站到第i+1站,第i+2站, ... , 第n站的租金， 1258 輸出格式: 1259 輸出從游艇出租站1 到游艇出租站n所需的最少租金， 1260 輸入樣例: 1261 在這里給出一組輸入，例如： 1262 1263 3 1264 5 15 1265 7 1266 輸出樣例: 1267 在這里給出相應的輸出，例如： 1268 1269 12 1270 1271 作者: 陳曉梅 1272 單位: 廣東外語外貿大學 1273 時間限制: 400 ms 1274 記憶體限制: 64 MB 1275 代碼長度限制: 16 KB 1276 題目詳情 1277 1278 7-40 修理牧場 (20分) 1279 農夫要修理牧場的一段柵欄，他測量了柵欄，發現需要N塊木頭，每塊木頭長度為整數Li個長度單位，于是他購買了一條很長的、能鋸成N塊的木頭，即該木頭的長度是Li的總和， 1280 但是農夫自己沒有鋸子，請人鋸木的酬金跟這段木頭的長度成正比，為簡單起見，不妨就設酬金等于所鋸木頭的長度，例如，要將長度為20的木頭鋸成長度為8、7和5的三段，第一次鋸木頭花費20，將木頭鋸成12和8；第二次鋸木頭花費12，將長度為12的木頭鋸成7和5，總花費為32，如果第一次將木頭鋸成15和5，則第二次鋸木頭花費15，總花費為35（大于32）， 1281 請撰寫程式幫助農夫計算將木頭鋸成N塊的最少花費， 1282 輸入格式: 1283 輸入首先給出正整數N（≤104），表示要將木頭鋸成N塊，第二行給出N個正整數（≤50），表示每段木塊的長度， 1284 輸出格式: 1285 輸出一個整數，即將木頭鋸成N塊的最少花費， 1286 輸入樣例: 1287 1288 8 1289 4 5 1 2 1 3 1 1 1290 輸出樣例: 1291 1292 49 1293 1294 作者: DS課程組 1295 單位: 浙江大學 1296 時間限制: 400 ms 1297 記憶體限制: 64 MB 1298 代碼長度限制: 16 KB 1299 題目詳情
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/114580.html
標籤：其他