作者bleed1979 (十三)
站內Prob_Solve
標題[請益] SPOJ 4300. Rectangles [AE00]
時間Sun Oct 9 00:46:35 2011
http://www.spoj.pl/problems/AE00/
這題大意在於給定n個1 x 1的方塊，可以組成二維平面的幾種不同型式的矩形。
所謂二維就是不能堆高，不同型式的矩形就是翻轉後相同者要去掉。
n個方塊不一定全部用到。
所以，4個方塊。
1) *
2) **
3) ***
4) ****
5) **
**
答案是5。
又，9個方塊。
*
**
***
****
*****
******
*******
********
*********
**
**
***
***
****
****
***
***
***
共13組解。
我寫出以下的accepted code：
#include <cstdio>
int R[10001];
int main() {
R[0] = 0;
R[1] = 1;
for(int i = 2; i <= 10000; ++i) {
R[i] = i;
for(int j = 2; j * j <= i; ++j) {
R[i] += i / j - (j - 1);
}
}
int N;
while(~scanf("%d", &N)) {
printf("%d\n", R[N]);
}
return 0;
}
judge後花費了0.47s。時間複雜度應該是O(N ^ 1.5) (經指正以修改)。
但是排行榜上面幾乎都是0.00s。這應該有O(1)的公式解。
於是我輸出了1到30的解，然後到以下網站搜尋也順利查到了。
http://oeis.org/A094820
看了COMMENTS有符合題意，但是上面沒有附FORMULA。
所以來請益是否能導出公式，謝謝。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.25.241.129
1F：→ firejox:痾...你建表的時間複雜度是O(N^1.5)吧... 10/09 02:03
2F：→ bleed1979:對，是我搞錯了。 10/09 08:28
※ 編輯: bleed1979 來自: 114.43.116.47 (10/09 08:41)
3F：→ LinkCar:我覺得壓不進O(N^1.5) 除非靜態建表作弊吧... 10/09 09:02
4F：推 atoi:可以用找質數那樣篩的去做 順便動手腳就可以0.00了唷 10/09 11:05
大感謝樓上，我把時間推進到了0.03s，算是OK了。
大概是這樣做。
For all i in array R, 我觀察R[i] 和 R[i - 1]，
R[i] 包括 R[i - 1]，並多了長和寬相乘等於 i 的個數。
ex. R[9] = 13, R[8] = 11,
多的2個矩形是 1 * 9 和 3 * 3。
1 * 9是自己，
3 * 3的話，3是9的因數。相當於篩3，只要是因數都要篩。
所以pre calculation如下：
int R[10001] = {0};
R[0] = 0;
R[1] = 1;
for(int i = 2; i <= 10000; i += 2) {
for(int j = i * i; j <= 10000; j += i) {
++R[j];
}
}
for(int i = 3; i <= 10000; i += 2) {
for(int j = i * i; j <= 10000; j += i) {
++R[j];
}
}
加上自己和R[i - 1]如下：
for(int i = 2; i <= 10000; ++i) {
R[i] += R[i - 1] + 1;
}
這樣就搞定了，再次感謝各位的幫忙。
※ 編輯: bleed1979 來自: 114.43.116.47 (10/09 13:19)
5F：推 LPH66:其實這就是 OEIS A094820 的敘述的意思... 10/11 07:26
6F：→ LPH66:所謂"多的"只不過就是面積為該數的矩形 10/11 07:26