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

Codeforces Round #288 (Div. 2) A-E 題解總覽

     編輯:關於C++

A. Pasha and Pixels

逐個像素著色,檢查是否形成 2×2 全黑方塊。用二維數組標記,每次著色後檢查以該點為右下角的四個可能 2×2 方塊。O(n*m)。

B. Anton and Currency

給定數字字符串,交換最後一位與某一偶數位,使結果最大。貪心:從左向右找第一個 偶數位 < 最後一位 交換;若無,從右向左找最後一個偶數位交換。

C. Anya and Ghosts

蠟燭燃燒 t 秒,點燃需 1 秒。幽靈到達時刻 w_i,需至少 r 支燃燒中蠟燭。貪心:倒序處理幽靈,盡可能晚點燃蠟燭(在 [w_i - t, w_i - 1] 區間最右端未被佔用的秒點燃)。若區間長度 t < r 則無解 (-1)。

D. Tanya and Password

詳見 CF 508D / CF 288D:三元子串建模有向圖歐拉路徑,Hierholzer 算法構造。

E. Arthur and Brackets

給定 n 對括號,第 i 對左括號與右括號距離在 [l_i, r_i] 且為奇數。求合法括號序列。DP:dp[l][r] 表示區間 [l,r] 能否合法匹配。枚舉 l 匹配的位置 k (步長 2),需滿足 k-l+1 ∈ [l_l, r_l] 且 dp[l+1][k-1] 和 dp[k+1][r] 均合法。記錄選擇以構造輸出。O(n^3),n≤600 可過。

總結

本場比賽涵蓋:模擬 (A)、貪心 (B, C)、圖論歐拉路徑 (D)、區間 DP (E)。D 和 E 是難點,分別考察歐拉路徑構造與括號序列 DP。

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