#21720: 加速方法
yes51851823@gmail.com
(wseds)
學校
:
國立花蓮高級工業職業學校
編號 : 108813
來源 : [36.227.245.149]
最後登入時間 ：
2024-04-16 01:11:16
e355. Squares and Rectangle in Rectangle
--
TIOJ 1015 改編
| From: [114.37.241.197] |
發表日期
:
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)
學校
:
國立花蓮高級工業職業學校
編號 : 108813
來源 : [36.227.245.149]
最後登入時間 ：
2024-04-16 01:11:16
e355. Squares and Rectangle in Rectangle
--
TIOJ 1015 改編
| From: [114.37.241.197] |
發表日期
:
2020-07-11 23:08
以sigma表示就是
抱歉 文章內圖片消失@@
#21722: Re:加速方法
yes51851823@gmail.com
(wseds)
學校
:
國立花蓮高級工業職業學校
編號 : 108813
來源 : [36.227.245.149]
最後登入時間 ：
2024-04-16 01:11:16
e355. Squares and Rectangle in Rectangle
--
TIOJ 1015 改編
| From: [114.37.241.197] |
發表日期
:
2020-07-11 23:12
以sigma表示就是
抱歉 文章內圖片消失@@
因為我實在不知道為甚麼圖片丟上來會消失 所以只好放這邊了@@
https://ppt.cc/fxbFvx@.jpg
ZeroJudge Forum