问题描述

题目要求我们根据给定的字母组合列表，对合法的单词进行编号和查询。合法的单词是指不包含列表中任何字母组合的字符串。我们需要实现两个功能：

1. 给定一个单词，输出它的编号。
2. 给定一个编号，输出对应的单词。

单词的编号规则如下：

• 按长度递增排序，长度相同的单词按字典序排序。
• 编号从1开始。

输入输出格式

• 输入：
  • 第一行：测试用例数量 ( T )。
  • 每个测试用例：
    • 第一行：两个整数 ( N ) 和 ( M )，分别表示字母组合的数量和查询的数量。
    • 接下来 ( N ) 行：每行一个字母组合（长度为1到3）。
    • 接下来 ( M ) 行：每行一个查询，可以是单词或编号。
• 输出：
  • 对于每个查询，输出单词对应的编号，或者编号对应的单词。

解题思路

1. 标记非法组合：使用三维数组 taboo 标记所有非法的字母组合。
2. 动态规划计算合法单词数量：通过递归和记忆化搜索，计算给定长度和前两个字母的合法单词数量。
3. 回溯生成单词：根据编号，通过回溯法生成对应的单词。
4. 二分查找单词编号：对于给定的单词，通过二分查找确定其编号。

代码实现

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>

using namespace std;

#define CZ ('z' - 'a' + 1)  // 字母表大小（26）
#define INVC CZ             // 无效字符标记
#define MAX (2000000001LL)  // 最大值

bool taboo[CZ + 1][CZ + 1][CZ + 1];  // 标记非法字母组合
char buf[21];                        // 临时缓冲区
char ans[21];                        // 存储结果单词
long long tbl[CZ + 1][CZ + 1][21];   // 动态规划表

// 动态规划计算合法单词数量
long long calc_len(char p1, char p2, int len) {
	if (len == 0) return 1;  // 长度为0时，只有一个空字符串
	if (len >= 20) return MAX;  // 长度过大，直接返回最大值
	if (tbl[p1][p2][len] != -1)
		return tbl[p1][p2][len];  // 如果已经计算过，直接返回结果
	long long ans = 0;
	for (int p3 = 0; p3 < CZ; p3++) {
		if (!taboo[p1][p2][p3])  // 如果当前字母组合不非法
			ans += calc_len(p2, p3, len - 1);  // 递归计算剩余长度
	}
	return tbl[p1][p2][len] = ans;  // 存储结果并返回
}

// 回溯生成单词
void find(int idx, char p1, char p2, int len, long long n) {
	long long prev = 0;
	int p3 = 0;
	for (p3 = 0; p3 < CZ; p3++) {
		if (taboo[p1][p2][p3]) continue;  // 跳过非法组合
		long long t = calc_len(p2, p3, len - 1);  // 计算当前分支的合法单词数量
		if (prev + t >= n) break;  // 找到目标分支
		prev += t;
	}
	ans[idx] = 'a' + p3;  // 添加当前字母到结果
	if (len != 1)
		find(idx + 1, p2, p3, len - 1, n - prev);  // 递归生成剩余部分
}

// 根据编号找到对应的单词
void find(long long n) {
	int len = 1;
	while (n > calc_len(INVC, INVC, len)) {  // 找到目标单词的长度
		n -= calc_len(INVC, INVC, len);
		len++;
	}
	ans[len] = '\0';  // 设置字符串结束符
	find(0, INVC, INVC, len, n);  // 生成目标单词
}

// 比较函数
int cmp(char *p1, char *p2) {
	int len1 = strlen(p1);
	int len2 = strlen(p2);
	if (len1 < len2) return -1;
	if (len1 > len2) return 1;
	return strcmp(p1, p2);  // 按字典序比较
}

// 主函数
int main(void) {
	int cases;
	scanf("%d", &cases);
	while (cases--) {
		int n, q;
		scanf("%d %d", &n, &q);
		memset(taboo, 0, sizeof(taboo));  // 初始化非法组合标记
		while (n--) {
			scanf(" %s", buf);
			int len = strlen(buf);
			if (len == 1) {
				for (int i = 0; i < CZ + 1; i++)
					for (int j = 0; j < CZ + 1; j++)
						taboo[i][j][buf[0] - 'a'] = true;  // 标记单字母非法组合
			} else if (len == 2) {
				for (int i = 0; i < CZ + 1; i++)
					taboo[i][buf[0] - 'a'][buf[1] - 'a'] = true;  // 标记双字母非法组合
			} else {
				taboo[buf[0] - 'a'][buf[1] - 'a'][buf[2] - 'a'] = true;  // 标记三字母非法组合
			}
		}
		memset(tbl, -1, sizeof(tbl));  // 初始化动态规划表
		while (q--) {
			scanf("%s", buf);
			if (isdigit(buf[0])) {  // 如果是数字
				int n = atoi(buf);
				find(n);  // 找到对应单词
				printf("%s\n", ans);
			} else {  // 如果是单词
				long long low = 1, high = MAX, mid;
				while (true) {
					mid = (low + high) >> 1;  // 二分查找
					find(mid);  // 生成中间编号对应的单词
					int res = cmp(buf, ans);  // 比较目标单词和生成的单词
					if (res < 0) {
						high = mid;
					} else if (res > 0) {
						low = mid;
					} else {
						low = mid;  // 找到目标编号
						break;
					}
				}
				printf("%lld\n", low);
			}
		}
	}
	return 0;
}

代码说明

1. 全局变量和常量定义：

   • CZ：字母表大小（26）。
   • INVC：无效字符标记。
   • MAX：最大值，用于处理边界情况。
   • taboo：标记非法字母组合。
   • buf 和 ans：临时缓冲区和存储结果单词。
   • tbl：动态规划表，用于存储中间结果，避免重复计算。

2. calc_len 函数：

   • 递归计算从当前字母组合 (p1, p2) 开始，长度为 len 的合法单词数量。
   • 使用动态规划表 tbl 存储中间结果，避免重复计算。

3. find 函数：

   • 根据编号 n 生成对应的单词。
   • 使用回溯法，逐个字母生成单词。

4. cmp 函数：

   • 比较两个单词的大小，先比较长度，再按字典序比较。

5. 主函数：

   • 处理多个测试用例。
   • 读取非法字母组合，标记到 taboo 中。
   • 初始化动态规划表 tbl。
   • 对于每个查询，根据输入是数字还是单词，调用相应的函数进行处理。

示例运行

输入：

2
3 4
q
ab
aaa
16
r
27
aac
7 2
a
b
c
d
ef
ghi
ijk
102345678
ksvfuw

输出：

p
17
ac
650
xexgun
39174383

总结

本题通过动态规划和回溯法，解决了合法单词的编号和查询问题。通过标记非法组合，避免了非法单词的生成，同时利用二分查找优化了查询效率。