安徽省2009年省選題day2

《安徽省2009年省選題day2》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、1：飛行棋（Fly）在經(jīng)過地“小小宇航員夏令營”的學(xué)習(xí)以及模擬飛行實驗后，小可可明白宇航員并不是那么容易當?shù)?，除了需要強健的身體，豐富的經(jīng)驗以及靈活的應(yīng)變能力以外，縝密的思維也是不可少的，為了早日實現(xiàn)自己的宇航員的夢想，小可可決定在平時就開始鍛煉——利用棋類游戲來鍛煉自己的思維。小可可發(fā)明一種飛行棋，棋盤是一個圓周形，在圓周形上有若干個點，已知這些點與點之間的弧長，弧長均為正整數(shù)，并且依圓弧順序排列，飛行棋的規(guī)則是找出這些點中有沒有可以圍成矩形的，在最短時間內(nèi)找出所有不重復(fù)矩形的玩家勝出。輸入：第一行為正整數(shù)N，表示棋盤上點的個數(shù)，接下來n行分別為這N個點所分割

2、的各個圓弧的長度。輸出：所構(gòu)成的不重復(fù)的矩形。樣例：輸入：812231133輸出：3100%的數(shù)據(jù):n<=20Timelimit:1000ms2：中國象棋（Chess）這次小可可想解決的難題和中國象棋有關(guān)，在一個N行M列的棋盤上，讓你放若干個炮（可以是0個），使得沒有一個炮可以攻擊到另一個炮，請問有多少種放置方法。大家肯定很清楚，在中國象棋中炮的行走方式是：一個炮攻擊到另一個炮，當且僅當它們在同一行或同一列中，且它們之間恰好有一個棋子。你也來和小可可一起鍛煉一下思維吧！輸入：一行包含兩個整數(shù)N，M，之間由一個空格隔開。輸出：總共的方案數(shù)，由于該值可能很大，只需給

3、出方案數(shù)模9999973的結(jié)果。樣例：輸入：13輸出：7樣例說明：除了3個格子里都塞滿了炮以外，其它方案都是可行的，所以一共有2*2*2-1=7種方案。提示：100%的數(shù)據(jù)中N和M不超過10050%的數(shù)據(jù)中N和M至少有一個數(shù)不超過830%的數(shù)據(jù)中N和M均不超過6Casetimelimit:1000ms3:跳棋（checker）象棋的問題被小可可輕松解決了，下面小可可邀請你一起來研究另一個難題，這次與跳棋有關(guān)，問題是這樣的：在一個1行N列（N是奇數(shù)）的棋盤上，在K個格子是紅色的，這種情況下，在開始移動之前，你可以棋盤的任何空位上放棋子。在游戲開始后，你只可以隨時在

4、一個紅色格子上放棋子。棋子的移動規(guī)則是：每次只可以選擇一個棋子，跳過與之相鄰的棋子走到后面的空格上，被它跳過的棋子就被吃掉了，即從棋盤上移走，如相鄰棋子的另一側(cè)有棋子，則不能跳。現(xiàn)在你和小可可要解答以下兩個問題：1.移動開始前至少要放多少棋子才能完成任務(wù)？2.如果使移動開始前放的棋子數(shù)要求盡量少，那么在移動過程中最少需要放多少個棋子才能完成任務(wù)？這是你和小可可合作解決的最后一個問題了，共同努力吧！關(guān)于規(guī)則的補充說明：1.只能往空位上放棋子，不管是移動開始前還是在移動過程中。2.移動開始前棋盤最左端的那個原始棋子絕對不能被吃掉。輸入：第一行一個正奇數(shù)N第二行有N個

5、整數(shù)，如果第i個整數(shù)是1，說明第i個格子是紅色，否則則為白色，數(shù)字之間用一個空格隔開。輸出：兩個用一個空格隔開的整數(shù)，分別為對第一問和第二問的回答。樣例：輸入：500010輸出：11提示：100%的數(shù)據(jù)中，N不超過1000.輸出中數(shù)字不會超過10的15次方！30%的數(shù)據(jù)，N不超過20Timelimit:1000ms