[已解決] SPOJ 4300. Rectangles [AE00]
看板Prob_Solve (計算數學 Problem Solving)作者bleed1979 (十三)時間13年前 (2011/10/09 00:46)推噓2(2推 0噓 4→)留言6則, 5人參與討論串1/1
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
→
10/09 02:03, , 1F
10/09 02:03, 1F
→
10/09 08:28, , 2F
10/09 08:28, 2F
※ 編輯: bleed1979 來自: 114.43.116.47 (10/09 08:41)
→
10/09 09:02, , 3F
10/09 09:02, 3F
推
10/09 11:05, , 4F
10/09 11:05, 4F
大感謝樓上，我把時間推進到了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)
推
10/11 07:26, , 5F
10/11 07:26, 5F
→
10/11 07:26, , 6F
10/11 07:26, 6F
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
-1
12