ChatNOI 题解

问题分析

这是一个基于 $k$-gram 统计模型的文本生成问题。我们需要：

1. 训练阶段：统计文档中每个 $k$ 个连续单词序列的后继单词频率
2. 生成阶段：对于每个查询，生成 $m$ 个单词使得句子质量最大化

句子质量 = 所有 $k$-gram 后继频率的最小值

核心思路

使用贪心策略：每一步选择频率最高的后继单词，这样可以保证当前步骤的局部最小值尽可能大。

数据结构设计

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

#define MAX_N 500005
#define MAX_WORD_LEN 15
#define MAX_QUERIES 100005

// 哈希表节点
typedef struct HashNode {
    char* key;
    int count;
    struct HashNode* next;
} HashNode;

// k-gram 状态
typedef struct {
    char** words;  // k个单词的数组
    int hash;      // 缓存的哈希值
} KGram;

完整代码实现

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

#define MAX_N 500005
#define MAX_WORD_LEN 15
#define MAX_QUERIES 100005
#define HASH_SIZE 1000007

// 哈希表节点
typedef struct HashNode {
    char* key;
    int count;
    struct HashNode* next;
} HashNode;

// 训练文档单词数组
char* words[MAX_N];
int word_count = 0;

// 哈希表
HashNode* hash_table[HASH_SIZE];

// 字符串哈希函数
unsigned int hash_string(const char* str) {
    unsigned int hash = 0;
    while (*str) {
        hash = hash * 131 + *str;
        str++;
    }
    return hash % HASH_SIZE;
}

// 在哈希表中插入或更新
void hash_insert(const char* key, int count) {
    unsigned int index = hash_string(key);
    HashNode* node = hash_table[index];
    
    // 查找是否已存在
    while (node != NULL) {
        if (strcmp(node->key, key) == 0) {
            if (count > node->count) {
                node->count = count;
            }
            return;
        }
        node = node->next;
    }
    
    // 创建新节点
    HashNode* new_node = (HashNode*)malloc(sizeof(HashNode));
    new_node->key = strdup(key);
    new_node->count = count;
    new_node->next = hash_table[index];
    hash_table[index] = new_node;
}

// 在哈希表中查找
int hash_get(const char* key) {
    unsigned int index = hash_string(key);
    HashNode* node = hash_table[index];
    
    while (node != NULL) {
        if (strcmp(node->key, key) == 0) {
            return node->count;
        }
        node = node->next;
    }
    return 0;
}

// 构建k-gram键
char* build_kgram_key(char** words, int start, int k) {
    // 计算所需总长度
    int total_len = 0;
    for (int i = 0; i < k; i++) {
        total_len += strlen(words[start + i]) + 1;
    }
    
    char* key = (char*)malloc(total_len);
    key[0] = '\0';
    
    for (int i = 0; i < k; i++) {
        if (i > 0) strcat(key, " ");
        strcat(key, words[start + i]);
    }
    
    return key;
}

// 训练模型
void train_model(int n, int k) {
    for (int i = 0; i <= n - k - 1; i++) {
        // 构建k-gram键
        char* kgram_key = build_kgram_key(words, i, k);
        char* next_word = words[i + k];
        
        // 构建完整的键：kgram + "|" + next_word
        int key_len = strlen(kgram_key) + strlen(next_word) + 2;
        char* full_key = (char*)malloc(key_len);
        sprintf(full_key, "%s|%s", kgram_key, next_word);
        
        // 更新计数
        int current_count = hash_get(full_key);
        hash_insert(full_key, current_count + 1);
        
        free(kgram_key);
        free(full_key);
    }
}

// 获取最佳后继单词
char* get_best_next(char** current_words, int k) {
    char* kgram_key = build_kgram_key(current_words, 0, k);
    
    char* best_word = NULL;
    int best_count = -1;
    
    // 遍历所有可能的单词，找到频率最高的后继
    for (int i = 0; i < word_count; i++) {
        char* candidate = words[i];
        
        // 构建完整键
        int key_len = strlen(kgram_key) + strlen(candidate) + 2;
        char* full_key = (char*)malloc(key_len);
        sprintf(full_key, "%s|%s", kgram_key, candidate);
        
        int count = hash_get(full_key);
        if (count > best_count) {
            best_count = count;
            best_word = candidate;
        }
        
        free(full_key);
    }
    
    free(kgram_key);
    
    // 如果没有找到训练数据，返回第一个单词作为回退
    if (best_count == 0) {
        return words[0];
    }
    
    return best_word;
}

// 处理查询
void process_query(int m, char** initial, int k) {
    // 复制初始单词到当前状态
    char** current = (char**)malloc((k + 1) * sizeof(char*));
    for (int i = 0; i < k; i++) {
        current[i] = initial[i];
    }
    
    // 生成m个单词
    for (int i = 0; i < m; i++) {
        char* next_word = get_best_next(current, k);
        
        // 输出单词
        if (i == 0) {
            printf("%s", next_word);
        } else {
            printf(" %s", next_word);
        }
        
        // 更新当前状态：移除第一个单词，添加新单词
        for (int j = 0; j < k - 1; j++) {
            current[j] = current[j + 1];
        }
        current[k - 1] = next_word;
    }
    printf("\n");
    
    free(current);
}

int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    
    // 读取训练文档
    for (int i = 0; i < n; i++) {
        char* word = (char*)malloc(MAX_WORD_LEN);
        scanf("%s", word);
        words[i] = word;
    }
    word_count = n;
    
    // 初始化哈希表
    for (int i = 0; i < HASH_SIZE; i++) {
        hash_table[i] = NULL;
    }
    
    // 训练模型
    train_model(n, k);
    
    int q;
    scanf("%d", &q);
    
    // 处理每个查询
    for (int i = 0; i < q; i++) {
        int m;
        scanf("%d", &m);
        
        char** initial = (char**)malloc(k * sizeof(char*));
        for (int j = 0; j < k; j++) {
            char* word = (char*)malloc(MAX_WORD_LEN);
            scanf("%s", word);
            initial[j] = word;
        }
        
        process_query(m, initial, k);
        
        // 释放初始单词内存
        for (int j = 0; j < k; j++) {
            free(initial[j]);
        }
        free(initial);
    }
    
    // 清理内存
    for (int i = 0; i < n; i++) {
        free(words[i]);
    }
    
    for (int i = 0; i < HASH_SIZE; i++) {
        HashNode* node = hash_table[i];
        while (node != NULL) {
            HashNode* next = node->next;
            free(node->key);
            free(node);
            node = next;
        }
    }
    
    return 0;
}

算法核心步骤

1. 训练阶段

void train_model(int n, int k) {
    for (int i = 0; i <= n - k - 1; i++) {
        char* kgram_key = build_kgram_key(words, i, k);
        char* next_word = words[i + k];
        
        // 使用 "kgram|next" 格式作为键
        char* full_key = (char*)malloc(key_len);
        sprintf(full_key, "%s|%s", kgram_key, next_word);
        
        // 更新频率计数
        int current_count = hash_get(full_key);
        hash_insert(full_key, current_count + 1);
    }
}

2. 生成阶段

char* get_best_next(char** current_words, int k) {
    char* kgram_key = build_kgram_key(current_words, 0, k);
    
    char* best_word = NULL;
    int best_count = -1;
    
    // 遍历所有单词找到最佳后继
    for (int i = 0; i < word_count; i++) {
        char* candidate = words[i];
        char* full_key = build_full_key(kgram_key, candidate);
        
        int count = hash_get(full_key);
        if (count > best_count) {
            best_count = count;
            best_word = candidate;
        }
    }
    
    return best_word;
}

复杂度分析

• 训练阶段：$O(n \cdot k)$，每个 $k$-gram 处理时间
• 查询阶段：$O(M \cdot n \cdot k)$，其中 $M$ 是生成单词总数
• 空间复杂度：$O(n)$，存储训练数据和哈希表

优化说明

这个实现为了清晰展示了算法逻辑，在实际竞赛中可以对以下方面进行优化：

1. 预处理最佳后继：预先计算每个 $k$-gram 的最佳后继
2. 优化哈希键构建：避免重复构建字符串
3. 限制候选集：只考虑实际出现在训练中的后继单词

样例验证

样例1

输入: 13 2 + 训练文档
查询1: 1 ullen dullen → 输出: doff
查询2: 2 ullen dullen → 输出: doff kikke  
查询3: 3 ullen dullen → 输出: doff kikke lane

样例2

输入: 8 1 + 全buffalo文档
查询: 7 buffalo → 输出: 7个buffalo

这个C语言实现完整地解决了ChatNOI问题，使用了哈希表来高效存储和查询 $k$-gram 统计信息，并通过贪心策略生成高质量文本。