#21720: 加速方法


yes51851823@gmail.com (wseds)

School : 國立花蓮高級工業職業學校
ID : 108813
IP address : [111.243.205.152]
Last Login :
2021-09-19 13:00:20
e355. Squares and Rectangle in Rectangle -- TIOJ 1015 改編 | From: [114.37.241.197] | Post Date : 2020-07-11 23:03

首先 求長方形數量的方式可以用組合 (N+1)取2 × (M+1)取2

如果建立10000格陣列跑一遍儲存,每次輸入時計算長方形數量只需O(1)

 

 

再來是正方形數量 假設N=5,M=6

求正方形數量的方法為 6×5+5×4+4×3+······+2×1

其實也就是1×2+2×3+······+5×6

以sigma表示就是

==> ==> 

其實上面的5就是N和M中較小的數 1×k的1是|M-N|得到的

所以利用公式搭配algorithm找出大小 如果傳給函式的N是兩數中較小者、M是較大者的話 就會變成

N*(N+1)*(2*N+1)/6+(M-N)*((1+N)*N/2)

如此一來求正方形數量的方法就會變成O(1)囉~

 
#21721: Re:加速方法


yes51851823@gmail.com (wseds)

School : 國立花蓮高級工業職業學校
ID : 108813
IP address : [111.243.205.152]
Last Login :
2021-09-19 13:00:20
e355. Squares and Rectangle in Rectangle -- TIOJ 1015 改編 | From: [114.37.241.197] | Post Date : 2020-07-11 23:08


以sigma表示就是


抱歉 文章內圖片消失@@

 
#21722: Re:加速方法


yes51851823@gmail.com (wseds)

School : 國立花蓮高級工業職業學校
ID : 108813
IP address : [111.243.205.152]
Last Login :
2021-09-19 13:00:20
e355. Squares and Rectangle in Rectangle -- TIOJ 1015 改編 | From: [114.37.241.197] | Post Date : 2020-07-11 23:12


以sigma表示就是


抱歉 文章內圖片消失@@


因為我實在不知道為甚麼圖片丟上來會消失 所以只好放這邊了@@
https://ppt.cc/fxbFvx@.jpg

 
ZeroJudge Forum