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

「题意」

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

n700n\leq 700

「链接」

7079

「分析」

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

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

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

复杂度 O(n2×35000w)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;
}