字母游戏 - 题目列表

形式化题目

给定一个字母多重集 $C$ （用 26 维计数向量 $c_a,\dots,c_z$ 表示， $3 \leqslant |C| \leqslant 7$ ）、一张分值表 $value(\cdot)$ ，以及一个按字典序升序排列、最多含 $40000$ 个互不相同单词的字典 $D$ （每个单词长度在 $3$ 到 $7$ 之间）。

每个单词 $w$ 有自己的计数向量 $u(w)$ 与分值

s(w) = \sum_{ch \in w} value(ch).

求所有满足 $u(w_1) + u(w_2) \leqslant C$ （逐分量比较）的单词或词对 $(w_1, w_2)$ 中， $s(w_1) + s(w_2)$ 的最大值，并输出所有取到该最大值的方案。

正解

思路

先看清答案的形状。 单词长度至少是 $3$ ，而卡片最多 $7$ 个字母：三个单词至少要 $3 + 3 + 3 = 9$ 个字母，卡片根本不够。所以词组里最多只能有两个单词，答案只可能是单字或词对。这一点让枚举空间天然封闭。

朴素做法错在哪。 直接双重循环枚举字典里的每一对单词： $N \leqslant 40000$ 时组合数是 $1.6\times10^9$ 量级，每组还要比 26 个字母，必然超时。瓶颈不在"检查是否合法"，而在组合数——而绝大多数单词根本不可能被拼出来，因为它们含有卡片里没有的字母。

第一步：用位掩码粗筛。 把卡片和单词都压成一个 26 位整数，第 $i$ 位表示字母 'a' + i 是否出现：

\text{mask}(s) = \bigvee_{ch \in s} 2^{\,ord(ch)-97}.

于是"单词含有卡片外的字母"这件事，等价于一次按位与非的结果不为零：

python

1kept = [w for w in words if (letter_mask(w) & ~cards_mask) == 0]

$O(N)$ 扫一遍，每个单词 $O(1)$ 判断，绝大部分单词在这一步就被扔掉。

第二步：掩码抓不住重复字母，必须再比计数。 卡片是 abc（各 1 个）时，单词 abb 需要的 2 个 b 掩码看不出来，会被放行。因此粗筛只能当作快速过滤器，幸存者还要逐字母比 26 维用量向量：

python

1playing = [item for item in playing if all(x <= y for x, y in zip(item[2], card_usage))]

注意卡片本身可以有重复字母（例如 jicuzza 有 2 个 z、2 个 a），所以用量向量必须按实际重复次数建立，不能退化成集合。

第三步：单字基线 + 词对枚举。 先把候选里的最大单词分值当作当前最高分 best，这样词对枚举一开始就有门槛可以剪枝。然后在候选表上做两两枚举，内层下标从外层的 $i$ 开始：

python

1
2
3
4
5
6
7
8
9for i, (word_a, score_a, usage_a) in enumerate(playing):
    for word_b, score_b, usage_b in playing[i:]:
        if score_a + score_b < best:      # 追不平当前最高分
            continue
        if any(x + y > z for x, y, z in zip(usage_a, usage_b, card_usage)):
            continue                      # 卡片不够拼这一对
        if score_a + score_b > best:      # 刷新纪录：清空旧答案
            best, winners = score_a + score_b, []
        winners.append(f"{word_a} {word_b}")

内层从 $i$ （而不是 $i+1$ ）开始有两个作用：允许同一个单词在词对里出现两次（与官方"在剩余卡片上枚举第二个词"的语义一致），同时因为输出时统一取字典序较小的单词在前，rag prom 与 prom rag 只会以一种形式出现一次，天然满足"不许重复表示字对"。只有在分值严格大于 best 时才清空答案，相等时追加，这样并列方案不会被覆盖。

整体流程：

flowchart TD
    A[读入卡片 + 字典] --> B[算卡片掩码与用量向量]
    B --> C[粗筛: mask w 与 cards 掩码无交集]
    C --> D[精筛: 逐字母比用量向量]
    D --> E[单字基线 best = max 单词分值]
    E --> F[枚举词对 i <= j]
    F --> G{分值小于 best?}
    G -- 是, 剪枝 --> F
    G -- 否 --> H{用量超出卡片?}
    H -- 是 --> F
    H -- 否 --> I{分值大于 best?}
    I -- 是 --> J[清空答案并更新 best]
    I -- 否 --> K[追加并列答案]
    J --> F
    K --> F
    F --> L[输出 best 与排序后的答案]

图里有两条剪枝边（分值不够、用量不够）和两条更新边（刷新纪录、追加并列），它们合起来保证枚举结束时 best 与 winners 正好是全部最优方案。

样例推演。 题面样例中卡片为 prmgroa，小字典只有 6 个词。先看掩码粗筛：profile 含有卡片里没有的 i、e、f、l，直接淘汰；其余 5 个词的字母都在卡片里。再看计数：卡片里 r、o、a、p 各 1 个、m 1 个，program 用掉 p r o g r a m 共 7 个字母，用量恰好落在卡片容量内。

单词	分值	卡片够用	说明
`profile`	21	否	含卡片外的 `i`、`e`、`f`、`l`，掩码粗筛淘汰
`program`	24	是	单字最优，`best` 先取 24
`prom`	15	是	单独 15，需配词
`rag`	9	是	单独 9
`ram`	9	是	单独 9
`rom`	10	是	单独 10

best = 24 来自 program。接着枚举词对，只有 prom（15）与 rag（9）相加为 24，用掉的卡片是 p r o m + r a g，r 恰好用满 1 个，其余也都不超；prom 与 ram 的 r 会冲突（需要 2 个 r），prom 与 rom 的 r、o 都冲突。所以与 24 并列的只有 prom rag 一条，输出：

text

1
2
324
program
prom rag

这也解释了为什么题面样例输出里两个答案一个来自单字、一个来自词对——它们分值相同，必须同时输出。

代码

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75#!/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-01 06:48
# update_at: 2026-10-01 06:48

import sys
from pathlib import Path

# 图上给出的字母分值，下标 = ord(字母) - ord('a')
SCORE = (2, 5, 4, 4, 1, 6, 5, 5, 1, 7, 6, 3, 5, 2, 3, 5, 7, 2, 1, 2, 4, 6, 6, 7, 5, 7)

DICT_NAME = "lgame.dict"  # 题面规定的字典文件


def letter_mask(word: str) -> int:
    """单词里出现过哪些字母：第 i 位为 1 表示 chr(ord('a') + i) 出现过。"""
    return sum(1 << (ord(ch) - 97) for ch in set(word))


def usage_vector(word: str) -> tuple[int, ...]:
    """单词在 26 个字母上各用了几个，用来精确判断手上的卡片够不够拼。"""
    counts = [0] * 26
    for ch in word:
        counts[ord(ch) - 97] += 1
    return tuple(counts)


def word_score(word: str) -> int:
    """单词得分 = 每个字母分值之和。"""
    return sum(SCORE[ord(ch) - 97] for ch in word)


def solve() -> None:
    # 卡片是第 1 个 token；字典长度不固定，以 "." 结束，只能用迭代器顺序消费到终止点。
    data = iter(sys.stdin.read().split())
    cards = next(data)                 # 第 1 个 token：手上的卡片
    words: list[str] = []
    for token in data:                 # 第 2..stop-1 个 token：字典单词
        if token == ".":
            break
        words.append(token)

    if not words:                      # 只给了卡片，字典按题面从 lgame.dict 读
        candidates = (Path(__file__).with_name(DICT_NAME), Path(DICT_NAME))
        words = next(p for p in candidates if p.is_file()).read_text().split()

    cards_mask, card_usage = letter_mask(cards), usage_vector(cards)

    # 用位与整批淘汰含卡片外字母的单词：掩码挡住字母种类，挡不住重复个数
    kept = [w for w in words if (letter_mask(w) & ~cards_mask) == 0]
    # 剩下的少量候选再逐字母比用量，抓出"卡片只有 1 个 a、单词却要 2 个 a"这类
    playing = [(w, word_score(w), usage_vector(w)) for w in kept]
    playing = [item for item in playing if all(x <= y for x, y in zip(item[2], card_usage))]

    best = max((score for _, score, _ in playing), default=0)
    winners = [word for word, score, _ in playing if score == best]

    # 词对枚举下标 i <= j：小者在前，同一对不会换个顺序再出现一次
    for i, (word_a, score_a, usage_a) in enumerate(playing):
        for word_b, score_b, usage_b in playing[i:]:
            if score_a + score_b < best:  # 追不平当前最高分，不必再算用量
                continue
            if any(x + y > z for x, y, z in zip(usage_a, usage_b, card_usage)):
                continue
            if score_a + score_b > best:
                best, winners = score_a + score_b, []
            winners.append(f"{word_a} {word_b}")

    sys.stdout.write("\n".join([str(best), *sorted(winners)]) + "\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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156/**
 * 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-06 11:20
 * update_at: 2026-10-06 11:21
 */
// main.cpp：roj 2072 字母游戏。
// 先用 26 位掩码淘汰含卡片外字母的单词，再用 26 维用量向量精筛，
// 最后在少量候选上枚举单字与词对，取最高分并输出全部并列方案。
#include <algorithm>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

typedef long long ll;

const int MAXW = 40005;

// 字母分值表，下标 = 字母 - 'a'
const int SCORE[26] = {2, 5, 4, 4, 1, 6, 5, 5, 1, 7, 6, 3, 5, 2, 3, 5, 7, 2, 1, 2, 4, 6, 6, 7, 5, 7};

struct Item {
    string word;
    ll score;
    int usage[26]; // 该单词在 26 个字母上各用了几个
};

string cards;       // 手上的卡片串
string words[MAXW]; // 读入的字典单词
int word_cnt;

Item playing[MAXW]; // 通过粗筛与精筛的候选单词
int playing_cnt;

int card_usage[26]; // 卡片的 26 维用量
int card_mask;      // 卡片出现过的字母位掩码

// 单词里出现过哪些字母：第 i 位为 1 表示字母 'a' + i 出现过。
int word_mask(const string &w) {
    int m = 0;
    for (ll i = 0; i < (ll)w.size(); i++) {
        m |= (1 << (w[i] - 'a'));
    }
    return m;
}

// 单词得分 = 每个字母分值之和。
ll word_score(const string &w) {
    ll s = 0;
    for (ll i = 0; i < (ll)w.size(); i++) {
        s += SCORE[w[i] - 'a'];
    }
    return s;
}

// 统计卡片的字母掩码与 26 维用量（卡片可能有重复字母）。
void build_card() {
    for (ll i = 0; i < (ll)cards.size(); i++) {
        int idx = cards[i] - 'a';
        card_usage[idx]++;
        card_mask |= (1 << idx);
    }
}

void read_input() {
    // 标准输入第一段是卡片串，之后是字典单词，以 "." 结束；
    // 若只给了卡片，则按题面去读同目录的 lgame.dict。
    if (!(cin >> cards)) return;
    string w;
    while (cin >> w) {
        if (w == ".") break;
        words[++word_cnt] = w;
    }
    if (word_cnt == 0) {
        ifstream fin("lgame.dict");
        while (fin >> w) {
            if (w == ".") break;
            words[++word_cnt] = w;
        }
    }
}

void solve() {
    build_card();

    for (int i = 1; i <= word_cnt; i++) {
        string w = words[i];
        if (word_mask(w) & ~card_mask) continue; // 含卡片外的字母，直接淘汰

        Item cur;
        cur.word = w;
        cur.score = word_score(w);
        for (int t = 0; t < 26; t++) cur.usage[t] = 0;
        for (ll j = 0; j < (ll)w.size(); j++) cur.usage[w[j] - 'a']++;

        bool enough = true; // 精筛：逐个字母比较卡片用量，掩码挡不住重复字母
        for (int t = 0; t < 26; t++) {
            if (cur.usage[t] > card_usage[t]) {
                enough = false;
                break;
            }
        }
        if (enough) playing[++playing_cnt] = cur;
    }

    ll best = 0; // 先取单字基线
    for (int i = 1; i <= playing_cnt; i++) {
        if (playing[i].score > best) best = playing[i].score;
    }
    vector<string> winners;
    for (int i = 1; i <= playing_cnt; i++) {
        if (playing[i].score == best) winners.push_back(playing[i].word);
    }

    // 词对枚举：下标 i <= j，同一单词可重复使用，也避免同一对换序重复
    for (int i = 1; i <= playing_cnt; i++) {
        for (int j = i; j <= playing_cnt; j++) {
            ll sum = playing[i].score + playing[j].score;
            if (sum < best) continue; // 追不平当前最高分，不必再比用量

            bool enough = true;
            for (int t = 0; t < 26; t++) {
                if (playing[i].usage[t] + playing[j].usage[t] > card_usage[t]) {
                    enough = false;
                    break;
                }
            }
            if (!enough) continue;

            if (sum > best) { // 刷新纪录：清空旧答案
                best = sum;
                winners.clear();
            }
            winners.push_back(playing[i].word + " " + playing[j].word);
        }
    }

    sort(winners.begin(), winners.end());
    cout << best << "\n";
    for (ll i = 0; i < (ll)winners.size(); i++) {
        cout << winners[i] << "\n";
    }
}

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

    read_input();
    solve();

    return 0;
}

复杂度

设字典规模为 $N$ ，精筛后的候选数为 $k$ 。

粗筛： $O(N \cdot L)$ ， $L \leqslant 7$ 为单词长度；
精筛： $O(k \cdot 26)$ ；
枚举词对： $O(k^2 \cdot 26)$ 。

总计 $O(NL + 26k^2)$ ，与标准 C++ 解法同阶。 $k$ 被"单词长度 $\geqslant 3$ 、卡片 $\leqslant 7$ "压缩得很小：真实数据中最大为 $44$ （卡片 abcdefg），随机采样 3 万组 7 字母卡片最大也只有 $172$ ，所以 $k^2$ 完全在可接受范围内。空间 $O(NL + k)$ ，实测峰值约 $18\,\text{MB}$ 。

真实数据验证： $12$ 组测例全部通过，最慢约 $0.04\,\text{s}$ ，无 TLE/MLE 风险。

总结

先定形状再选算法：单词长度 $\geqslant 3$ 、卡片 $\leqslant 7$ 直接推出"最多两个字"，答案空间随即封闭。
瓶颈在组合数，不在判定： $O(N^2)$ 不可行，但绝大多数单词压根拼不出来；先用 26 位掩码做 $O(1)$ 粗筛，把 $N$ 压到几十。
掩码 ≠ 计数：位掩码只管字母种类，重复字母必须靠 26 维用量向量精筛，否则卡片 abc 会误收 abb。
枚举顺序即去重规则：内层从 $i$ 开始、输出时小者在前，a b 与 b a 自然只出现一次；只有严格更大才清空答案，并列方案不丢。