烦人的幻灯片(slides)

题目描述

给定 $n$ 个按顺序编号为 $A,B,\dots$ 的矩形幻灯片，以及 $n$ 个按顺序编号为 $1,2,\dots$ 的数字点。点不会落在所有矩形之外。求数字与字母之间是否存在唯一的双射；若存在，按字母升序输出每对 字母数字，否则输出 None。

输入第一行为 $n$ ，接下来 $n$ 行每行四个整数 xmin xmax ymin ymax 表示幻灯片坐标，再接下来 $n$ 行每行两个整数 $x,y$ 表示数字点坐标。

思路

对每个数字点枚举所有矩形，得到它可能落入的幻灯片集合（含边界）。用位掩码存储候选集合， repeatedly 将候选集合只剩一个字母的数字确定下来，并把该字母从其它数字的候选中删去；若出现同一字母被两个数字抢占、或消元后仍有字母未确定，则输出 None。

参考代码

Python 版：

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#!/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-07-05 21:47
# update_at: 2026-07-05 21:47

import sys

# 候选表：letter[i] = 数字编号 i 可以放在哪些字母幻灯片里（位掩码，第 j 位 = 幻灯片 j）
# n ≤ 26，一个 int 装下所有候选，方便做拓扑消元时的位运算。


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)

    # 每张幻灯片（按输入顺序编号 A,B,...）的边界，每行 xmin xmax ymin ymax
    rect = [(next(data), next(data), next(data), next(data)) for _ in range(n)]

    # 数字编号 i 的候选字母集合：数字点落在哪些幻灯片矩形内部
    candidates: list[int] = []
    for _ in range(n):
        x = next(data)
        y = next(data)
        inside = [j for j in range(n)
                  if rect[j][0] <= x <= rect[j][1] and rect[j][2] <= y <= rect[j][3]]
        candidates.append(sum(1 << j for j in inside))  # 空集合 = 无解

    # 拓扑排序式消元：候选只有 1 个字母的数字先确定，把该字母从别人的候选里删掉
    match: list[int] = [-1] * n  # match[i] = 数字 i 对应的字母下标
    queue = [i for i in range(n) if candidates[i].bit_count() == 1]
    while queue:
        nxt: list[int] = []
        for i in queue:
            letter = candidates[i].bit_length() - 1   # 唯一剩下的字母
            if match[letter] != -1:                   # 同一字母被两个数字抢 → 无解
                print("None")
                return
            match[letter] = i
            bit = 1 << letter
            for k in range(n):                        # 从其他数字的候选中删掉该字母
                if k != i and candidates[k] & bit:
                    candidates[k] &= ~bit
                    if candidates[k].bit_count() == 1:
                        nxt.append(k)
        queue = nxt

    if any(m == -1 for m in match):                   # 有字母没被匹配 → 多解或无解
        print("None")
        return

    # match[letter] = 数字，按字母升序输出
    print("\n".join(f"{chr(ord('A') + j)} {match[j] + 1}" for j in range(n)))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * 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-05 12:44
 * update_at: 2026-10-05 12:44
 */

#include <cstdio>
#include <queue>

using namespace std;

typedef long long ll;

const int MAXN = 30;

ll xmin[MAXN], xmax[MAXN], ymin[MAXN], ymax[MAXN]; // 每张幻灯片（A,B,...）的边界
int candidates[MAXN]; // 每个数字点的候选字母集合，第 j 位为 1 表示字母 j 在候选中
int match_letter[MAXN]; // match_letter[j] = 占用字母 j 的数字编号（-1 表示未占用）

int main() {
    int n;
    scanf("%d", &n);

    // 读入 n 个矩形，按顺序对应字母 A,B,...
    for (int j = 0; j < n; j++) {
        scanf("%lld %lld %lld %lld", &xmin[j], &xmax[j], &ymin[j], &ymax[j]);
    }

    // 读入 n 个数字点，计算每个点落在哪些矩形内（含边界）
    for (int i = 0; i < n; i++) {
        ll x, y;
        scanf("%lld %lld", &x, &y);
        candidates[i] = 0;
        for (int j = 0; j < n; j++) {
            if (xmin[j] <= x && x <= xmax[j] && ymin[j] <= y && y <= ymax[j]) {
                candidates[i] |= (1 << j);
            }
        }
    }

    for (int j = 0; j < n; j++) {
        match_letter[j] = -1;
    }

    queue<int> q;
    // 初始候选唯一的数字入队
    for (int i = 0; i < n; i++) {
        int bits = candidates[i] & -candidates[i]; // 最低位的 1
        if (candidates[i] != 0 && (candidates[i] ^ bits) == 0) {
            q.push(i);
        }
    }

    while (!q.empty()) {
        int i = q.front();
        q.pop();

        // 取唯一候选字母
        int letter = 0;
        int tmp = candidates[i];
        while (tmp > 1) {
            tmp >>= 1;
            letter++;
        }

        if (match_letter[letter] != -1) {
            printf("None\n");
            return 0;
        }
        match_letter[letter] = i;

        int bit = (1 << letter);
        for (int k = 0; k < n; k++) {
            if (k == i) continue;
            if (candidates[k] & bit) {
                candidates[k] &= ~bit;
                // 删除后候选恰好为 1 个，入队
                int low = candidates[k] & -candidates[k];
                if (candidates[k] != 0 && (candidates[k] ^ low) == 0) {
                    q.push(k);
                }
            }
        }
    }

    // 仍有字母没被占用 → 多解或无解
    for (int j = 0; j < n; j++) {
        if (match_letter[j] == -1) {
            printf("None\n");
            return 0;
        }
    }

    // 按字母升序输出
    for (int j = 0; j < n; j++) {
        printf("%c %d\n", 'A' + j, match_letter[j] + 1);
    }

    return 0;
}

烦人的幻灯片(slides)

目录

题目描述

思路

参考代码