Problem Description
You are required to put n straight lines on a plane, guaranteeing no three lines share a common point and no lines are coincident. They will form some intersections, please output all possible numbers of intersections.
Input
The first line, an integer T(1 ≤ T ≤ 5) - the number of test cases.
Following T lines, an positive integer n(1 ≤ n ≤ 700) - the number of lines.
Output
Several lines, each line several numbers separated by a blank space - all possible numbers of intersections.
Sample Input
2
3
5
Sample Output
0 2 3
0 4 6 7 8 9 10
这个题题意非常短，问的是给定n条直线，问在没有三线共点等情况下能产生多少种不同的交点数。
这个题可以看做HDU1466的加强版。原题给的数据范围是n <= 20，那么就可以用普通的dp求解。如果手玩几个样例，例如n = 5，会发现一开始如果五条线平行的话交点为0，四条线平行一条线与这四条平行线相交的话交点为4，三条线平行，另外两条线互相平行或相交的话交点数为6或者7...可以看出来平行线的存在能够将问题规模缩小。因为如果x条线相互平行，另外y条线任意（但不与这x条线平行）的话，总的交点数就是y条线自己产生的交点数 + x * y，原因就是y条线中的每条线都与x条平行线产生x个交点。
这样就可以进行dp了，设(dp[i, j])为用i条直线产生j个交点是否可行，k为i条线中相互平行的线的数量，则转移方程为(dp[i, j] |= dp[i - k, j - (i - k) imes k])。其中i - k就是任意的线的数量，(i - k) * k就是任意的线与平行线产生的交点数。这样就可以轻松通过HDU1466这道题了。
#include <bits/stdc++.h>
using namespace std;
const int N = 25;
const int NN = N * N / 2;//交点数最多有这么多
bool dp[N + 5][NN + 5];//dp[i][j]表示用i条直线凑出来j个点是否可行
void init() {
for(int i = 0; i < N; i++) dp[i][0] = 1;
for(int i = 1; i <= N; i++) {
for(int j = 1; j <= NN; j++) {
for(int k = 0; k < i; k++) {//k条直线平行
if(j - (i - k) * k >= 0) dp[i][j] = dp[i][j] | dp[i - k][j - (i - k) * k];
}
}
}
}
void solve(int n) {
vector<int> ans;
for(int i = 0; i < NN; i++) {
if(dp[n][i]) ans.push_back(i);
}
for(int i = 0; i < ans.size(); i++) {
if(i != ans.size() - 1) cout << ans[i] << " ";
else cout << ans[i] << endl;//注意行末空格
}
}
int main () {
cin.tie(0);
ios::sync_with_stdio(false);
init();
int n;
while(cin >> n) {
solve(n);
}
}
然而对于比赛的这道题，n的范围陡然增加到了700，上述代码的时间复杂度为(O(n^4))，显然时间上无法通过，而且有爆内存的风险。那么就要考虑进行优化，一种可行的方案是使用bitset进行优化。观察上面代码，第二重循环实际上直接贡献了(n^2)的复杂度，那么借助bitset，我们可以把它优化成(O(frac{n^2}{w}）)。具体来说，对于每一个i维护一个bitset,bitset的大小为(frac{n imes (n - 1)}{2})，在循环里直接省略掉原先的第二重循环，同时把转移方程的写法改为dp[i] = dp[i] | dp[i - k] << ((i - k) * k);这里相当于整体进行或操作而不是单独进行遍历，借助bitset的玄学操作可以带来不小的提升。因为左移会在低位补0，因此也不用像上面代码一样担心越界的问题。
#include <bits/stdc++.h>
using namespace std;
const int N = 700;
const int NN = N * N / 2;
bitset<NN + 5> dp[N + 5];
void init() {
for(int i = 0; i < N; i++) dp[i][0] = 1;
for(int i = 1; i <= N; i++) {
for(int k = 0; k < i; k++) {
dp[i] = dp[i] | dp[i - k] << ((i - k) * k);
}
}
}
void solve(int n) {
vector<int> ans;
for(int i = 0; i < NN; i++) {
if(dp[n][i]) ans.push_back(i);
}
for(int i = 0; i < ans.size(); i++) {
if(i != ans.size() - 1) cout << ans[i] << " ";
else cout << ans[i] << endl;
}
}
int main () {
cin.tie(0);
ios::sync_with_stdio(false);
init();
int n;
while(cin >> n) {
solve(n);
}
}
然而本地跑一下会发现init()函数执行的时间还是非常长（需要好几秒才能进行查询），瓶颈在于bitset开的实际上非常大。这时候就需要继续进行优化。比赛的时候发现当输出了若干个数以后，后面的数都是连续的，通过对拍程序测试一下n = 20的时候100以后基本都是连续的，猜想可能是大约5倍以上后面就都是连续的了（然而是错的），题解给的界限是31500，这样的话bitset实际上只需要开到这个上界就足矣，i大于上届的话直接输出即可，这样就能通过本题了。
#include <bits/stdc++.h>
using namespace std;
const int N = 700;
const int NN = N * N / 2;
#define MX 35000
bitset<MX> dp[N + 5];//dp[i][j]表示用i条直线凑出来j个点是否可行
void init() {
for(int i = 0; i <= N; i++) dp[i][0] = 1;
for(int i = 1; i <= N; i++) {
for(int k = 0; k <= i; k++) {
dp[i] = dp[i] | (dp[i - k] << ((i - k) * k));
}
}
}
void solve(int n) {
vector<int> ans;
int lim = min(MX - 1, n * (n - 1) / 2);
for(int i = 0; i <= lim; i++) {
if(dp[n][i]) ans.push_back(i);
}
for(int i = lim + 1; i <= n * (n - 1) / 2; i++) ans.push_back(i);
for(int i = 0; i < ans.size(); i++) {
if(i != ans.size() - 1) cout << ans[i] << " ";
else cout << ans[i] << endl;
}
}
int main () {
cin.tie(0);
ios::sync_with_stdio(false);
init();
int t;
cin >> t;
while(t--) {
int n;
cin >> n;
solve(n);
}
}