隨便寫寫,不一定對,有誤請指出。
感覺考慮反向問題「給定的氣數下最多能擺多少棋子」會更簡單一些。
觀察一些簡單的結構:
?*?
XXX
在這種結構中,無論 ? 的情況如何,只要 X 處全有子,那麽,在 * 處也放子,氣的數量不會增加。
X*?
?XX
同上。
所以答案的邊界一定:
所以答案一定形如:四個方向上最遠的邊的長度為 1 或 2,它們之間用 45° 折線連線。
考慮按這四條邊的長度對這種圖案進行分類,依次為 1111 1122 1212 2222 分別稱為 A B C D。
除了 1122 情形外可以證明「對邊」長度必然相等,且長寬之間對稱。1122 情形規定兩個 1 之間的折線段長度為寬 m ,12 之間的折線段長度為長 n 。長寬都是指由多少個 270° 拐彎構成。
那麽
氣 | 面積 | |
---|---|---|
A(n,m) | 2n+2m+4 | 2nm+n+m+1 |
B(n,m) | 2n+2m+5 | 2nm+n+2m+1 |
C(n,m) | 2n+2m+6 | 2nm+2n+2m+2 |
D(n,m) | 2n+2m+8 | 2nm+3n+3m+4 |
2k 氣時可以用 A 或 C 或 D 得到 \lfloor (k-2)^2/2\rfloor +k-1 或 \lfloor (k-3)^2/2\rfloor+2k-4 或 \lfloor (k-4)^2/2\rfloor+3k-8 個子。前者大於等於後兩者。寫出來就是 \lfloor(k^2-2k+2)/2\rfloor 。
2k+1 氣時可以用 B 得到 k(k-1)/2 個子。這比退化的前者要大。
最終可以得到 t 氣最多 \lfloor t^2/8-t/2+1\rfloor 子。
反過來寫就是 x 子最少 \lceil2+\sqrt{8x-4}\rceil 氣。