前言
题目链接:洛谷。
题意简述
你需要构造一个 \(1 \sim n\) 的排列 \(a\),满足 \(m\) 个条件,格式如下:
-
1 x y v
:\(\max \limits _ {i = l} ^ r a_i = v\)。 -
2 x y v
:\(\min \limits _ {i = l} ^ r a_i = v\)。
题目分析
首先这个最值很难受,考虑能不能转化成我们喜欢的二元关系。比如,当 \([l, r]\) 的最值为 \(v\) 时,说明 \(v\) 必须出现在这段区间内。再思考一下,对于最大值,为了保证这段区间的最大值是 \(v\),那么大于 \(v\) 的数就不能出现在这段区间内,最小值同理。把前者“必须出现”转化为补集的“不能出现”,这样我们处理出了对于每一个值 \(v\) 不能出现的位置。
有什么用呢?我在膜尼赛上用爆搜骗分。直接骗肯定不好看,这时候就需要一些常见的剪枝优化。对于限制类题目,我们把限制多的先搜索能节约不少时间。此外,寻找到一个没有确定的位置可以使用双向链表优化。预处理区间覆盖转化为差分。能够得到 \(86\) 分的好成绩。
话说回来,这么搜肯定是错的,那还有什么做法呢?我们必须敏感地注意到位置和值的特殊二元关系。到了最后,每一个位置一定一一对应一个值,将“不能”反转得到若干“可能”的匹配关系,最后的对应一定这些可能匹配中的一种。
不妨继续抽象模型。有红黄两种颜色的小球各 \(n\) 个,我们知道了每一个红球可能和哪些黄球匹配,找到一种匹配方式,使得红黄球一一对应。这不就是二分图的裸题了吗?我们将可能得匹配方式看作是值向位置的连边,最终的答案就是位置对应的那个值。
注意到存在无解的情况,此时说明二分图不存在完美匹配,判断即可。
时间复杂度理论上来说可以优化到:\(\Theta(m \log n + n^{\frac{5}{2}})\),但是可能比不过常数小的 \(\Theta(nm + n ^ 3)\)?
代码
#include <cstdio>
#define isdigit(x) ('0' <= x && x <= '9')
inline void read(int &x) {
x = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar());
for (; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
}
const int N = 220;
int n, m, val[N], mi[N], mx[N], cant[N][N];
int to[N * N], nxt[N * N], head[N], tot;
int vis[N], timer, mark[N];
bool dfs(int now) {
for (int i = head[now]; i; i = nxt[i]) {
int to = ::to[i];
if (vis[to] != timer) {
vis[to] = timer;
if (!mark[to] || dfs(mark[to])) {
mark[to] = now;
return true;
}
}
}
return false;
}
signed main() {
read(n), read(m);
for (int i = 1; i <= n; ++i) mx[i] = n;
for (int i = 1, op, l, r, v; i <= m; ++i) {
read(op), read(l), read(r), read(v);
++cant[v][1], --cant[v][l];
++cant[v][r + 1], --cant[v][n + 1];
for (int j = l; j <= r; ++j) {
if (op == 1)
v < mx[j] && (mx[j] = v);
else
v > mi[j] && (mi[j] = v);
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
cant[i][j] += cant[i][j - 1];
if (mi[j] <= i && i <= mx[j] && !cant[i][j]) {
to[++tot] = j;
nxt[tot] = head[i];
head[i] = tot;
}
}
}
for (int i = 1; i <= n; ++i) {
++timer;
if (!dfs(i)) return puts("-1"), 0;
}
for (int i = 1; i <= n; ++i) printf("%d ", mark[i]);
return 0;
}
总结 & 反思
说实话,都想到爆搜,想不到二分图匹配确实不应该,应该归根结底是二分图模型不熟悉了。
二分图是处理两种不同类型的物件之间的对应关系。对于本题,一个排列的构造,我们如果能找出值和下标的二元关系,就能建立二分图,跑匹配,最后输出匹配的方案。
标签:二分,匹配,题解,位置,二元关系,COCI2012,区间,INFORMACIJE From: https://www.cnblogs.com/XuYueming/p/18389339