T1 廊桥分配
\(Lemma:\) 对于已经存在的廊桥集合，加入新的廊桥不会影响之前分配好的航班。
证明： 由于题目所给限制，若有空廊桥，则航班一定会停在空廊桥，直至该航班离开，廊桥再次空置，下一个符合条件的航班使用该廊桥。有空置廊桥不必讨论；而在所有廊桥都被占满的期间，显然加入新的廊桥不会影响已经停靠的航班。
而国内和国际航班是独立的，因此分别讨论即可。维护一个航班的序列，枚举廊桥个数 \(1\)~\(n\)（\(0\) 不必枚举，因为必然妹有飞机停靠在廊桥）。设已经分配了 \(k\) 个廊桥，每当廊桥个数 \(+1\)，即加入一个空廊桥（显然不影响已经分配好的\(k\)个廊桥和航班），将剩余未停靠航班中最先到的航班取出并使它“停靠在廊桥”，然后删除该航班，继续枚举下一个符合条件的航班并从航班序列中删除，直至不存在符合条件的航班。
这样做可以看作维护了很多个“航班集合”，这些航班集合满足了时间区间互不相交，且按抵达时间排列。
一种实现方法如下：
void count(int n, int *cnt) { // cnt[k] 表示k个廊桥可以停靠的航班数
for(int i = 1; i <= n; ++i) {
int pos = 0, idx = 0;
// s为现存航班序列，按照左端点排序（为什么？请读者思考）
while(true) {
it = s.lower_bound(flight(pos, 0));
if(it == s.end()) break;
pos = (*it).r;
s.erase(it);
++idx;
}
cnt[i] = cnt[i - 1] + idx;
}
}
分别处理国内和国际航班得到两个 \(cnt\) 数组，答案即为 \(\max \limits_{i=0}^{n}cnt_i+cnt^{'}_{n-i}\)。
注意坑点 \(i\) 从 \(0\) 开始枚举而不是 \(1\)，因为国内（或国际）航班的廊桥个数可以为 \(0\)。
完整代码见文末（请勿抄袭）。
未完待续
各题完整代码
T1 廊桥分配
#include <bits/stdc++.h>
using namespace std;
struct flight {
int l, r;
bool operator < (const flight &x) const {
return l < x.l;
}
flight(int a, int b) : l(a), r(b) {}
};
set<flight> s;
set<flight> :: iterator it;
const int N = 1e5 + 5;
int cnt1[N], cnt2[N];
void count(int n, int *cnt) {
for(int i = 1; i <= n; ++i) {
int pos = 0, idx = 0;
while(true) {
it = s.lower_bound(flight(pos, 0));
if(it == s.end()) break;
pos = (*it).r;
s.erase(it);
++idx;
}
cnt[i] = cnt[i - 1] + idx;
}
}
int main() {
int n, m1, m2, ans = 0;
scanf("%d %d %d", &n, &m1, &m2);
for(int i = 1, x, y; i <= m1; ++i)
scanf("%d %d", &x, &y), s.insert(flight(x, y));
count(n, cnt1);
s.clear();
for(int i = 1, x, y; i <= m2; ++i)
scanf("%d %d", &x, &y), s.insert(flight(x, y));
count(n, cnt2);
for(int i = 0; i <= n; ++i)
ans = max(ans, cnt1[i] + cnt2[n - i]);
printf("%d\n", ans);
return 0;
}