「Sorting Slide」排版幻灯片

形式化题目

平面上有 $n$ 个矩形（幻灯片） $R_1, \dots, R_n$ 和 $n$ 个点（编号数字） $p_1, \dots, p_n$ 。一个分配是编号到幻灯片的双射 $f$ ，满足 $p_i \in R_{f(i)}$ （点在矩形闭区域内）。对每张幻灯片 $s$ ，若所有分配中分给它的编号都相同（记为 $i$ ），则输出配对 $(s, i)$ ；若没有任何幻灯片能被这样唯一确定，输出 none。

正解

思路

第一步：把"唯一确定"翻译成图论语言。 把编号 $1..n$ 和幻灯片 $A, B, C, \dots$ 看作二分图的两侧，若点 $p_i$ 落在矩形 $R_s$ 内，就在编号 $i$ 与幻灯片 $s$ 之间连一条边。一个合法分配恰好是这张图的一个完美匹配；幻灯片 $s$ 的编号被唯一确定，意思是"配对 $(i, s)$ 出现在每一个完美匹配中"——这样的边叫必须边。

必须边有一个好刻画的等价定义：

(i, s) \text{ 是必须边} \iff \text{删掉边 } (i, s) \text{ 后图中不存在完美匹配}

理由很直接：若删掉后仍存在完美匹配，那它就是一条不含 $(i,s)$ 的完美匹配，与"每个都含"矛盾；反过来，若每个完美匹配都含 $(i,s)$ ，删掉它自然一个都不剩。

第二步：朴素枚举为什么不行，必须边检测为什么快。 暴力做法是枚举全部 $n!$ 个双射再统计， $n = 26$ 时 $26! \approx 4 \times 10^{26}$ ，完全不可行。但注意必须边有个关键性质：只有当前匹配里的边才可能是必须边。任取一个完美匹配 $M$ ，对 $M$ 之外的一条边 $(i, s)$ （ $i$ 在 $M$ 里配给了别的幻灯片 $s'$ ），把 $i$ 改配到 $s$ 、把原配给 $s$ 的编号还给 $s'$ 就得到一个不含 $(i,s)$ 的完美匹配——所以非匹配边永远"可被避开"。于是只需要检验 $n$ 条匹配边。

第三步：删掉一条匹配边后怎么判断还能不能完美匹配。 删掉匹配边 $(i, s)$ 后，原匹配里 $i$ 和 $s$ 都空了出来。整个图是否还有完美匹配，等价于：能否从编号 $i$ 出发，沿"非匹配边 → 匹配边 → 非匹配边 → …"交替前进（首条非匹配边不许直接走被删的 $(i,s)$ ），最后用一条非匹配边进入幻灯片 $s$ ，把路上所有匹配边换向。这条路径就是匈牙利算法里的交错路：

找得到：按交错路换边，得到避开 $(i,s)$ 的新完美匹配， $(i, s)$ 不是必须边；
找不到：每个完美匹配都必须含 $(i, s)$ ，它是必须边，登记配对。

下面是样例 1（ $n=4$ ）的二分图，实线是求出的匹配（同时都是必须边），虚线是会干扰判断的非匹配边：

digraph G {
  rankdir = LR;
  node [shape = circle, style = filled, fillcolor = lightblue];
  1 2 3 4;
  node [shape = box, style = filled, fillcolor = lightyellow];
  A B C D;

  1 -> A [label = " ", style = dashed];
  1 -> D [label = " ", penwidth = 2];
  2 -> B [label = " ", penwidth = 2];
  2 -> C [label = " ", style = dashed];
  2 -> D [label = " ", style = dashed];
  3 -> B [label = " ", style = dashed];
  3 -> C [label = " ", penwidth = 2];
  3 -> D [label = " ", style = dashed];
  4 -> B [label = " ", penwidth = 2];

  { rank = same; 1; 2; 3; 4; }
  { rank = same; A; B; C; D; }
}

以编号 1（实线配在 D）为例：删掉 $(1, D)$ 后，从 1 出发只有虚线边 $(1, A)$ 可走； $A$ 目前没有编号占用，无法沿匹配边换向，更走不回 $D$ ——交错路不存在， $(1, D)$ 是必须边，所以输出 (A,4)。再看一条虚线边为什么不用检验：比如 $(2, C)$ ，把 2 改配到 $C$ 、3 改配到 $B$ 就避开它了。

第四步：输出。 必须边两两不冲突： $(i,s)$ 与 $(j,s)$ 都是必须边会推出 $i = j$ （否则存在同时含两条的匹配，矛盾）， $(i,s)$ 与 $(i,t)$ 同理。所以按编号逐个判定后，得到的配对天然合法，按幻灯片字母序输出即可；一条必须边都没有时输出 none。注意题意是输出所有能唯一确定的幻灯片，部分幻灯片确定不了不影响其余的输出（这也是本题最容易误解的地方）。

代码

cpp

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 11:30
 * update_at: 2026-10-10 11:30
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct Rect { int x1, x2, y1, y2; };
Rect rects[30];
int match[30];              // 幻灯片 -> 当前占用它的编号
vector<int> adj[30];        // 编号 i 的邻接表（能落到的幻灯片）

bool augment(int i, bool seen[]) {
    for (size_t t = 0; t < adj[i].size(); t++) {
        int s = adj[i][t];
        if (seen[s]) continue;
        seen[s] = true;
        if (match[s] == -1 || augment(match[s], seen)) {
            match[s] = i;
            return true;
        }
    }
    return false;
}

// 删掉匹配边 (i, s) 后，编号 i 能否沿交错路绕回 s 重新落位
bool can_swap(int i, int s, int n) {
    bool seen[30] = {false};
    deque<int> q;
    for (size_t t = 0; t < adj[i].size(); t++) {
        int u = adj[i][t];
        if (u != s) { seen[u] = true; q.push_back(u); }
    }
    while (!q.empty()) {
        int t = q.front(); q.pop_front();
        int j = match[t];
        for (size_t t2 = 0; t2 < adj[j].size(); t2++) {
            if (adj[j][t2] == s) return true;
            int u = adj[j][t2];
            if (!seen[u]) { seen[u] = true; q.push_back(u); }
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int heap_no = 0;
    int n;
    while (cin >> n && n != 0) {
        heap_no++;
        for (int i = 0; i < n; i++)
            cin >> rects[i].x1 >> rects[i].x2 >> rects[i].y1 >> rects[i].y2;
        // 编号 i 的坐标
        for (int i = 0; i < n; i++) {
            int x, y;
            cin >> x >> y;
            adj[i].clear();
            for (int s = 0; s < n; s++) {
                if (rects[s].x1 <= x && x <= rects[s].x2 &&
                    rects[s].y1 <= y && y <= rects[s].y2)
                    adj[i].push_back(s);
            }
        }
        // 求一个完美匹配
        for (int s = 0; s < n; s++) match[s] = -1;
        for (int i = 0; i < n; i++) {
            bool seen[30] = {false};
            augment(i, seen);
        }

        int owner[30];
        for (int s = 0; s < n; s++) owner[s] = -1;
        bool perfect = true;
        for (int s = 0; s < n; s++)
            if (match[s] == -1) { perfect = false; break; }

        if (perfect) {
            // 编号 i 的当前匹配边是否必须
            int owner_by_num[30];
            for (int i = 0; i < n; i++) owner_by_num[i] = -1;
            for (int s = 0; s < n; s++) owner_by_num[match[s]] = s;
            for (int i = 0; i < n; i++) {
                int s = owner_by_num[i];
                if (!can_swap(i, s, n)) {
                    owner[s] = i;   // 必须边：幻灯片 s 被编号 i 唯一确定
                }
            }
        }

        vector<string> parts;
        for (int s = 0; s < n; s++) {
            if (owner[s] != -1) {
                string p = "(";
                p += (char)('A' + s);
                p += "," + to_string(owner[s] + 1) + ")";
                parts.push_back(p);
            }
        }
        cout << "Heap " << heap_no << "\n";
        if (parts.empty()) cout << "none\n";
        else {
            for (size_t i = 0; i < parts.size(); i++) {
                if (i) cout << " ";
                cout << parts[i];
            }
            cout << "\n";
        }
        cout << "\n";
    }
    return 0;
}

python

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 03:02
# update_at: 2026-10-02 03:02

import sys
from collections import deque

Rect = tuple[int, int, int, int]  # 一张幻灯片的边界 (x_min, x_max, y_min, y_max)


def slides_covering(rects: list[Rect], point: tuple[int, int]) -> list[int]:
    """返回包含该点的幻灯片下标：编号可能落在哪些幻灯片上（二分图中该编号的邻接表）。"""
    x, y = point
    return [i for i, (x1, x2, y1, y2) in enumerate(rects) if x1 <= x <= x2 and y1 <= y <= y2]


def augment(match: list[int], i: int, adj: list[list[int]], seen: list[bool]) -> bool:
    """匈牙利增广：编号 i 能否沿交错路找到一个空幻灯片，找到则更新 match。"""
    for t in adj[i]:
        if seen[t]:
            continue
        seen[t] = True
        if match[t] == -1 or augment(match, match[t], adj, seen):
            match[t] = i
            return True
    return False


def can_swap(i: int, s: int, adj: list[list[int]], match: list[int]) -> bool:
    """删掉匹配边 (i, s) 后，编号 i 能否沿交错路绕回 s 重新落位：能则 (i, s) 不是必须边。"""
    seen = [False] * len(adj)
    queue = deque(t for t in adj[i] if t != s)  # 第一步不许再走被删的边
    for t in queue:
        seen[t] = True
    while queue:
        t = queue.popleft()
        j = match[t]                # 占用 t 的编号，沿匹配边走到它
        if s in adj[j]:
            return True             # j 腾退到 s、i 顶替 t：交错环成立
        for u in adj[j]:
            if not seen[u]:
                seen[u] = True
                queue.append(u)
    return False


def must_owner(adj: list[list[int]]) -> list[int | None]:
    """返回 owner[s] = 幻灯片 s 被唯一确定的编号，无法确定记为 None。

    必须边 (i, s) 含义：删掉它后不存在完美匹配，于是它出现在每个完美匹配中，
    各编号的必须边天然互不冲突，可以逐个登记后按幻灯片输出。
    """
    n = len(adj)
    match = [-1] * n                   # 幻灯片 -> 当前占用它的编号
    for i in range(n):
        augment(match, i, adj, [False] * n)
    if -1 in match:                    # 完美匹配不存在，任何幻灯片都无法确定
        return [None] * n

    # 编号 i 只有当前匹配边可能成为必须边：其余边都被这份匹配本身避开
    must: list[int | None] = [None] * n
    for i in range(n):
        s = match.index(i)             # 编号 i 当前占用的幻灯片
        if not can_swap(i, s, adj, match):
            must[i] = s                # 删掉后无法重排：每个完美匹配都含这条边

    owner: list[int | None] = [None] * n
    for i, s in enumerate(must):
        if s is not None:
            owner[s] = i
    return owner


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []
    heap_no = 0

    while (n := next(data)) != 0:
        heap_no += 1
        rects: list[Rect] = []
        for _ in range(n):
            rects.append((next(data), next(data), next(data), next(data)))
        points = [(next(data), next(data)) for _ in range(n)]  # 编号 1..n 的坐标

        adj = [slides_covering(rects, p) for p in points]
        owner = must_owner(adj)
        # 只输出能唯一确定的幻灯片；一个都确定不了才输出 none
        parts = [f"({chr(65 + s)},{owner[s] + 1})" for s in range(n) if owner[s] is not None]
        out += [f"Heap {heap_no}", " ".join(parts) if parts else "none", ""]

    print("\n".join(out))


if __name__ == "__main__":
    solve()

复杂度

设 $n$ 为幻灯片数， $|E| \leqslant n^2$ 为二分图边数。

建图与匈牙利求完美匹配： $O(n \cdot |E|) = O(n^3)$ ；
必须边判定：对 $n$ 条匹配边各做一次 $O(|E|)$ 的交错路 BFS，合计 $O(n^3)$ 。

总复杂度 $O(n^3)$ ， $n \leqslant 26$ 时远低于时限（全部 11 组测试数据 Python 实测约 0.02s），与 C++ 正解同阶。

总结

合法分配 = 二分图完美匹配，“幻灯片编号唯一确定” = 配对边是必须边（出现在每个完美匹配中）。
必须边检测只需两步：先匈牙利求出一个完美匹配，再对每条匹配边删边跑一次交错路 BFS——能绕回则非必须，绕不回则必须。
两个易错点：① 非匹配边不可能是必须边，不必枚举全部 $n^2$ 条边；② 输出的是"所有能唯一确定的幻灯片"，部分确定时输出确定的部分，一个都确定不了才输出 none。

「Sorting Slide」 排版幻灯片

目录

形式化题目

正解

思路

代码

复杂度

总结

「Sorting Slide」排版幻灯片