稗田阿求

GitHub跳转原题关系图返回列表

把每组文字段与数列看成字母到数字的部分单射,两组相容就连边,答案化为 40 点相容图上的最大团,用位掩码加分支限界求解。

OJ: roj

题目 ID: 1683

难度:提高+/省选-

标签:图论位运算搜索剪枝python

创建: 2026-10-07 15:17

更新: 2026-10-07 15:17

形式化题目

有 NN 个数字 1,2,…,N1, 2, \dots, N 和 NN 个字母(第 11 到第 NN 个大写字母),二者之间要建立 一个双射 φ\varphi:每个字母配一个数字,每个数字恰好被一个字母用掉。

给定 MM 组数据,第 ii 组是一对「文字段 SiS_i、数列 AiA_i」,长度都是 LiL_i,并且组内合法:

  • 同一个字母在 SiS_i 中出现多次时,对应位置的数字都相同;
  • 不同字母对应位置的数字互不相同。

第 ii 组被满足,当且仅当在双射 φ\varphi 下

φ(Si[j])=Ai[j](1⩽j⩽Li),\varphi(S_i[j]) = A_i[j] \qquad (1 \leqslant j \leqslant L_i),

即文字段的第 jj 个字母恰好配到数列的第 jj 项。求最多能同时被满足的组数。

1⩽N⩽261 \leqslant N \leqslant 26,1⩽M⩽401 \leqslant M \leqslant 40,1⩽Li⩽1001 \leqslant L_i \leqslant 100。

正解

思路

第一步:一组数据 = 一个部分单射。 组内合法意味着第 ii 组只做了一件事: 把 SiS_i 里出现过的字母各指定一个数字。这是一个部分单射

fi:{ Si 中出现的字母 }→{1,…,N},f_i : \{\,S_i \text{ 中出现的字母}\,\} \to \{1, \dots, N\},

没出现过的字母在 fif_i 里没有定义。于是"第 ii 组被满足"就是"φ\varphi 在 fif_i 的定义域上等于 fif_i"。

第二步:一堆组能同时满足,等价于它们的并还是单射。 记 f=⋃i∈Tfif = \bigcup_{i \in T} f_i。 若存在双射 φ⊇f\varphi \supseteq f,则 ff 必须是单射(既是函数、又是单射); 反过来只要 ff 是单射,把剩下的 N−∣f∣N - |f| 个字母与剩下的 N−∣f∣N - |f| 个数字随便配对, 就补成了一个双射。所以

T 能被同时满足  ⟺  f=⋃i∈Tfi 是一个部分单射.T \text{ 能被同时满足} \iff f = \bigcup_{i \in T} f_i \text{ 是一个部分单射}.

第三步:冲突一定在某一对上暴露。 合并后 ff 不是单射,只可能是两种情形:

  1. 某个字母被指定了两个不同的数字 —— 这两个来源分属两组 i,ji, j(若同属一组,则该组自己就不合法), 于是 fi∪fjf_i \cup f_j 已经不是单射;
  2. 两个不同字母被指定了同一个数字 —— 同理,fi∪fjf_i \cup f_j 已经不是单射。

因此 “任意两组都相容” 就推出 “全体相容”:集合 TT 合法当且仅当 TT 中任意一对都合法。

第四步:建图,答案就是最大团。 以 MM 组为点,ii 与 jj 之间连边当且仅当 fi∪fjf_i \cup f_j 是单射。由第三步,TT 合法   ⟺  \iff TT 是这张图里的团。所以答案等于 相容图的最大团大小。判断两条边只需逐字母扫一遍:

  • 公共字母上两组的数字必须相同;
  • 合并后「用到的不同数字个数」必须等于「用到的不同字母个数」 (映射是单射   ⟺  \iff 值域大小 = 定义域大小)。

第五步:M⩽40M \leqslant 40 的最大团。 最大团是 NP 难问题,但 M⩽40M \leqslant 40, 一个 unsigned long long / Python 大整数就能表示"还能选哪些组",直接搜索:

  • 按编号从小到大决定每一组"选 / 不选";
  • 用掩码 candidates 记录"与已选集合全部相容、还有资格被选的组"; 选第 ii 组时把 candidates 与第 ii 组的相容掩码取交;
  • 剪枝:若 已选数 + 剩余组数 <= 当前最优,后面的组全选也追不平,直接返回。

本题的 40 组数据里有大团结构(第 9 个点是 40 组完全相容,第 10 个点是 39 组完全相容 + 1 组捣乱), 但"先一路选到底"的顺序会立刻拿到最优解,剪枝随即把其余分支全部砍掉,所以实际搜索量很小。

样例推演。 题面样例的三组数据给出的部分单射是

组 文字段 / 数列 定义域与取值
1 ACCA / 1 3 3 1 A→1A \to 1,C→3C \to 3
2 AAC / 2 2 1 A→2A \to 2,C→1C \to 1
3 BCBC / 3 1 3 1 B→3B \to 3,C→1C \to 1

逐对检查:

组对 公共字母 合并后的字母 / 数字 相容?
1, 2 AA:1≠21 \neq 2 — 否(AA 被指定了两个数字)
1, 3 CC:3≠13 \neq 1 — 否(CC 被指定了两个数字)
2, 3 CC:1=11 = 1 {A,C,B}\{A,C,B\} / {2,1,3}\{2,1,3\},个数相同 是

相容图只有 2 ⁣− ⁣32\!-\!3 一条边,最大团大小为 22,与样例输出一致; 取 A=2,B=3,C=1A=2, B=3, C=1 时第 2、3 组被满足,正是题目提示里的那组对应关系。

代码

Python 版(最大团用 functools.cache 记忆化:候选集里取编号最小的组,选 / 不选两支取最大值):

python
#!/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-07 15:17
# update_at: 2026-10-07 15:17

import sys
from functools import cache

# 类型别名(Python 3.12+ 的 type 语句),相当于 C++ 的 using / typedef
type Group = dict[str, int]  # 一组的 字母 -> 数字 部分映射(题面保证组内是一一对应)
type Masks = list[int]       # 相容掩码:masks[i] 的第 j 位为 1 ⟺ 第 i 组与第 j 组能同时成立


def compatible(first: Group, second: Group) -> bool:
    """两组能否同时成立:公共字母取值一致,且合并后不同字母不共用数字。"""
    shared = first.keys() & second.keys()
    if any(first[ch] != second[ch] for ch in shared):
        return False
    # 合并后的映射是单射 ⟺ 用到的不同数字个数 == 用到的不同字母个数
    return len(set(first.values()) | set(second.values())) == len(first) + len(second) - len(shared)


def build_masks(groups: list[Group]) -> Masks:
    """算出所有两两相容关系,返回对称的相容掩码表。"""
    masks = [0] * len(groups)
    for i in range(len(groups)):
        for j in range(i + 1, len(groups)):
            if compatible(groups[i], groups[j]):
                masks[i] |= 1 << j  # 关系对称,两边都要登记
                masks[j] |= 1 << i
    return masks


def max_clique_size(masks: Masks) -> int:
    """相容图上的最大团大小:候选集只存"还能选哪些组",按编号从小到大做选/不选 DP。"""

    @cache
    def best(cand: int) -> int:
        """cand 里最多能同时选多少组(选出的组必须两两相容)。"""
        if not cand:
            return 0  # 没有候选组了,这一支只能贡献 0
        bit = cand & -cand
        index = bit.bit_length() - 1  # 最低位对应的组编号
        rest = cand ^ bit             # 不选它:剩下的组编号都大于 index
        keep = rest & masks[index]    # 选它:剩下的只能从它的相容集合里挑
        return max(best(rest), 1 + best(keep))

    return best((1 << len(masks)) - 1)


def solve() -> None:
    tokens = iter(sys.stdin.buffer.read().split())
    n = int(next(tokens))  # N:数字与字母的个数,只限定值域,算法本身用不到
    m = int(next(tokens))  # M:组的个数

    groups: list[Group] = []
    for _ in range(m):
        word = next(tokens).decode()  # 本组的文字段
        length = len(word)            # 数列的数字个数,题面保证等于字符数
        numbers = [int(next(tokens)) for _ in range(length)]
        groups.append(dict(zip(word, numbers)))

    print(max_clique_size(build_masks(groups)))


if __name__ == "__main__":
    solve()

C++ 版(同一算法,最大团用位掩码 + 分支限界 DFS,与 std 等价):

cpp
/**
 * 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-07 15:17
 * update_at: 2026-10-07 15:17
 */
// main.cpp:稗田阿求。
// 每一组"文字段 + 数列"给出一个 字母->数字 的部分单射(题面保证组内合法),
// 两组能同时成立就连一条边,答案就是这张相容图上的最大团。
// M <= 40,用 64 位掩码表示"还能选哪些组",再做分支限界 DFS。与 main.py 同一算法。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXM = 45;   // 组数上限 40,留一点余量
const int ALPHA = 26;  // 字母表大小,A..Z

// 一组数据:既存它给出的部分单射,也存它在相容图上的邻接掩码
struct Group {
    ll value[ALPHA];           // value[c]:本组里字母 c 对应的数字,0 表示该字母没出现
    unsigned long long compat; // 第 j 位为 1 <=> 本组与第 j 组能同时成立(不含自己)
};

ll n, m;             // n:数字与字母的个数(只限定值域,算法本身不需要);m:组的个数
Group group[MAXM];   // group[i] 就是第 i 组,下标从 1 开始和题面一致
ll best_answer;      // 目前搜到的最大团大小

// 两组能否同时成立:公共字母必须对应同一个数字,且合并后不同字母不共用数字。
bool compatible(ll a, ll b) {
    bool used_number[ALPHA + 1] = {false}; // used_number[v]:数字 v 已被合并后的某个字母占用
    for (int c = 0; c < ALPHA; c++) {
        ll va = group[a].value[c];
        ll vb = group[b].value[c];
        if (va != 0 && vb != 0 && va != vb) return false; // 同一个字母被赋了两个数字
        ll v = va != 0 ? va : vb;
        if (v == 0) continue;              // 两组都没出现这个字母
        if (used_number[v]) return false;  // 两个不同字母挤到了同一个数字上
        used_number[v] = true;
    }
    return true;
}

// 分支限界求最大团:决定第 idx 组选不选,cnt 是已经选了几组,
// candidates 中为 1 的位是"与已选集合全部相容、还能继续选"的那些组。
void dfs(ll idx, ll cnt, unsigned long long candidates) {
    if (cnt + (m - idx + 1) <= best_answer) return; // 剩下的组全选也追不平,直接剪掉
    if (idx > m) {
        best_answer = max(best_answer, cnt);
        return;
    }
    if ((candidates >> (idx - 1)) & 1ULL) {
        dfs(idx + 1, cnt + 1, candidates & group[idx].compat); // 选第 idx 组,候选集同步收窄
    }
    dfs(idx + 1, cnt, candidates); // 不选第 idx 组
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        string word;
        cin >> word;              // 第 i 组的文字段
        ll length = word.size();  // 数列长度,题面保证等于文字段的字符数
        for (ll j = 0; j < length; j++) {
            ll value;
            cin >> value;
            group[i].value[word[j] - 'A'] = value; // 组内合法,同一字母重复出现时数字相同
        }
    }

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= m; j++) {
            if (i != j && compatible(i, j)) group[i].compat |= 1ULL << (j - 1);
        }
    }

    dfs(1, 0, ~0ULL); // 一开始所有组都在候选集里
    cout << best_answer << "\n";

    return 0;
}

复杂度

设 MM 为组数,α=26\alpha = 26 为字母表大小。

  • 建图:每组读入 O(Li+α)O(L_i + \alpha),两两判断相容 O(M2α)O(M^2 \alpha),即 O(M2α+∑Li)O(M^2 \alpha + \sum L_i)。
  • 最大团:最坏 O(2M)O(2^M),是本题唯一的指数部分;M⩽40M \leqslant 40 时靠"上界剪枝"退化到可接受范围。 实测官方 10 个点的搜索节点数最多为 1.2×1051.2 \times 10^5(第 7 个点),第 9、10 个点的完全团结构只有 8181、8080 个节点。
  • 实测:C++ 版 10 个点全部在 9 ms9\ \text{ms} 内跑完、峰值内存 8.4 MB8.4\ \text{MB} (限时 1000 ms1000\ \text{ms}、64 MB64\ \text{MB});Python 版每点约 0.02 s0.02\ \text{s}, @cache 的状态数最多只有 7979 个(记忆化把"同一候选集"的重复计算全部合并了)。
  • 空间:C++ 版除输入外只需 O(M)O(M) 的掩码与 O(M)O(M) 的递归栈;Python 版额外存记忆化表, 状态数是实际搜索到的不同候选集个数,本题量级在 10210^2 以内。

总结

  • 把"一组数据"读成一个部分单射,题目就从"安排一个双射"变成了"挑一些单射拼起来", 不再需要关心具体是哪个双射。
  • 两两相容 ⇒\Rightarrow 全体相容是本题的关键一步:任何冲突都只涉及两组, 于是"选哪些组"变成图上的团,答案就是最大团。没有这条观察就只能对 N!N! 个双射暴力枚举。
  • 补全为双射不需要额外条件:只要合并后是单射,剩余字母数与剩余数字数就必然相等, 随便配对即可。这也是题目里 NN 只用来限定值域、算法根本用不到它的原因。
  • M⩽40M \leqslant 40 让最大团可以硬搜:一个 64 位掩码存候选集,配一条 已选数 + 剩余组数 <= 最优 的上界剪枝;数据里的"完全相容"结构恰好让最优解在第一条路径上就被找到, 剪枝随即生效。Python 版用 @cache 记忆化候选集,把重复状态合并掉,同样很快。

图示解析

把整个推导串成一条流水线:每组数据压缩成一个部分单射,两两判断相容建成图,答案落在最大团上。

flowchart TD
  G["M 组 (文字段, 数列)"] --> P["每组 = 一个部分单射 f_i"]
  P --> E["两两判断 f_i ∪ f_j 是否仍是单射"]
  E --> H["相容图:相容就连边"]
  H --> C["答案 = 最大团大小"]
  C --> S["位掩码候选集 + 上界剪枝搜索"]

左边三步是建模,右边两步是实现。读图时注意两点:判断边的条件是"公共字母取值相同" 且"合并后数字个数 = 字母个数"这两条同时成立;而最大团搜索里,candidates 掩码始终表示 “和已经选定的组全部相容、还有资格入选的组”,一旦某组与已选集合冲突,它就从候选集里消失, 不会再被回溯到。