兩玩家各寫 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
兩組各 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
連通迷宮保留 s-k 空地。DFS 訪問前 s-k 個,其餘標 'X'。詳見專題解析。
m 個 Bug(難度 a_i),n 程序員(能力 b_j、費用 c_j),總預算 s。每天每程序員修一個難度 ≤ 能力的 Bug。求最少天數及分配方案。
核心:二分天數 T。檢查 T 天可行性:
- Bug 按難度降序,程序員按能力降序。
- 每輪分配 T 個最難 Bug 給當前最強可用程序員(優先隊列維護費用最小的可用程序員)。
- 總費用 ≤ s 即可行。
複雜度:O((n+m) log n log m)。
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 綜合訓練的優質題單。