2010-06-29 Individual Training

今天仍然選了比較難的題

6題之中，在4小時內只把3題做出來... 感覺有點差...-_-
Parsing (題A) 及 Greedy (題F) 卡了太久... 沒有時間做剩下的題
還好最後仍然把那道 2D Geometry (PKU 2036!) 做出來...

今次的題目涵蓋了 2D Geometry、Parsing／String Processing、Simulation、DP、Integration，算是相當全面，而且比較煩。在考驗編程技巧同時，亦要求謹慎小心。值得一提的是，自己在 PKU 2065(題F) 學了一樣很多人早已知道的事實（見下）。

這一 set題目 是比較難+煩... 所以表現不理想大家也不要灰心！

---

Problem A: PKU 2372 D++ Again
問：（講起我就扯火...）自己看！這題目就是考驗閱題！
（縱使 AC 過後我依然覺得題目寫得不夠清楚...-_-）
注：最後栽在這 Test Case...
　　"(*(**)" - YES
解：用 stack 記錄現在到 Arithmetic expression 中第幾層括號，另外記錄當前是否在 Comment 之中，小心處理 "(*"

---

Problem B: PKU 3442 Baseball
問：模擬棒球球賽
解：小心解題，然後就是做！

---

Problem C: PKU 3289 Moonshine
問：（如下圖）給定 h, h_b, h_n, k 及上下底圓的半徑，當瓶子水平放下時，求 s

解：二分 + 數值積分 (Numerical Integration)
最難在於求出中間部份（把Cone旋轉使軸水平，然後打橫切一刀剩下來的-.-）的體積
在這兩三天，我好幾次嘗試求出其不定積分，未果
只好上網搜一下，發現貌似這個不定積分是求不出來的...
或者只好橫切面切成很多份迫近答案吧...
有時間會試一下

---

Problem D: PKU 2036 I Conduit!
問：在白紙上要畫 N (≤ 10000) 條線段 (Straight line segment)，問總共最少要畫多少筆
解：排序→掃描
大意如下：

struct E { // 線段 a→b
　　Pt a, b, dir;
　　double distToOrigin;
　　double t1, t2;
};

1) 按 方向(dir) → 與原點距離(distToOrigin) → a在dir的投影(t1) 排序
2) 一邊掃描，一邊 merge 線段，統計答案

詳參另一篇 Blog Entry

---

Problem E: PKU 3718 Facer's Chocolate Dream
這題 Guarder... 是 杭州2008 題B 的進化版本！
嗯... 較難的題，暫時略過～

---

Problem F: PKU 1065 Wooden Sticks
問：給 N 個 int-pair，用最小數量的 increasing sequence S s.t. S[i-1].x ≤ S[i].x & S[i-1].y ≤ S[i].y，去覆蓋全部 N 個 pair
解1：貪心
把這些 pair 由小至大（by x then by y）sort好，設這個 sorted sequence 為 A[N]
對每個 A[i]，找出一個未使用的 A[j]（j ≤ i），使得 A[j] ≤ A[i]
若選擇多於一個，選當中 y 最大的
若依然多於一個，選當中 x 較大的
解2：DP
Fact： 以最小數量的 "≤ Subsequence" 覆蓋 Sequence = Longest "< Subsequence" 的長度
把這些 pair 由小至大（by x then by y）sort好，只考慮 y
答案 := Longest Strictly Decreasing Subsequence 的長度