[solution] 2019-2020 ACM-ICPC Latin American Regional Programming Contest

• [solution] 2019-2020 ACM-ICPC Latin American Regional Programming Contest
  • pB - Build the Perfect House
  • pF - Fabricating Sculptures
  • pH

pB - Build the Perfect House

性質 B1

答案是否大於等於某個數值

$x$ 具有單調性。

有了 性質 B1，我們就可以二分搜某個

$mid$ 代表正方形的半邊長，並檢查該半邊長是否有辦法找到一種旋轉使得所有給定的點都不會被蓋到。

觀察 B2

每個給定的點，都可以用一個開區間

$({\theta }_l,{\theta }_r)$ 代表當正方形旋轉

$({\theta }_l,{\theta }_r)$ 之間的角度時，會被覆蓋到。

說明

以圖片為例，若正方形旋轉的角度嚴格大於紅線與橘線的夾角並嚴格小於紅線與綠線的夾角，則就會發生重疊。

若一個點與原點的長度

$L<mid$，則該點無論如何都會被覆蓋到；若

$L>\sqrt{2mid}$，則該點一定不會被覆蓋到。

根據 觀察 B2，我們只要檢查所有旋轉的區間是否都被覆蓋到。實作上，可能會將角度限制在

$[0,\frac{\pi }{2})$，這樣比較好處理。因為上面的區間都是開區間，可能要特判是否有覆蓋到

$0$ 或

$\frac{\pi }{2}$ 左邊一點。

筆者實作方法是對區間做差分，做完差分後前綴和，若某個非開頭結尾的時間點數值為

$0$，就代表不是所有旋轉的區間都被覆蓋到。特別的，差分的數值一樣，要讓右區間排在左區間前面，因為所有東西都是開區間。

pF - Fabricating Sculptures

轉化一下題目從下到上一層一層疊方塊，最下面一層的大小必須為

$S$，上面一層用的方塊用的數量不能多於下面一層。

令

$d{p}_{i,j}$ 為「總共有

$i$ 堆，還可以用

$j$ 個方塊，每一堆不一定要用完」。因為最下面一層一定要取，所以我們的所求是

$d{p}_{S,B-S}$。

這樣的狀態會遇到三個狀況：

1. 最下面一列都是方塊，刪掉最下面一列，變成子問題。
2. 最左邊一行沒有方塊了，刪掉最左邊一行，變成子問題。
3. 最右邊一行沒有方塊了，刪掉最右邊一行，變成子問題。

但是 (2.) 跟 (3.) 形成的子問題有可能重複，又就是左右一行同時都沒有方塊，因此要用排容處理掉。

根據上面的狀況，可以列出這樣的轉移：

$$d{p}_{i,j}=\{\begin{array}{ll}0& \text{if }i<0\text{ or }j<0\\ 1& \text{if }j=0\\ d{p}_{i,j-i}+2d{p}_{i-1,j}-d{p}_{i-2,j}& \text{otherwise}\end{array}$$

pH

令

$d{p}_{a,b,c}$ 為當 Alice 是先手，且分數為

$a$，Bob 的分數為

$b$ 時，這回合 Alice 已經累計了

$c$ 點的加分時的勝率。

若

$a+c>75$，則

$d{p}_{a,b,c}=0$；若

$a+c=75$，則

$d{p}_{a,b,c}=1$；若

$a+c=74$，則

$d{p}_{a,b,c}=0$。

$$d{p}_{a,b,c}=max(1-d{p}_{b,a+c,0},\frac{1}{6}(1-d{p}_{b,a,0})+\frac{1}{6}\sum _{i=2}^6(d{p}_{a,b,i+c}))$$

---

---

---

---

---

---

---

---

---

---

---

---