主要做ai解答的记录

哈希模板

[cf大佬博客](Blowing up unordered_map, and how to stop getting hacked on it - Codeforces)

1. 标准 unordered_map 安全增强版

这是在比赛中最通用的写法，兼容所有现代 C++ 编译器。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <unordered_map>
#include <chrono> // 必须引用，用于获取随机时间

using namespace std;

// --- 第一部分：把图片里的 custom_hash 结构体抄下来 ---
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // 这是一个高品质的扰动函数，把输入的位彻底打乱
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        // 使用系统时间作为随机种子，出题人无法预知
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

int main() {
    // --- 第二部分：使用自定义哈希定义 map ---
    // 语法：unordered_map<键类型, 值类型, 自定义哈希类>
    unordered_map<long long, long long, custom_hash> safe_map;

    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        long long x, y;
        cin >> x >> y;

        // 查询旧值并更新，逻辑和普通 map 一模一样
        if (safe_map.count(x)) {
            cout << "f(" << x << ") 的旧值是: " << safe_map[x] << endl;
        } else {
            cout << "f(" << x << ") 之前没有值，默认为 0" << endl;
        }

        safe_map[x] = y; // 更新映射
    }

    return 0;
}

2. 进阶版：高性能 gp_hash_table（最快选择）

gp_hash_table，这是 C++ 扩展库里的“神级”哈希表。它比 unordered_map 快好几倍，但它非常容易被卡（因为它使用 2 的幂次作为桶大小）。所以它必须配合 custom_hash 使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <chrono>
// PBDS 库的头文件
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>

using namespace std;
using namespace __gnu_pbds; // 必须使用这个命名空间

struct custom_hash {
    /* ... 和上面一样的 splitmix64 代码 ... */
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

int main() {
    // 定义一个超级快的哈希表
    // 它的用法和 unordered_map 几乎完全一样
    gp_hash_table<long long, int, custom_hash> fast_safe_table;

    fast_safe_table[123456789012345LL] = 1;
    
    cout << fast_safe_table[123456789012345LL] << endl;

    return 0;
}

为什么要这样写？（总结）

  1. 防止碰撞攻击：你定义的 FIXED_RANDOM 每次运行都不一样。即使出题人知道你用了 splitmix64，他也没法构造出让你冲突的数据，因为他不知道你那一秒钟的 chrono 种子是多少。
  2. 通过高难度子任务：如果专门卡 unordered_map。你只要加上这个 custom_hash，原本超时的代码可能直接就 AC (Accepted) 了。
  3. 万能模板：这个 struct custom_hash 。以后只要题目可美美保存下来。涉及到 long long 类型的哈希映射，直接把它扔进代码开头即可。

模板应用

[洛谷P11615](P11615 【模板】哈希表 - 洛谷)
![[Pasted image 20260504091237.png]]

为了苟对，需要把刚才学到的 “快读” + “手写线性探测哈希” + “SplitMix64位扰动” 结合在一起。

解题核心逻辑

  1. 数据类型：全部使用 unsigned long long (简称 ull)，因为它正好是 64 位，且在 C++ 中 ull 的溢出自动相当于对 $2^{64}$ 取模。
  2. 哈希冲突处理：题目明确说了要 hack 标准库，所以我们手动实现一个闭散列（线性探测）哈希表。
  3. 哈希函数：使用 splitmix64 逻辑，确保 $x$ 被打得足够碎。
  4. 快速读入：题目给出的 rd() 函数必须写，否则 500 万数据读入就会超时。

完整的实践代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <cstdio>
#include <iostream>

using namespace std;

typedef unsigned long long ull;

// --- 1. 高效快读 (题目图片中提供的逻辑) ---
char buf[1 << 23], *p1 = buf, *p2 = buf;
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)

inline ull rd() {
    ull x = 0;
    char ch = gc();
    while (ch < '0' || ch > '9') {
        if (ch == EOF) return 0;
        ch = gc();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + (ch - '0');
        ch = gc();
    }
    return x;
}


const int HashSize = 1 << 24;
const int Mask = HashSize - 1;

ull keys[HashSize];
ull vals[HashSize];
bool used[HashSize];

// SplitMix64 扰动函数：防止被 Hack 的核心
inline ull splitmix64(ull x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
}

// 哈希表查询与更新
// 返回值是旧的 f(x)
ull query_and_set(ull x, ull y) {
    int pos = splitmix64(x) & Mask;
    
    // 线性探测
    while (used[pos]) {
        if (keys[pos] == x) {
            ull old_v = vals[pos];
            vals[pos] = y; // 更新 f(x) <- y
            return old_v;
        }
        pos = (pos + 1) & Mask;
    }
    
    // 如果没找到，说明之前 f(x) = 0
    used[pos] = true;
    keys[pos] = x;
    vals[pos] = y;
    return 0;
}

int main() {
    int n = (int)rd();
    ull final_ans = 0;

    for (int i = 1; i <= n; i++) {
        ull x = rd();
        ull y = rd();

        // 这里的 ans_i 是查询到的 f(x)
        ull ans_i = query_and_set(x, y);
        
        // 按照题目要求累加结果
        // i * ans_i 在 ull 下会自动对 2^64 取模
        final_ans += (ull)i * ans_i;
    }

    printf("%llu\n", final_ans);

    return 0;
}

为什么这段代码能通过“子任务 4”？（AI如是答

  1. 线性探测 vs 拉链法：
    标准库 unordered_map 是拉链法，它需要为每个节点分配内存。在 $N=5 \times 10^6$ 时，频繁的内存分配和指针跳转（Cache Miss）非常慢。我们手写的数组线性探测是连续内存，CPU 访问极快。
  2. splitmix64 的威力：
    Subtask 4 的 Hack 数据通常是故意构造的“等差数列”或者“特定质数的倍数”。splitmix64 这种位运算组合能把这些规律彻底打碎，让它们在 HashSize 范围内分布得非常均匀，几乎不产生冲突。
  3. Mask 取模优化：
    我们把 HashSize 设为 $2$ 的幂次，通过 & Mask 快速得到下标。这比 % 运算要快得多，在千万级计算中能省下大量时间。