2024年CSPS提高級第二輪復(fù)賽試題

時間：2024年10月26日14:30～18:30題目名稱決斗超速檢測染色題目類型傳統(tǒng)型傳統(tǒng)型傳統(tǒng)型傳統(tǒng)型目錄可執(zhí)行文件名輸入文件名輸出文件名每個測試點時限1.0秒2.0秒1.0秒1.0秒內(nèi)存限制測試點數(shù)目測試點是否等分是是是是對于C++語言注意事項(請仔細閱讀)1.文件名(程序名和輸入輸出文件名)必須使用英文小寫。2.main函數(shù)的返回值類型必須是int,程序正常結(jié)束時的返回值必須是0。5.若無特殊說明，結(jié)果的比較方式為全文比較(過濾行末空格及文末回車)。6.選手提交的程序源文件必須不大于100KB。10.評測在當(dāng)前最新公布的NOILinux下進行，各語言的編譯器版本以此為準(zhǔn)?！绢}目描述】今天是小Q的生日，他得到了n張卡牌作為禮物。這些卡牌屬于火爆的“決斗怪獸”,其中，第i張卡代表一只攻擊力為ri,防御力也為r:的怪獸。一場游戲分為若干回合。每回合，小Q會選擇某只怪獸i以及另一只怪獸j(i≠j),并讓怪獸i向怪獸j發(fā)起攻擊。此時，若怪獸i的攻擊力小于等于怪獸j的防御力，則無事發(fā)生；否則，怪獸j的防御被打破，怪獸j退出游戲不再參與到剩下的游戲中。一只怪獸在整場游戲中至多只能發(fā)起一次攻擊。當(dāng)未退出游戲的怪獸都已發(fā)起過攻擊時，小Q希望決定一組攻擊順序，使得在游戲結(jié)束時，未退出游戲的怪獸數(shù)量盡可能【輸入格式】輸入的第一行包含一個正整數(shù)n,表示卡牌的個數(shù)。輸入的第二行包含n個正整數(shù)，其中第i個正整數(shù)表示第i個怪獸的攻擊力及防御【輸出格式】121【樣例1輸入】55【樣例1輸出】22【樣例1解釋】其中一種最優(yōu)方案為：第一回合讓第2只怪獸向第1只怪獸發(fā)起攻擊，第二回合讓第5只怪獸向第4只怪獸發(fā)起攻擊，第三回合讓第3只怪獸向第5只怪獸發(fā)起攻擊。此時沒有退出游戲的怪獸都進行過攻擊，游戲結(jié)束?？梢宰C明沒有更優(yōu)第2頁共14頁2024CCF非專業(yè)級軟件能力認(rèn)證CSP-J/S2024第二輪認(rèn)證提高級(de斗l)21361361362417136136241見選手目錄下的duel/duel3.in與duel/duels.ans。該樣例滿足V1≤i≤n,ri≤2。見選手目錄下的duel/duel4.in與duel/duel4.ans?！緮?shù)據(jù)范圍】對于所有測試數(shù)據(jù)，保證：1≤n≤10?,1≤ri≤10?。測試點nT特殊性質(zhì)無特殊性質(zhì)無特殊性質(zhì)特殊性質(zhì)A:保證每個r;在可能的值域中獨立均勻隨機生成。第3頁共14頁【題目描述】小D新入職了某國的交管部門，他的第一個任務(wù)是負責(zé)國家的一條長度為L的南北主干道的車輛超速檢測。為了考考小D,上司首先需要他解決一個簡化的場景。這個周末，主干道上預(yù)計出現(xiàn)n輛車，其中第i輛車從主干道上距離最南端d;的位置駛?cè)耄詖;的初速度和a;的加速度做勻加速運動向北行駛。我們只考慮從南向北的車輛，故vi>0,但a;可正可負，也可以為零。當(dāng)車輛行駛到主干道最北端(即距離最南端為L的位置)或速度降為0(這只可能在a;<0時發(fā)生)時，我們認(rèn)為該車駛離主干道。主干道上設(shè)置了m個測速儀，其中第j個測速儀位于主干道上距離最南端p;的位置，每個測速儀可以設(shè)置開啟或關(guān)閉。當(dāng)某輛車經(jīng)過某個開啟的測速儀時，若這輛車的瞬時速度超過了道路限速V,那么這輛車就會被判定為超速。注意當(dāng)車輛駛?cè)肱c駛出主干道時，如果在對應(yīng)位置有一個開啟的測速儀，這個測速儀也會對這輛車進行測速。上司首先想知道，如果所有測速儀都是開啟的，那么這n輛車中會有多少輛車被判定為超速。其次，為了節(jié)能，部門想關(guān)閉一部分測速儀。然而，他們不希望漏掉超速的車，也就是說，當(dāng)n輛車?yán)锏哪齿v車在所有測速儀都開啟時被判定為超速，他們希望在關(guān)閉一部分測速儀以后它依然被判定為超速。上司還想知道在這樣的條件下最多可以關(guān)閉多少測速儀。由于n很大，上司允許小D使用編程解決這兩個問題，于是小D找到了你。如果你對于加速度并不熟悉，小D貼心地在本題的“提示”部分提供了有關(guān)加速度的公式?！据斎敫袷健繌奈募etect.in中讀入數(shù)據(jù)。本題有多組測試數(shù)據(jù)。輸入的第一行包含一個正整數(shù)T,表示數(shù)據(jù)組數(shù)。接下來包含T組數(shù)據(jù)，每組數(shù)據(jù)的格式如下：第一行包含四個整數(shù)n,m,L,V,分別表示車輛數(shù)量、測速儀數(shù)量、主干道長度和道路限速。接下來n行：第i行包含三個整數(shù)d,vi,a;描述一輛車。最后一行包含m個整數(shù)P1,P?,…,pm描述道路上所有測速儀的位置。第4頁共14頁【輸出格式】對于每組數(shù)據(jù)：輸出一行包含兩個整數(shù)，第一個整數(shù)為所有測為超速的車輛數(shù)量，第二個整數(shù)為在不漏掉超速車輛的前提12345678【樣例1輸入】1【樣例1輸出】【樣例1解釋】在該組測試數(shù)據(jù)中，主干道長度為15,限速為3,在距離最南端2,5,8,9,15的位置·第一輛車在最南端駛?cè)?，?的速度勻速行駛。這輛車在整個路段上都沒有超速。·第二輛車在距離最南端12的位置駛?cè)?，?的速度勻速行駛。在最北端駛離主干道時，它會被距離最南端15的測速儀判定為超速?！さ谌v車在距離最南端1的位置駛?cè)?，?的初速度、4的加速度行駛。其在行駛了的距離，即到達2的位置時，速度變?yōu)?,并在之后一直超速。因此這輛車會被除了距離最南端2的測速儀以外的其他測速儀判定為超速?！さ谒妮v車在距離最南端5的位置駛?cè)?，?的初速度、-2的加速度行駛。其在行駛了4的距離，即到達9的位置時，速度變?yōu)?。因此這輛車在距離最南端(5,9)時超速，會被距離最南端5和8的兩個測速儀判定為超速?！さ谖遢v車在距離最南端6的位置駛?cè)?，?的初速度、-4的加速度行駛。在其行駛了的距離后，即這輛車到達63的位置時，其速度變?yōu)?。因此第5頁共14頁這輛車在距離最南端(6,63)時超速，但這段區(qū)間內(nèi)沒有測速儀，因此不會被判定因此第二、三、四輛車會被判定為超速，輸出的第一個數(shù)為3。我們可以關(guān)閉距離最南端2,8,9的三個測速儀，保留5和15的兩個測速儀，此時三輛之前被判定為超速的車依然被判定為超速?？梢宰C明不存在更優(yōu)方案，因此輸出的第二個數(shù)為3。見選手目錄下的detect/detect2.in與detect/detect2.ans。該組樣例滿足n,m≤10。見選手目錄下的detect/detect3.in與detect/detect3.ans。該組樣例滿足特殊性質(zhì)A,其中前十組測試數(shù)據(jù)滿足n,m≤3000。見選手目錄下的detect/detect4.in與detect/detect?.ans。該組樣例滿足特殊性質(zhì)B,其中前十組測試數(shù)據(jù)滿足n,m≤3000。見選手目錄下的detect/detect5.in與detect/detect5.ans。該組樣例滿足特殊性質(zhì)C,其中前十組測試數(shù)據(jù)滿足n,m≤3000。【數(shù)據(jù)范圍】對于所有測試數(shù)據(jù)，保證：第6頁共14頁測試點特殊性質(zhì)1無23A45B67C89無特殊性質(zhì)A:保證a;=0?！咎崾尽縑?=vo+a×t,它的位移(即行駛路程)s=vo×t+0.5×a×t2。路程)為s時，這輛車的瞬時速度為√咯+2×a×S?！ぎ?dāng)一輛車的初速度為vo、加速度a≠0,在它的位移(即行駛路程)為時，【題目描述】給定一個長度為n的正整數(shù)數(shù)組A,其中所有數(shù)從左至右排成一排。你需要將A中的每個數(shù)染成紅色或藍色之一，然后按如下方式計算最終得分：設(shè)C為長度為n的整數(shù)數(shù)組，對于A中的每個數(shù)A;(1≤i≤n):·否則，記其左側(cè)與其最靠近的同色數(shù)為A;,若A;=A;,則令C=A,否則令你的最終得分為C中所有整數(shù)的和，即你需要最大化最終得分，請求出最【輸入格式】第一行包含一個正整數(shù)n,表示數(shù)組長度。第二行包含n個正整數(shù)A?,A?,..,An,表示數(shù)組A中的元素?！据敵龈袷健枯敵龅轿募olor.out中。對于每組數(shù)據(jù)：輸出一行包含一個非負整數(shù)，表示最終得分的【樣例1輸入】1234567348第8頁共14頁【樣例1輸出】123108【樣例1解釋】1.將A?,A?染成紅色，將A?染成藍色(121),其得分計算方式如下：·對于A?,由于其左側(cè)沒有紅色的數(shù)，所以C?=0?！τ贏?,其左側(cè)與其最靠近的紅色數(shù)為A?。由于A?≠A?,所以C?=0?！τ贏?,由于其左側(cè)沒有藍色的數(shù)，所2.將A?,A?,A?全部染成紅色(121),其得分計算方式如下：·對于A?,由于其左側(cè)沒有紅色的數(shù)，所以C?=0?！τ贏?,其左側(cè)與其最靠近的紅色數(shù)為A?。由于A?≠A?,所·對于A?,其左側(cè)與其最靠近的紅色數(shù)為A?。由于A?≠A?,所該方案最終得分為C?+C?+C?=0。3.將A?,A?染成紅色，將A?染成藍色(121),其得分計算方式如下：·對于A?,由于其左側(cè)沒有紅色的數(shù)，所以C?=0?！τ贏?,由于其左側(cè)沒有藍色的數(shù)，所以C?=0?？梢宰C明，沒有染色方案使得最終得分大于1。對于第二組數(shù)據(jù)，可以證明，任何染色方案的最終得分都是0。染為藍色(35152124),其對應(yīng)C=[0,0,0,5,0,1,2,0],最終得分為8?！緲永?】見選手目錄下的color/color2.in【數(shù)據(jù)范圍】第9頁共14頁2024CCF非專業(yè)級軟件能力認(rèn)證CSP-J/S2024第二輪認(rèn)證提高級(co染lor色)測試點n第10頁共14頁2024CCF非專業(yè)級軟件能力認(rèn)證CSP-J/S2024第二輪認(rèn)證提高級擂臺(a游ren)【題目描述】小S想要舉辦一場擂臺游戲，如果共有2k名選手參加，那么游戲分為k輪進行：·第一輪編號為1,2的選手進行一次對局，編號為3,4的選手進行一次對局，以此類推，編號為2*-1,2k的選手進行一次對局?！さ诙喸谥槐Ａ舻谝惠喌膭僬叩那疤嵯?，相鄰·以此類推，第k-1輪在只保留第k-2輪的4位勝者的前提下，前兩位、后兩手都有一個能力值a?,a?,…,a?k,能力值為[0,231-1]之內(nèi)的整數(shù)。對于每場比賽，會先抽簽決定一個數(shù)0/1,我們將第R輪的第G場比賽抽到的數(shù)記為dr,c。抽到0則表示表示編號小的選手為擂主，抽到1則表示編號大的選手為擂主。擂主獲勝當(dāng)且僅當(dāng)他現(xiàn)在，小S先后陸續(xù)收到了n位選手的報名信息，他們分別告知了小S自己的能盡量少的選手使總?cè)藬?shù)為2的整次冪，且所有選手進行一次完整的擂臺游戲后，所有可形式化地，設(shè)k是最小的非負整數(shù)使得2k≥n,那么應(yīng)當(dāng)補充(2k-n)名選手，且補充的選手的能力值可以任取[0,231-1]之內(nèi)的整數(shù)。如果補充的選手有可能獲勝，也當(dāng)然小S覺得這個問題還是太簡單了，所以他給了你m個詢問c?,C?,…,Cm。小S希望你幫忙對于每個c;求出，在只收到前c:位選手的報名信息時，這個問題的答案【輸入格式】到，其他內(nèi)容均保持不變，請參考以下格式。其中田代表異或運算符，amodb代表a除以b的余數(shù)。輸入的第一行包含兩個正整數(shù)n,m,表示報名的選手?jǐn)?shù)量和輸入的第二行包含n個非負整數(shù)d?,a2,…,an,這列數(shù)將用來計算真正的能力值。輸入的第三行包含m個正整數(shù)c?,C?,…,Cm,表示詢問。設(shè)K是使得2K≥n的最小的非負整數(shù)，接下來的K行當(dāng)中，第R行包含2K-R個數(shù)(無空格),其中第G個數(shù)表示第R輪的第G場比賽抽簽得到的dr,c=0/1。第11頁共14頁注意，由于詢問只是將人數(shù)湊齊到2k≥c;,這里的k≤K,因此你未必會用到全部接下來一行包含一個正整數(shù)T,表示有T組測試數(shù)據(jù)。接下來共T行，每行描述一組數(shù)據(jù)，包含4個非負整數(shù)X?,X?,X?,X3,該組數(shù)據(jù)的能力值a;=a'田Ximod4,其中1≤i≤n?！据敵龈袷健抗草敵鯰行，對于每組數(shù)據(jù)，設(shè)A?為第i(1≤i≤m)組詢問的答案，你只需要1231234567891121234571【樣例1解釋】共有T=4組數(shù)據(jù)，這里只解釋第一組。5名選手的真實能力值組詢問分別是對長度為5,4,1,2,3的前綴進行的。1.對于長度為1的前綴，由于只有1號一個人，因此答案為1。第12頁共14頁2.對于長度為2的前綴，由于2個人已經(jīng)是2的冪次，因此不需要進行擴充。根據(jù)抽簽d?,1=1可知2號為擂主，由于a?<1,因此1號獲勝，答案為1。3.對于長度為3的前綴，首先1號、2號比賽是1號獲勝(因為d1,1=1,