打卡信奥刷题（3671）用C++实现信奥题 P12238 [蓝桥杯 2023 国 Java A] 单词分类

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */
#content_views .toc,
/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */
#content_views.markdown_views > p:empty:has(+ .toc),
#content_views.markdown_views > .toc + p:empty,
/* 富文本旧版目录标记 */
#content_views.htmledit_views #main-toc,
#content_views.htmledit_views #hr-toc,
#content_views.htmledit_views p[id*=\”-toc\”] {
display: none !important;
}
/* 目录去掉后，紧跟的首个标题不再多出一块上边距 */
#content_views.markdown_views > .toc + h1,
#content_views.markdown_views > .toc + h2,
#content_views.markdown_views > .toc + h3,
#content_views.markdown_views > .toc + h4,
#content_views.markdown_views > .toc + p:empty + h1,
#content_views.markdown_views > .toc + p:empty + h2,
#content_views.markdown_views > .toc + p:empty + h3,
#content_views.markdown_views > .toc + p:empty + h4 {
margin-top: 0 !important;
}

P12238 [蓝桥杯 2023 国 Java A] 单词分类

题目描述

在遥远的 LQ 国，只存在三种字符：$\mathtt{l}$、$\mathtt{q}$ 和 $\mathtt{b}$（ASCII 码分别为 $108$、$113$、$98$），所有的单词都由这三种字符组合而来。小蓝为了更加快速的记忆单词，决定将词典上所有的单词按照单词前缀将其分为 $K$ 类，具体的要求是:

现在已知字典上一共有 $N$ 个单词，小蓝想要知道将这 $N$ 个单词按照上述要求分为 $K$ 类，一共有多少种不同的方案。两个方案不同指的是两个方案各自选出的 $K$ 个单词前缀不完全相同。答案可能过大，所以你需要将答案对 $1000000007$（即 $10^9+7$）取模后输出。

输入格式

输入的第一行包含两个整数 $N$ 和 $K$；

接下来 $N$ 行，每行包含一个单词，由 $\mathtt{l}$、$\mathtt{q}$、$\mathtt{b}$ 三种字符组成。

输出格式

输出一个整数表示答案。答案可能很大，请输出答案对 $1000000007$ 取模的值。

输入输出样例 #1

输入 #1

4 2
lqb
lql
qqq
qql

输出 #1

4

说明/提示

样例说明

• 方案 1：$\mathtt{l}=\mathtt{lqb},\mathtt{lql}$、$\mathtt{q}=\mathtt{qqq},\mathtt{qql}$；
• 方案 2：$\mathtt{lq}=\mathtt{lqb},\mathtt{lql}$、$\mathtt{q}=\mathtt{qqq},\mathtt{qql}$；
• 方案 3：$\mathtt{l}=\mathtt{lqb},\mathtt{lql}$、$\mathtt{qq}=\mathtt{qqq},\mathtt{qql}$；
• 方案 4：$\mathtt{lq}=\mathtt{lqb},\mathtt{lql}$、$\mathtt{qq}=\mathtt{qqq},\mathtt{qql}$。

以方案 $1$ 为例，他表示选出的两类对应的前缀分别是 $\mathtt{l}$ 和 $\mathtt{q}$，属于前缀 $\mathtt{l}$ 的单词有 $\mathtt{lqb}$、$\mathtt{lql}$，属于前缀 $\mathtt{q}$ 的单词有 $\mathtt{qqq}$、$\mathtt{qql}$，方案 $1$ 将四个单词按照前缀分成了两类，且每类至少包含一个单词，每个单词仅属于一类，所以方案 $1$ 满足题意。

评测用例规模与约定

• 对于 $30\%$ 的评测用例，$1\le N\le 10$，$1\le K\le 5$；
• 对于 $50\%$ 的评测用例，$1\le N\le 50$，$1\le K\le 10$；
• 对于所有评测用例，$1\le N\le 200$，$1\le K\le 100$，$1\le$ 单词长度 $\le 10$。

C++实现

#include"bits/stdc++.h"
using namespace std;
const int N = 205 * 10, K = 105, mod = 1e9 + 7;
int n, k;
int trie[N][4], word[N], tot;
vector<int>g[N];
inline int get_num(char c) {
if (c == 'l')return 1;
if (c == 'q')return 2;
return 3;
}
void insert(string s) {
int u = 0;
for (char c : s) {
int a = get_num(c);
if (!trie[u][a]) {
trie[u][a] = ++tot;
g[u].push_back(tot);//建图
}
u = trie[u][a];
}
word[u]++;
}
long long dp[N][K];
void dfs(int u) {
if (u && word[u]) {//叶子节点
dp[u][1] = 1;
return;
}
dp[u][0] = 1;//初始状态
for (int v : g[u]) {
dfs(v);
long long t[K] = {0};//临时数组存储结果，避免计算时新计算的值影响后面的计算
for (int i = 0; i <= k; i++) {
for (int j = 0; j <= k – i; j++) {
t[i + j] = (t[i + j] + dp[u][i] * dp[v][j]) % mod;//枚举计算
}
}
memcpy(dp[u], t, sizeof dp[u]);//赋值回来
}
dp[u][1] = (dp[u][1] + 1) % mod;//单独选择该节点
}
signed main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
cin >> n >> k;
for (int i = 1; i <= n; i++) {
string s;
cin >> s;
insert(s);//建 Trie 树
}
dfs(0);//树形 DP
cout << dp[0][k];
return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容