算法标签：

字典树 数论

题解

一、题目分析

这段C++代码实现了对输入的多组DNA序列数据的处理功能。程序通过不断读取每组数据中的序列数量 n（m 在代码逻辑中未实际使用）和具体的 n 个DNA序列，先对这些序列进行字典序排序，然后统计每个不同DNA序列的出现次数，进一步再统计这些出现次数各自的频率，最后将频率从1到 n 依次输出。当输入的 n 和 m 都为0时，程序结束运行。

二、代码思路

1. 数据结构定义：
   • 定义宏 maxn 为 20005，用于限制存储DNA序列的数组 dna 以及辅助数组 ans 和 tmp 的大小。
   • 定义结构体 node，其中包含字符数组 str，用于存储单个DNA序列。dna 数组被声明为 node 类型，可存储多个DNA序列。
   • ans 数组用于记录每个出现次数出现的频率，tmp 数组用于临时记录每个不同DNA序列的出现次数。
2. 比较函数 cmp：该函数用于为 sort 函数提供比较规则。接受两个 node 类型的常量引用 a 和 b，通过 strcmp 函数比较它们的 str 成员（即DNA序列）的字典序。当 a 的字典序小于等于 b 时返回 1，否则返回 0，从而实现对 dna 数组中DNA序列按字典序从小到大排序。
3. 主函数流程：
   • 使用 while(scanf("%d%d",&n,&m)) 循环读取输入的 n 和 m，当 n 和 m 都为 0 时，通过 break 语句结束循环。
   • 利用 for 循环根据 n 的值读取 n 个DNA序列并存储到 dna 数组中。
   • 调用 sort 函数对 dna 数组进行排序，排序依据为 cmp 函数。
   • 初始化计数器 cnt 为 0，用 memset 函数将 ans 数组清零，并将 tmp[0] 初始化为 1。
   • 遍历排序后的 dna 数组，比较相邻的DNA序列。若相同，则增加 tmp[cnt] 的值；若不同，则 cnt 加 1，并将 tmp[cnt] 初始化为 1。
   • 遍历 tmp 数组，对于每个出现次数 tmp[i]，将 ans 数组中对应下标的元素 ans[tmp[i]] 加 1，以此统计每个出现次数的频率。
   • 最后通过一个 for 循环，从 1 到 n 依次输出 ans 数组中的元素，即每个出现次数的频率。

三、代码实现

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 20005;
const int MAX_STR_LEN = 25;

struct Node {
    char str[MAX_STR_LEN];
    // 重载小于运算符，用于 std::sort 排序
    bool operator<(const Node& other) const {
        return strcmp(str, other.str) < 0;
    }
};

Node dna[MAXN];
int ans[MAXN], tmp[MAXN];

int main() {
    int n, m;
    while (cin >> n >> m) {
        if (n == 0 && m == 0) {
            break;
        }

        // 输入验证
        if (n > MAXN) {
            cerr << "输入的 n 超出最大限制！" << endl;
            return 1;
        }

        // 读取 DNA 序列
        for (int i = 0; i < n; ++i) {
            cin >> dna[i].str;
        }

        // 排序
        sort(dna, dna + n);

        int cnt = 0;
        memset(ans, 0, sizeof(ans));
        tmp[0] = 1;

        // 统计相同 DNA 序列的数量
        for (int i = 0; i < n - 1; ++i) {
            if (strcmp(dna[i].str, dna[i + 1].str) == 0) {
                tmp[cnt]++;
            } else {
                tmp[++cnt] = 1;
            }
        }

        // 统计每种数量的出现次数
        for (int i = 0; i <= cnt; ++i) {
            ans[tmp[i]]++;
        }

        // 输出结果
        for (int i = 1; i <= n; ++i) {
            cout << ans[i] << endl;
        }
    }
    return 0;
}

四、复杂度分析

1. 时间复杂度：
   • 排序操作使用 sort 函数，其时间复杂度为 $O(n log n)$，n 为DNA序列的数量。
   • 后续的统计操作，包括统计每个不同DNA序列的出现次数以及这些出现次数的频率，均通过遍历数组实现，时间复杂度为 $O(n)$。
   • 因此，总体时间复杂度主要由排序操作决定，为 $O(n log n)$。
2. 空间复杂度：
   • dna 数组用于存储 n 个DNA序列，每个序列最多占用 25 个字符空间，空间复杂度为 $O(n)$。
   • ans 和 tmp 数组的大小均为 maxn，也与输入数据规模相关，空间复杂度同样为 $O(n)$。
   • 所以，整个程序的空间复杂度为 $O(n)$。

五、注意事项

1. 输入数据的格式要严格符合代码要求，使用 scanf 函数读取 n、m 和DNA序列时，确保输入的是正确类型的数据，否则可能导致程序运行异常。
2. 在处理新的一组输入数据时，ans 数组需要通过 memset 函数清零，以避免上一组数据的统计结果对当前组产生影响。