E卷-单词接龙(100分)

单词接龙

问题描述

单词接龙是一种有趣的文字游戏。在这个问题中，我们需要按照特定规则进行单词接龙，并找出最长的单词串。规则如下：

1. 接龙的单词首字母必须与前一个单词的尾字母相同。
2. 当有多个首字母相同的单词可选时，选择长度最长的单词。如果长度相同，则选择字典序最小的单词。
3. 已经使用过的单词不能重复使用。

给定一组全部由小写字母组成的单词数组，以及指定的起始单词，请输出按照上述规则形成的最长单词串。单词串是由多个单词直接拼接而成，中间没有空格。

输入格式

输入包含多行：

1. 第一行为一个非负整数 ，表示起始单词在数组中的索引，。
2. 第二行为一个非负整数 ，表示单词的总数。
3. 接下来的 行，每行包含一个单词，表示单词数组中的单词。

输出格式

输出一个字符串，表示最终拼接的最长单词串。

样例输入1

0
6
word
dd
da
dc
dword
d

样例输出1

worddwordda

样例输入2

4
6
word
dd
da
dc
dword
d

样例输出2

dwordda

样例解释

数据范围

• 
• 单个单词的长度范围：

题解

贪心+模拟

这道题目本质上是一个贪心算法问题，需要在每一步都做出最优选择。解题思路如下：

1. 首先，要从输入中提取起始单词，并将其作为单词串的第一个单词。

2. 接下来，我们需要对剩余的单词进行分类和排序。以使用一个哈希表来按首字母对单词进行分类。

3. 对于每个首字母分类，需要对其中的单词进行排序。排序的优先级是：

   • 首先按单词长度降序排列
   • 如果长度相同，则按字典序升序排列

4. 然后，开始构建单词串。每次我们都查看当前单词串最后一个单词的尾字母，然后在对应的首字母分类中选择第一个单词（如果存在的话）添加到单词串中。

5. 重复步骤4，直到无法找到合适的单词为止。

6. 最后，我们将单词串中的所有单词拼接起来，得到最终的结果。

这个算法的时间复杂度主要来自于对单词的排序，为 ，其中 是单词的总数。考虑到题目给出的数据范围（），这个复杂度是完全可以接受的。

参考代码

• Python

def word_chain(start_index, words):
    # 初始化结果链和单词分类字典
    chain = [words.pop(start_index)]
    prefix = {}
    
    # 对剩余单词按首字母分类
    for word in words:
        first_char = word[0]
        if first_char not in prefix:
            prefix[first_char] = []
        prefix[first_char].append(word)
    
    # 对每个分类进行排序：先按长度降序，再按字典序升序
    for char in prefix:
        prefix[char].sort(key=lambda x: (-len(x), x))
    
    # 构建单词链
    while True:
        last_word = chain[-1]
        last_char = last_word[-1]
        if last_char in prefix and prefix[last_char]:
            next_word = prefix[last_char].pop(0)
            chain.append(next_word)
        else:
            break
    
    # 返回拼接后的结果
    return ''.join(chain)

# 读取输入
start_index = int(input())
n = int(input())
words = [input().strip() for _ in range(n)]

# 输出结果
print(word_chain(start_index, words))

• C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_WORDS 20
#define MAX_WORD_LEN 31

// 单词结构体
typedef struct {
    char word[MAX_WORD_LEN];
    int length;
} Word;

// 比较函数，用于排序
int compare(const void* a, const void* b) {
    Word* w1 = (Word*)a;
    Word* w2 = (Word*)b;
    if (w1->length != w2->length)
        return w2->length - w1->length;  // 长度降序
    return strcmp(w1->word, w2->word);   // 字典序升序
}

// 主函数
int main() {
    int start_index, n;
    Word words[MAX_WORDS];
    char result[MAX_WORDS * MAX_WORD_LEN] = {0};
    
    // 读取输入
    scanf("%d", &start_index);
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%s", words[i].word);
        words[i].length = strlen(words[i].word);
    }
    
    // 将起始单词加入结果
    strcat(result, words[start_index].word);
    
    // 标记起始单词为已使用
    words[start_index].length = 0;
    
    // 主循环
    while (1) {
        char last_char = result[strlen(result) - 1];
        int found = 0;
        
        // 对剩余单词排序
        qsort(words, n, sizeof(Word), compare);
        
        // 查找下一个单词
        for (int i = 0; i < n; i++) {
            if (words[i].length > 0 && words[i].word[0] == last_char) {
                strcat(result, words[i].word);
                words[i].length = 0;  // 标记为已使用
                found = 1;