ZJ i253 - 正三角形非常好…差不多一樣凸多邊形 題解

<<回主頁

針對不同的

$K$ 做討論

雖然本題

$K\le 100$，但其實我們可以先討論一些

$\text{case}$ ，如果

$K\ge 7$ 時，因為用正三角形的緣故，角度只能組合出

$60°$ 或

$120°$ ，而如果

$K=7$，已知七邊形的內角和為

$900°$，而

$900/7=128.57>120$，所以發現

$K\ge 7$ 時一定組不出來 (不論

$N$ 如何，更大的

$K$ 算出來平均只會更大)，所以接著我們只要討論

$3\le K\le 6$ 的情況即可。

$K=3$

三角(邊)形的內角和為

$180°$，只有一種拆法 :

$60+60+60$，也就是是正三角形的時候，所以其實如果

$N$ 是完全平方數的時候就可以構造出來，否則就不行，這個檢查可以用

$O(\sqrt{N})$ 或

$O(logN)$ 的複雜度求得 (根據實作方法) 。

$K=4$

以上是一個構造方法，發現只要

$N\ge 2$ 都有解 (梯形) 。

$K=6$

我們先不討論

$K=5$ ，因為其實他和

$K=6$ 很相似。

其實每個六邊形都可以分成像這樣，三個部分，會發現綠色部分是類似平行四邊形這樣，然後藍色跟紅色的的部分是等腰梯形，我們如果像上圖一條一條線算他們的三角形數，會變成下面這樣(假設綠色的一條是

$x$) :

綠色 :

$x+x+x+...+x$
紅色 :

$(x-1)+(x-3)+(x-5)+...+y$
藍色 :

$(x-1)+(x-3)+(x-5)+...+z$

我們可以窮舉

$x,y,z$ ，然後先算出紅色及藍色的面積，然後綠色的面積其實就會是

$N$ - 紅色 - 藍色，然後檢查這東西能否整除

$x$ 就好了。

那

$x,y,z$ 的上界要到多少呢，一般來說應該要是到

$N$，但是其實一個六邊形可以想像成一個大的正三角形截去三個角，所以其實弄到

$\sqrt{N}$ 就行了，因此檢查一個的時間複雜度是

$O(N^{1.5})$。

$K=5$

同上面的解法，把

$x,z$ 其中一個固定成

$1$ 就是

$K=5$ 的解法了。

結論

我們可以發現不管哪一種

$\text{case}$ 最多一筆測資需要

$O(N^{1.5})$ 的時間判斷，

$T$ 筆就是

$O(T\cdot N^{1.5})$，已經足夠快通過。 (感謝 Ststone 提供解題方向) 另外，如果改變一下實作方法，其實也可以做到

$O(N^{1.5}+T)$，不過這題

$T\le 10$，所以本來的方法其實就夠快了。

後面是一些偷吃步 :

$K=5,6$ 的情況，其實有試著在本機建表過 (跑完所有小於

$10000$ 的

$N$ )，但其實最後一組不能構造出來的

$N$ 遠小於題目的範圍限制 (這點我還不知道怎麼證明)，所以其實本機建表也不是行不通，然後感謝 inversion 這篇 blog 其實有提到相關的方法，他也有說有一篇論文就是在證明

$K=5,6$ 的補集是有限集合，有興趣的可以參考看看。