作者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