算法标签：

字符串 哈希表

题解

一、题目分析

这段C++ 代码实现了一个模拟游戏的功能，游戏基于一个哈希表来记录游戏过程中产生的数值及其出现次数。根据输入的游戏参数 (n)、(a)、(b)，通过特定的计算规则生成一系列数值。在生成数值的过程中，利用哈希表记录每个数值出现的次数，当某个数值出现两次时进行相应计数（可理解为一种“特殊事件”计数），当某个数值出现三次时游戏结束。最后输出总数值 (n) 减去“特殊事件”计数后的结果。程序会持续读取输入数据，直到输入的 (n = 0) 为止。

二、代码思路

1. 数据结构定义：
   • 定义常量 MOD = 1000007，作为哈希表的大小，用于确定哈希函数的取值范围。
   • 使用 typedef long long ll; 为 long long 类型定义别名 ll，方便后续代码书写。
   • 定义结构体 node，包含三个成员：
     • n：用于存储游戏中的某个数值。
     • cnt：记录该数值在游戏过程中出现的次数。
     • next：指针，用于构建链表结构，处理哈希冲突（链地址法）。
   • 定义数组 mp[MOD]，用于存储哈希表的节点信息。
   • 定义数组 head[MOD]，作为哈希表的表头数组，每个元素存储对应链表的头节点索引。
   • 定义变量 hash_table_index，用于记录 mp 数组中已使用的下一个索引位置，初始化为 1（因为 0 用于表示空链表）。
2. 初始化函数 init：
   • 函数遍历 head 数组，将每个元素初始化为 0，表示每个链表的头节点索引初始为空。
   • 将 hash_table_index 初始化为 1，为后续添加节点做准备。
3. 添加元素函数 add：
   • 函数接受两个参数 u（哈希值，确定链表位置）和 v（要添加的数值）。
   • 在 mp 数组中，根据 hash_table_index 确定新节点的位置，将数值 v 存储在 mp[hash_table_index].n 中，将出现次数 cnt 初始化为 1，即 mp[hash_table_index].cnt = 1。
   • 将新节点的 next 指针指向当前 u 位置链表的头节点，即 mp[hash_table_index].next = head[u]。
   • 更新 u 位置链表的头节点为新节点的索引，即 head[u] = hash_table_index++，然后将 hash_table_index 自增 1，指向下一个可用的节点位置。
4. 查找元素函数 find：
   • 函数接受两个参数 t（哈希值，确定链表位置）和 x（要查找的数值）。
   • 从 head[t] 开始，通过遍历链表（i = head[t]; i; i = mp[i].next）查找数值为 x 的节点。
   • 如果找到匹配的节点（mp[i].n == x），将该节点的出现次数 cnt 加 1，即 mp[i].cnt++;，并返回更新后的出现次数。
   • 如果遍历完链表都没有找到匹配的节点，则返回 0。
5. 主函数 main：
   • 关闭 cin 和 cout 与 stdio 的同步，提高输入输出效率，即 std::ios::sync_with_stdio(false);。
   • 定义变量 x（用于存储每次计算得到的数值）、n（游戏的总数值）、a 和 b（计算数值的参数）、u（哈希值）、cnt（记录出现两次的数值的计数）。
   • 使用 while(std::cin >> n && n) 循环读取输入的总数值 n，当 n = 0 时结束循环。
   • 在每次循环中，读取参数 a 和 b，调用 init 函数初始化哈希表。
   • 计算初始数值 x = b%n，并将 cnt 初始化为 0。
   • 进入一个无限循环，在循环内部：
     • 调用 find 函数查找数值 x，并将返回的出现次数存储在 u 中。
     • 如果 u == 2，说明数值 x 出现了两次，将 cnt 加 1。
     • 如果 u == 3，说明数值 x 出现了三次，跳出循环，游戏结束。
     • 如果 u == 0，说明数值 x 是第一次出现，调用 add 函数将其添加到哈希表中。
     • 根据计算规则 x = (((a*x)%n*x) + b)%n 更新 x 的值。
   • 循环结束后，输出 n - cnt，即游戏结束后的结果。

三、代码实现

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>

using namespace std;

const int MOD = 1000007;
typedef long long ll;

// 定义结构体表示哈希表节点
struct node {
    long long n; // 存储游戏中的某个数值
    int cnt; // 记录该数值出现的次数
    int next; // 指向下一个节点，用于链表结构
} mp[MOD];

int head[MOD], hash_table_index; // 将t改为更具描述性的hash_table_index

// 初始化哈希表
void init() {
    for(int i = 0; i < MOD; ++i)    
        head[i] = 0;
    hash_table_index = 1;
}

// 向哈希表中添加元素
void add(int u, long long v) {
    mp[hash_table_index].n = v; 
    mp[hash_table_index].cnt = 1;
    mp[hash_table_index].next = head[u]; 
    head[u] = hash_table_index++;
}

// 在哈希表中查找元素并更新计数
int find(int t, long long x) {
    int i;
    for(i = head[t]; i; i = mp[i].next) {
        if(mp[i].n == x) {
            mp[i].cnt++;
            return mp[i].cnt;
        }
    }
    return 0;
}

int main() {
    //freopen("data.in", "r", stdin);
    std::ios::sync_with_stdio(false); // 关闭cin和cout与stdio的同步，提高输入输出效率
    ll x;
    int n, a, b, u;
    int cnt;
    while(std::cin >> n && n) { // 使用cin进行输入
        std::cin >> a >> b; // 使用cin进行输入
        init();
        x = b%n; 
        cnt = 0;
        while(1) {
            u = find(x%MOD, x);
            if(u == 2) 
                cnt++;
            if(u == 3)    
                break;
            if(!u) {
                add(x%MOD, x);
            }
            x = (((a*x)%n*x) + b)%n;
        }
        std::cout << n - cnt << std::endl; // 使用cout进行输出
    }
    return 0;
}

四、复杂度分析

1. 时间复杂度：
   • 在 add 函数中，每次添加操作的时间复杂度为常数级 (O(1))，因为只是对节点进行简单的赋值和指针操作。
   • 在 find 函数中，最坏情况下需要遍历整个链表来查找节点，链表长度可能与总数值 (n) 相关（当哈希冲突严重时），因此每次调用 find 函数的时间复杂度为 (O(n))。
   • 在主函数的循环中，每次循环都可能调用 find 和 add 函数，循环次数不确定，但最多不超过总数值 (n) 次。所以整个程序的时间复杂度在最坏情况下为 (O(n^2))。
2. 空间复杂度：
   • 程序使用了哈希表相关的数据结构，包括数组 mp[MOD] 和 head[MOD]，哈希表的大小为 MOD，空间占用为 (O(MOD))，可近似看作 (O(n))（(n) 为较大规模时）。
   • 此外，还使用了一些临时变量如 x、u、cnt 等，这些变量的空间占用为常数级，对总体空间复杂度影响较小。因此，总体空间复杂度为 (O(n))。

五、注意事项

1. 哈希冲突处理：采用链地址法处理哈希冲突，在操作链表时要注意指针的正确使用，避免空指针引用和内存泄漏问题。当哈希冲突严重时，链表可能会很长，导致查找效率降低，需要考虑优化哈希函数或调整哈希表大小。
2. 数据类型选择：使用 ll（即 long long）类型处理数值，是为了应对可能出现的较大数值，防止整数溢出。在处理类似数值计算问题时，需根据实际情况合理选择数据类型。
3. 输入输出效率：代码中使用了 std::ios::sync_with_stdio(false); 关闭了 cin 和 cout 与 stdio 的同步，以提高输入输出效率。但需要注意的是，在使用这种方式后，不能再混合使用 cin/cout 和 scanf/printf 进行输入输出，否则可能会导致错误。
4. 边界条件：在处理哈希表的索引和链表操作时，要注意边界条件，例如链表为空的情况以及 hash_table_index 的正确使用，避免数组越界等错误。