P11615 Solution

OIerWu_829 · 2025-02-11 21:55:37 · 题解

题目传送门

我们可以用链地址法来解决哈希冲突。

用一个结构体表示链表中的节点，k 存储键，v 存储值，nxt 存储下一个节点的索引，通过这种方式就可以将冲突的键值对连接成一个链表，再用一个 head 数组存储每个哈希桶对应的链表的头节点索引，初始化为 -1 表示链表为空。

每次输入一个键 x 和一个值 y，调用函数进行查询和更新，然后将结果储存在 p 中，再累加 i\times p 到答案最后输出。这个函数就是先用取模运算将 x 映射到哈希表的一个位置 pos，然后遍历哈希桶 pos 对应的链表，检查是否存在键 x，如果找到就将其原来的值赋给 p，并更新为新值 y；如果键 x 不存在就将 p 置为 0，表示原来的值为 0，然后创建一个新的节点，将键值对存储在该节点中，并将其插入到链表的头部。

#include <iostream>
#include <cstring>

using namespace std;
using ULL = unsigned long long;

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 (!isdigit(ch)) ch = gc();
    while (isdigit(ch)) x = x * 10 + (ch ^ 48), ch = gc();
    return x;
}

const int N = 5e6 + 5;
const int M = 1e7 + 7;

struct Edge
{
    ULL k, v;
    int nxt;
} e[N];

int head[M], cnt;

void insert(ULL x, ULL y, ULL &p)
{
    int pos = x % M;
    for (int i = head[pos]; i != -1; i = e[i].nxt)
        if (e[i].k == x)
        {
            p = e[i].v;
            e[i].v = y;
            return;
        }
    p = 0;
    e[cnt].k = x;
    e[cnt].v = y;
    e[cnt].nxt = head[pos];
    head[pos] = cnt++;
}

int main()
{
    int n = rd();
    memset(head, -1, sizeof head);
    cnt = 0;
    ULL ans = 0;
    for (int i = 1; i <= n; i++)
    {
        ULL x = rd(), y = rd(), p;
        insert(x, y, p);
        ans += (ULL)i * p;
    }
    cout << ans;
    return 0;
}