2010-08-03 Team Training - SWERC 2005

(整理中)

• 題目在這
  
• On Site Scoreboard
• Test Data + Reference
• 官網在這

這次的 SWERC 的題目
比起上兩次的 CEPC 輕鬆多了

今天我們 team （= Joe + Kn + Bill） solve 了 6 題
（Gagguy 獨力 solve 了 7 題!!）

飲恨是 Joe 的 題G... 只差一點點
題F 沒有想出算法... 這個有點過不去
題I 剛剛 AC了... 原來 problem statement 想暗示 test data 很弱
題J 也 AC 了... 算法不太難想，理論上應該也可以 AC 的...但前提是前幾題要做得足夠快

---

Problem A: ICPC 3502 The mysterious X network (Bill)

解：水題 ── BFS

---

Problem B: ICPC 3503 Bin Packing (Bill)

解：水題 ── 貪心

---

Problem C: ICPC 3504 On Storing Clothes (Kn)

解：簡單模擬


要小心的 Case 包括 一次過掛 N-1 件衣服 

---

Problem D: ICPC 3505 Buy or Build (Kn)

解1：256 次 MST

枚舉全 2⁸ 種 subnetwork 的選取方法
分別做 MST

Worst-case time complexity = O(256 × 1000²)...
在 Joe 強力鼓勵下
暴力硬搞 AC 了...

解2：256 次 MST on MST (Leo 提出的)

1. 對原圖 (complete graph) 做第一次 MST
2. 同樣對全 2⁸ 種 subnetwork 的選取方法做 MST但只考慮 1. 得出的 MST 裏面，那 O(1000) 條 edge

複雜度降至 O(256×1000) + O( log(1000×1000) × 1000×1000 )

---

Problem E: ICPC 3506 4 Values whose Sum is 0 (Bill)

解(Bill)：Ad-hoc

time limit 和 memory limit 都很寬鬆基本上不是最暴力的方法都可以通過...

---

Problem F: ICPC 3507 Keep the Customer Satisfied

解：貪心

---

Problem G: ICPC 3508 UFO Cubes in Roswell

解：模擬 ── 需要observation

---

Problem H: ICPC 3509 Black Box (Kn)

解：模擬 ── 「就是做！」

---

Problem I: ICPC 3510 Pixel Shuffle

解：Flood-fill、找 Cycle

---

Problem J: ICPC 3511 Consecutive ones

解：暴力搜索

O(N^N) DFS 枚舉...
legal 繼續
illegal 返回

---

有時間再補充