HKG Time - 1320 to 1815
OJ提交：
賽情：
- (我們開了 scoreboard simulation) 在封 board 前一分鐘 4 條，遙遙落後於中遊隊伍
- Joe 在 239 min Accept B，士氣大增!! (?)
- 最後一小時通過 3題!! 以題數獲得 第2 !!
- (詳情參下)
| Rank | Name | Solved | Time | A | B | C | D | E | F | G | H | I | J |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | THU_Dubhe | 9 | 1369 | 1/33 | 2/107 | 1/77 | 1/188 | 1/62 | -/- | 1/261 | 4/221 | 1/51 | 1/289 |
| 2 | ManiAC | 8 | 1902 | 1/28 | 5/239 | 2/74 | 1/292 | 2/101 | 9/280 | -/- | 7/277 | 1/211 | -/- |
| 3 | *SJTU_Luminer | 7 | 948 | 1/31 | 2/201 | 1/117 | 1/137 | 1/96 | -/- | -/- | -/- | 1/76 | 4/210 |
| 4 | ZJU_NFA | 7 | 990 | 2/67 | 2/194 | 2/106 | 1/46 | 1/135 | -/- | -/- | -/- | 1/119 | 2/243 |
| 5 | THU_CST0213 | 7 | 1016 | 2/65 | 1/213 | 1/138 | 1/254 | 1/86 | 1/215 | -/- | -/- | 1/25 | -/- |
| 6 | SJTU_ViGoR | 7 | 1046 | 2/67 | 1/116 | 1/69 | 1/38 | 1/174 | -/- | -/- | -/- | 3/273 | 2/229 |
| 7 | FZU_OpenGL | 7 | 1086 | 1/37 | 2/188 | 1/149 | 1/131 | 3/98 | -/- | -/- | -/- | 1/64 | 4/299 |
| 8 | HRBEU_Blue Sky | 7 | 1143 | 4/166 | 1/232 | 1/120 | 1/106 | 1/152 | -/- | -/- | -/- | 1/43 | 1/264 |
| 9 | THU_machinator | 6 | 742 | 2/54 | 1/117 | 1/139 | 1/261 | 1/66 | -/- | -/- | -/- | 1/85 | -/- |
| 10 | HDU-Knuth | 6 | 858 | 4/69 | 3/258 | 2/171 | 1/119 | 1/88 | -/- | -/- | -/- | 1/33 | -/- |
是次 Training Joe 塞了許多容易至中等難度的題目給我做 @@
[不計算自己看及想的 Problem A (直接暴力)]
他們在早段談了 C 的算法後就把它塞給我
特別又想說一下由 Joe 提供算法，由我 code 的 Problem H...
做得很差... 一連犯了許多個低給錯誤，包括：
- 計算圓/圓交點時，只移除了 || c_i - c_j || > || r_i + r_j || 的情況
卻沒有移除 || c_i - c_j || < || r_i - r_j || 的情況 - 計算圓/圓交點時，把 cosine 及 sine 的正負號弄錯了
- 建圖時，把嚴格包括在圓內的點加進去
- 陣列大小開得太小了
本來打算塞給我用質因數分解做
但想了片刻貌似未能承受如此複雜度...
(由於老早有隊伍 AC，所以我一直認為代碼量一定很短)
幸好在 training 尾段最後說服了Joe (其實是因為沒有其它事可以做)
頹 code Java BigInteger 通過
算法精簡概要：
A: 純暴力
B: 樹狀DP
C: 最大權最大匹配 (Maximum Weighted Bipartite Matching)
D: Catalan Number + BigInteger
E: 字典串 (Trie)
F: DP+斜率優化 (CTLi 用令類方法水過..-.-)
G: 疑似... Merge Balanced Binary Search Tree
H: 圓圓交點 + 圖遍歷 (DFS/BFS)
I: 貪心
J: Kth element
距離大家人生最後一場 ACM 比賽還有兩個月時間...
ManiAC... 努力吧!!
沒有留言:
發佈留言