「HDU 2021 Multi 10」[HDU 7079] Pty loves lines

「题意」

求在一个平面上 $n$ 条线(不存在多条线重叠和 $k(k>2)$ 线共点的情况)所有可能的交点个数。

$n\leq 700$

「链接」

7079

「分析」

$f(i,j)$ 表示 $i$ 条线组成 $j$ 个交点的可能性,通过枚举平行线的数量,得到递推式 $f(i,j) |= f(i,j-k\times(i-k))$。

这可以用bitset转移优化,复杂度 $O(\frac{n^4}{w})$。

注意到 $n\leq 700$,打表发现当 $j>35000$ 时,$f(i,j)=1$。因此bitset只需要维护前 $35000$ 位。

复杂度 $O(\frac{n^2\times 35000}{w})$。

「参考代码」

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>

using namespace std;
const int MAXN = 700 + 5;
const int MAXM = 40000;

bitset<MAXM> p[MAXN];

int main() {
int mx = 700;
for (int i = 0; i <= mx; i++) p[i][0] = 1;
for (int n = 2; n <= mx; n++) {
for (int i = 1; i < n; i++)
p[n] |= p[n - i] << (i * (n - i));
}
int T, n;
scanf("%d", &T);
vector<int> v;
while (T--) {
scanf("%d", &n);
v.clear();
int up = n * (n - 1) / 2;
for (int j = 0; j <= min(up, 39999); ++j) {
if (p[n][j]) v.push_back(j);
}
for (int j = 40000; j <= up; ++j) v.push_back(j);
for (int i = 0; i < v.size(); ++i) printf("%d%c", v[i], " \n"[i == v.size() - 1]);
}
return 0;
}