Penalty 輸俾 on site champion 幾十
題目較淺
80分鐘 KO 7題
Nope... 喺 UVa 見到啲 Statistic
人地單挑出嚟既成績都接近我地一team人做出黎既成績...
| # | Solved | Score | A | B | C | D | E | F | G | H | I | J | K |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Hussar | 10 | 1055 | 1/48 | 1/56 | -/- | 2/37 | 1/69 | 3/224 | 2/202 | 3/159 | 2/27 | 1/13 | 1/80 |
| GAGGUY+AC | 10 | 1354 | 1/33 | 1/43 | -/- | 4/296 | 3/37 | 1/244 | 1/165 | 1/203 | 1/62 | 1/54 | 1/117 |
| Prof. QQ | 8 | 1361 | 2/117 | 2/73 | -/- | 1/67 | 3/150 | -/- | -/- | 5/303 | 6/152 | 1/7 | 3/192 |
| BDJ | 8 | 1367 | 1/206 | 1/117 | -/- | 2/130 | 3/72 | -/- | 1/- | 3/282 | 4/144 | 1/16 | 3/200 |
飲恨係kick喺條 F - Suffix Array...
感覺明明algo冇錯
double check 過... 武器冇打錯...
又整唔出test case戳得死佢
到兩個鐘之後,終於忍唔住叫 Chin 幫手睇多次
...係我眼力唔好
原來係其中一句, 將 R2 打左做 R
蝕左 116 分鐘 Penalty + 些微諗題目時間
另外 Joe 條 C 都應該差少少過到...
呢條 DP 真係好難下...
望完其它人 program 既 runtime
感覺存在更簡單既 algo
題解簡述：
A - 樹狀DP
(待更新)
B - 水題
C - 貪心／動規？
(待更新)
D - 貪心+排序
盡可能早進遲出
E - 二分
先計算兩人用電量的總和 - Z
對自己用電度數 - X - 進行二分
使得 X + Y = Z
(留意到用電度數愈高，收費愈貴)
F - 後綴數組(Suffix Array) + 最長公共前綴(Longest Common Prefix -LCP)
(待更新)
G - 貪心
正方形的範圍為兩個階梯形狀的 Intersection（見圖；後補...= =)
階梯形狀可以線性時間求出；然後對每個”角落”位置，二分查找正方形最大可能長度
每項 Query 複雜度為 O((M+N) lg(M+N))
(逐漸增大正方形長度，可以把算法加快至 O(M+N))
H - 最大流+貪心
先讓目標隊伍勝出餘下的賽事
然後對每項隊伍，計算最多可以增加的分數... (略)
I - 簡單幾何？
J - 水題
1, 2, 4, ... 64
K - 窮舉
(其中一個)最優分界數值必然符合, T ∈ {0, 0.5, 1, 1.5, ... 1000}
對每個 Division 的數組排序，並記錄一支指針，表示 Advanced 及 Basic 的分水嶺
從小至大枚舉 T ，一邊移動指針，並更新最優答案
複雜度為指針的移動次數，即
(待更新...)
沒有留言:
發佈留言