又是掉大分场。
赛时前面两题还做得挺快，然后到 C 就卡住了。
\(2n\) 个点排在圆上，满足没有连成的弦三线共点。有 \(k\) 条弦以确定，请连 \((n-k)\) 条弦使交点最多，弦和弦不能共端点。
赛场上一直想着怎么处理新加进去的弦和原来弦的关系，然后就什么也没有想到。
先考虑我们要新连上去的弦的相交关系。把这些点重新编号 \(1 \to 2(n-k)\)， 这样的话，\(i\) 和 \(i+n-k\) 相连就是最优的了。因为在这种情况下无论交换哪俩端点都只能使两条弦变得不相交，从而减少交点。
然后再考虑这些弦和原来已有的弦的相交情况。你会惊奇的发现，这样的安排也是最优的，因为交换同样不能让它有更多的交点。
那么构造好再判交点就行了。
代码
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#define mapa std::make_pair
#define fi first
#define se second
const int N = 205;
int T, n, k;
bool inter(std::pair<int, int> x, std::pair<int, int> y) {
if (x.fi > y.fi) std::swap(x, y);
return x.se > y.fi && x.se < y.se;
}
int main() {
std::cin >> T;
while (T--) {
std::cin >> n >> k;
std::vector<std::pair<int, int> > ch;
std::vector<bool> vis(2*n+1);
for (int i = 1, x, y; i <= k; i++) {
std::cin >> x >> y;
if (x > y) std::swap(x, y);
ch.push_back(mapa(x, y));
vis[x] = vis[y] = 1;
}
std::vector<int> unu;
for (int i = 1; i <= 2*n; i++)
if (!vis[i]) unu.push_back(i);
for (int i = 0; i < n-k; i++)
ch.push_back(mapa(unu[i], unu[i+n-k]));
int ans = 0;
for (int i = 0; i < n; i++)
for (int j = i+1; j < n; j++)
if (inter(ch[i], ch[j])) ans ++;
std::cout << ans << ‘\n‘;
}
}
其实这题根本不难，赛场上有 \(2000+\) 的人过，但我确实没有什么想法。
平时要对这些没有什么高级技巧的题多练习啊。