把每组文字段与数列看成字母到数字的部分单射,两组相容就连边,答案化为 40 点相容图上的最大团,用位掩码加分支限界求解。
OJ: roj
题目 ID: 1683
难度:提高+/省选-
标签:图论位运算搜索剪枝python
创建: 2026-10-07 15:17
更新: 2026-10-07 15:17
形式化题目
有
给定
- 同一个字母在
中出现多次时,对应位置的数字都相同; - 不同字母对应位置的数字互不相同。
第
即文字段的第
正解
思路
第一步:一组数据 = 一个部分单射。 组内合法意味着第
没出现过的字母在
第二步:一堆组能同时满足,等价于它们的并还是单射。 记
第三步:冲突一定在某一对上暴露。 合并后
- 某个字母被指定了两个不同的数字 —— 这两个来源分属两组
(若同属一组,则该组自己就不合法), 于是 已经不是单射; - 两个不同字母被指定了同一个数字 —— 同理,
已经不是单射。
因此 “任意两组都相容” 就推出 “全体相容”:集合
第四步:建图,答案就是最大团。 以
- 公共字母上两组的数字必须相同;
- 合并后「用到的不同数字个数」必须等于「用到的不同字母个数」
(映射是单射
值域大小 = 定义域大小)。
第五步:unsigned long long / Python 大整数就能表示"还能选哪些组",直接搜索:
- 按编号从小到大决定每一组"选 / 不选";
- 用掩码
candidates记录"与已选集合全部相容、还有资格被选的组"; 选第组时把 candidates与第组的相容掩码取交; - 剪枝:若
已选数 + 剩余组数 <= 当前最优,后面的组全选也追不平,直接返回。
本题的 40 组数据里有大团结构(第 9 个点是 40 组完全相容,第 10 个点是 39 组完全相容 + 1 组捣乱), 但"先一路选到底"的顺序会立刻拿到最优解,剪枝随即把其余分支全部砍掉,所以实际搜索量很小。
样例推演。 题面样例的三组数据给出的部分单射是
| 组 | 文字段 / 数列 | 定义域与取值 |
|---|---|---|
| 1 | ACCA / 1 3 3 1 |
|
| 2 | AAC / 2 2 1 |
|
| 3 | BCBC / 3 1 3 1 |
逐对检查:
| 组对 | 公共字母 | 合并后的字母 / 数字 | 相容? |
|---|---|---|---|
| 1, 2 | — | 否( |
|
| 1, 3 | — | 否( |
|
| 2, 3 | 是 |
相容图只有
代码
Python 版(最大团用 functools.cache 记忆化:候选集里取编号最小的组,选 / 不选两支取最大值):
#!/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 等价):
/**
* 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;
}复杂度
设
- 建图:每组读入
,两两判断相容 ,即 。 - 最大团:最坏
,是本题唯一的指数部分; 时靠"上界剪枝"退化到可接受范围。 实测官方 10 个点的搜索节点数最多为 (第 7 个点),第 9、10 个点的完全团结构只有 、 个节点。 - 实测:C++ 版 10 个点全部在
内跑完、峰值内存 (限时 、 );Python 版每点约 , @cache的状态数最多只有个(记忆化把"同一候选集"的重复计算全部合并了)。 - 空间:C++ 版除输入外只需
的掩码与 的递归栈;Python 版额外存记忆化表, 状态数是实际搜索到的不同候选集个数,本题量级在 以内。
总结
- 把"一组数据"读成一个部分单射,题目就从"安排一个双射"变成了"挑一些单射拼起来", 不再需要关心具体是哪个双射。
- 两两相容
全体相容是本题的关键一步:任何冲突都只涉及两组, 于是"选哪些组"变成图上的团,答案就是最大团。没有这条观察就只能对 个双射暴力枚举。 - 补全为双射不需要额外条件:只要合并后是单射,剩余字母数与剩余数字数就必然相等,
随便配对即可。这也是题目里
只用来限定值域、算法根本用不到它的原因。 让最大团可以硬搜:一个 64 位掩码存候选集,配一条 已选数 + 剩余组数 <= 最优的上界剪枝;数据里的"完全相容"结构恰好让最优解在第一条路径上就被找到, 剪枝随即生效。Python 版用@cache记忆化候选集,把重复状态合并掉,同样很快。
图示解析
把整个推导串成一条流水线:每组数据压缩成一个部分单射,两两判断相容建成图,答案落在最大团上。
flowchart TD G["M 组 (文字段, 数列)"] --> P["每组 = 一个部分单射 f_i"] P --> E["两两判断 f_i ∪ f_j 是否仍是单射"] E --> H["相容图:相容就连边"] H --> C["答案 = 最大团大小"] C --> S["位掩码候选集 + 上界剪枝搜索"]
左边三步是建模,右边两步是实现。读图时注意两点:判断边的条件是"公共字母取值相同"
且"合并后数字个数 = 字母个数"这两条同时成立;而最大团搜索里,candidates 掩码始终表示
“和已经选定的组全部相容、还有资格入选的组”,一旦某组与已选集合冲突,它就从候选集里消失,
不会再被回溯到。