竹園論壇

標題: a888 - C. 混色模式 (NPSC2013 國中組初賽) [打印本頁]

作者: domen111 時間: 2014-11-25 15:41
標題: a888 - C. 混色模式 (NPSC2013 國中組初賽)
本帖最後由 domen111 於 2014-11-25 16:02 編輯

之前一直覺得好難(可能是因為我一直推Sigma的公式的關係吧)，今天頭腦突然想通了就覺得好像也沒多難

基本的上的想法是線性搜尋中間線(紅線)，將長方形切割成左右兩部分，左右兩部分分別求出方法數，相乘就是答案了。

(圖一)

問題: 不會有左右交叉的問題嗎? 如圖二
這就是我之前一直糾結很久的問題，事實上其實只要中間線切割的是長方形的長邊就不會有這個問題，所以第16行寫個判斷就一切解決。

(圖二)

好了，既然我們現在已經有了基本的想法，那麼下一步就是求左邊和右邊有多少種方法
左半部:
我們定義左半部較大的那塊正方形一定要貼齊中間線，否則可能會有重複計算的問題(假設左右半部都沒有貼齊中間線，可能同種情形不同中間線都會算到)
首先我們假設左上角的正方形>=左下角的正方形，既然一定要貼齊中間線，表示已經確定左上角的大小，那麼計算左下角的正方形有幾種方法數就ok了。
注意(我一開始寫出的小bug): 第21行，如果已經不可能貼齊中間線了就break
右半部:
比左半部複雜一些，自己推一下公式，我的code的解法用cal的function去計算，不過事實上不用那麼麻煩，因為我的cal function是支援兩個方形上限大小不同的情形 (那是我之前在想一個很複雜的作法時推出的公式)

歡迎光臨竹園論壇 (http://forum.tfcis.org/)