首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
您现在的位置: 程式碼之家 >> 編程語言 >  >> C語言 >> C++ >> C++ 入門

Codeforces Round #222 (Div. 2) 題解全集:A~E 五題完整分析與代碼

     編輯:C++ 入門

A. Playing with Dice

兩玩家各寫 1~6 數字 a,b,擲骰子,差值較小者勝,相等平局。統計三種結果出現次數。
解法:枚舉骰子 1~6,計算 |a-i| 與 |b-i| 比較,計數。
複雜度:O(1)。


int a,b; cin>>a>>b;
int win=0, draw=0, lose=0;
for(int i=1;i<=6;++i){
    int da=abs(a-i), db=abs(b-i);
    if(da

B. Semifinals

兩組各 n 人,前 k 直接晉級,其餘按時間排名。輸出每組晉級標記。
解法:貪心雙指針。前 n/2 名直接標記 1。剩餘名額按兩組時間歸併選取較小者。
代碼:


int n; cin>>n;
vector a(n), b(n);
for(int i=0;i>a[i]>>b[i];
vector ansA(n), ansB(n);
for(int i=0;i

C. Maze (同 CF 377A)

連通迷宮保留 s-k 空地。DFS 訪問前 s-k 個,其餘標 'X'。詳見專題解析。

D. Bugs Fixing

m 個 Bug(難度 a_i),n 程序員(能力 b_j、費用 c_j),總預算 s。每天每程序員修一個難度 ≤ 能力的 Bug。求最少天數及分配方案。
核心:二分天數 T。檢查 T 天可行性:
- Bug 按難度降序,程序員按能力降序。
- 每輪分配 T 個最難 Bug 給當前最強可用程序員(優先隊列維護費用最小的可用程序員)。
- 總費用 ≤ s 即可行。
複雜度:O((n+m) log n log m)。

E. Dota 2 Senate (BP 博弈)

m 個英雄(能力值 s_i),雙方輪流 Ban/Pick。Pick 時雙方必選當前最強;Ban 時需考慮後續局勢。
解法:狀態壓縮 DP + 記憶化搜索。
- 狀態:mask 表示剩餘英雄集合,step 表示當前操作索引。
- 轉移:Pick 時直接取最大值(貪心);Ban 時枚舉所有可 Ban 英雄,取最優(Max 玩家取最大,Min 玩家取最小)。
- 初始狀態:前 m 強英雄(其餘無關)。
代碼框架:


int dp[1<<20];
int dfs(int mask, int step) {
    if (dp[mask]!=-1) return dp[mask];
    if (step==m) return 0;
    if (op[step]=='p') {
        int best = -INF;
        for(int i=0;i

總結

本輪比賽涵蓋模擬、貪心、DFS構造、二分+優先隊列、狀態壓縮 DP 等經典技巧,是 Div.2 綜合訓練的優質題單。

  1. 上一篇文章:
  2. 下一篇文章:
Copyright © 程式碼之家 All Rights Reserved