[請益] SPOJ 4300. Rectangles [AE00]

[bleed1979 (十三)]

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
→ firejox:痾...你建表的時間複雜度是O(N^1.5)吧...
→ bleed1979:對，是我搞錯了。
※ 編輯: bleed1979       來自: 114.43.116.47        (10/09 08:41)
→ LinkCar:我覺得壓不進O(N^1.5) 除非靜態建表作弊吧...
推 atoi:可以用找質數那樣篩的去做 順便動手腳就可以0.00了唷
大感謝樓上，我把時間推進到了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)
推 LPH66:其實這就是 OEIS A094820 的敘述的意思...
→ LPH66:所謂"多的"只不過就是面積為該數的矩形