0w1

Entries from 2017-03-29 to 1 day

CFR 613 C. Necklace ( Ad hoc, Palindrome )

Problem - C - Codeforces題意: 給 'a' ~ 'a' + N - 1 各個字母的出現頻度。要求構造一個環狀的字串,使得最多處切下去會是迴文。資料規模: N ≤ 26 出現頻度總數不超過 1e5解法: 因為至少要有一個迴文就必須有不超過一個奇數的頻度,所以接下來可以分開討…

CFR 613 B. Skills ( Binary Search )

Problem - B - Codeforces題意: 有 N 個技能,所有技能都用一個數值描述,上限皆為 A,你有 M 單位的金子,一個單位的金子可以提升一個技能的數值一個單位。你要最大化:數值為 A 的技能數量 * Cf + 最低的技能數值 * Cm。求最大化的值以及方案。資料規模:…

CFR 613 A. Peter and Snow Blower ( Geometry )

Problem - A - Codeforces題意: 給一個代表自轉中心的座標,以及順時針給的座標描述一個凸多邊形。問旋轉 360 度後,被覆蓋過的面積有多少。資料規模: N ≤ 1e5解法: 顯然要找離圓心的最遠點,以及最近點... 但仔細想想會發現不是最近點,其實是和任意線段…

CFR 781 C. Underground Lab ( Ad hoc, Time Stamp, DFS )

Problem - C - Codeforces題意: 給一個圖,要求放 K 個機器人並給出每個機器人的路徑,路徑長至多為 ceil( 2 * N / K ),使得所有節點都被至少一個機器人拜訪過。資料規模: N, M ≤ 2e5解法: 首先把圖轉換成任意一個生成樹。接著進行類似時間戳記的 DFS,…

CFR 781 B. Innokenty and a Football League ( 2SAT )

Problem - B - Codeforces題意: 給 N 個姓名,現在要為每個姓名做縮寫,但希望滿足以下規則: 1. 姓名是 A 的前三個字元,或 A 的前兩個字元接上 B 的第一個字元。 2. 任何縮寫不重複 3. 若對於第 i 個人採取第一種縮寫和第 j 個人採取第一種縮寫會是一樣的…

CFR 781 A. Andryusha and Colored Balloons ( Greedy, DFS )

Problem - A - Codeforces題意: 給一棵 N 個節點的樹,要求給每個節點著色,滿足所有長度為 2 的路徑裡的三個節點都異色。問最少顏色數量。資料規模: N ≤ 2e5解法: 隨便找一個節點當作根,轉為有根樹上的問題。遞迴拜訪一個節點之前先為該節點著色。在當…