翻译
查看原帖
翻译
1003721
shb20111113楼主2024/1/6 14:53

智能海狸和解决碰撞

题目描述

来自ABBYY的聪明海狸有很多爱好。其中之一就是构造高效的哈希表。哈希表中最严重的问题之一是解决冲突。海狸对这个问题很感兴趣，他决定详细研究一下。

我们假设哈希表包含hh单元格，编号从00到h−1h-1。对象被添加到和从中移除。每个对象都有自己唯一的标识符。此外，每个对象都有一个相应的哈希值——一个介于00和h−1h-1之间的整数，包括00。当一个对象被添加到表中时，如果该对象的哈希值对应的单元格是空闲的，那么这个对象就会被添加到表中。如果单元格已被另一个对象占用，则会发生碰撞。当一个对象从表中删除时，它所占用的单元格变为空。

智能海狸最近学会了线性探测解决碰撞的方法。具体情况如下。假设添加的对象的哈希值等于tt，并且表的单元格tt已经被占用。然后我们尝试将这个对象添加到单元格(t+m)modh(t+m) mod\quad h。如果它也被占用，那么我们尝试单元格(t+2⋅m)modh(t+2·m) mod\quad h，然后单元格(t+3⋅m)modh(t+3·m) mod \quad h，以此类推。注意，在某些情况下，可能无法将新对象添加到表中。可以保证这个问题的输入不包含这种情况。

运算amodba \quad mod\quad b意味着取数aa除以数bb的余数。

海狸立刻觉得这种技术很不理想，于是他决定评估一下它的低效率。因此，给您一个操作序列，每个操作要么向表中添加一个对象，要么从表中删除一个对象。在添加新对象时，将执行对表的一系列调用。对已占用单元的调用称为dummy。换句话说，如果上面描述的算法的结果是对象被添加到单元格(t+i⋅m)modh(t+i·m) mod \quad h (i≥0)(i\geq 0) ，那么正好执行了，那么正好执行了 i $ 虚拟调用。

您的任务是为给定的添加和删除序列计算对表的虚拟调用的总数。当一个对象从表中删除时，假设没有执行虚拟调用。在执行操作之前，表是空的，也就是说，最初它不包含任何对象。

输入格式

第一行输入包含三个整数hh， mm和nn (1≤m<h1 \leq m<h)，以空格分隔，其中hh是哈希表的大小，mm是用于解决冲突的数字，nn是操作的数量。

以下nn行包含操作说明。它们的执行顺序与它们在输入文件中出现的顺序相对应。每个操作由一行描述。操作说明如下:

  • "+ id哈希"这是向表中添加对象的操作格式。第一个字符是“+”(ASCII 43)，后跟一个空格，然后是对象标识符idid (0≤id≤109)(0\leq id \leq 10^{9})，然后是另一个空格，以及给定对象的哈希值hashhash (0≤hash<h)(0 \leq hash < h)。对象标识符和该对象的哈希值为整数。

  • "- id"从表中删除对象的操作格式。第一个字符是"-" (ASCII 45)，后跟一个空格，然后是对象标识符idid (0≤id≤109)(0\leq id \leq10^{9})。对象标识符为整数。

可以保证对于所有的加法操作，idid的值是唯一的。它还保证初始数据是正确的，也就是说，总是可以向哈希表中添加对象，并且不会删除不存在的对象。

获得2020分的输入限制是:

  • 1≤n≤5000 1 \leq n \leq 5000

  • 1≤n≤5000 1 \leq n \leq 5000

获得5050分的输入限制是:

  • 1≤h≤2⋅104 1 \leq h \leq 2·10^{4}

  • 1≤n≤2⋅104 1 \leq n \leq 2·10^{4}

获得100100分的输入限制为:

  • 1≤h≤2⋅105 1 \leq h \leq 2·10^{5}

  • 1≤n≤2⋅105 1 \leq n \leq 2·10^{5}

输出格式

打印单个数字-对哈希表的虚拟调用的总数。

请不要使用%lld说明符在С++中读写6464位整数。最好使用cin、cout流和%I64d说明符。

样例 #1

样例输入 #1

10 2 7
+ 11 0
+ 22 2
+ 33 6
+ 44 0
+ 55 0
- 22
+ 66 0

样例输出 #1

7

样例 #2

样例输入 #2

5 1 6
+ 123 0
+ 234 1
+ 345 2
- 234
+ 456 0
+ 567 0

样例输出 #2

4

源码：

# 智能海狸和解决碰撞



## 题目描述



来自ABBYY的聪明海狸有很多爱好。其中之一就是构造高效的哈希表。哈希表中最严重的问题之一是解决冲突。海狸对这个问题很感兴趣，他决定详细研究一下。



我们假设哈希表包含$ h $单元格，编号从$ 0 $到$ h-1 $。对象被添加到和从中移除。每个对象都有自己唯一的标识符。此外，每个对象都有一个相应的哈希值——一个介于$ 0 $和$ h-1 $之间的整数，包括$ 0 $。当一个对象被添加到表中时，如果该对象的哈希值对应的单元格是空闲的，那么这个对象就会被添加到表中。如果单元格已被另一个对象占用，则会发生碰撞。当一个对象从表中删除时，它所占用的单元格变为空。



智能海狸最近学会了线性探测解决碰撞的方法。具体情况如下。假设添加的对象的哈希值等于$ t $，并且表的单元格$ t $已经被占用。然后我们尝试将这个对象添加到单元格$ (t+m) mod\quad h $。如果它也被占用，那么我们尝试单元格$ (t+2·m) mod\quad h $，然后单元格$ (t+3·m) mod \quad h $，以此类推。注意，在某些情况下，可能无法将新对象添加到表中。可以保证这个问题的输入不包含这种情况。



运算$ a \quad mod\quad b $意味着取数$ a $除以数$ b $的余数。



海狸立刻觉得这种技术很不理想，于是他决定评估一下它的低效率。因此，给您一个操作序列，每个操作要么向表中添加一个对象，要么从表中删除一个对象。在添加新对象时，将执行对表的一系列调用。对已占用单元的调用称为dummy。换句话说，如果上面描述的算法的结果是对象被添加到单元格$ (t+i·m) mod \quad h $ $ (i\geq 0) $ $，那么正好执行了$ i $ 虚拟调用。



您的任务是为给定的添加和删除序列计算对表的虚拟调用的总数。当一个对象从表中删除时，假设没有执行虚拟调用。在执行操作之前，表是空的，也就是说，最初它不包含任何对象。



## 输入格式



第一行输入包含三个整数$ h $， $ m $和$ n $ ($ 1 \leq m<h $)，以空格分隔，其中$ h $是哈希表的大小，$ m $是用于解决冲突的数字，$ n $是操作的数量。



以下$ n $行包含操作说明。它们的执行顺序与它们在输入文件中出现的顺序相对应。每个操作由一行描述。操作说明如下:



- "+ id哈希"这是向表中添加对象的操作格式。第一个字符是“+”(ASCII 43)，后跟一个空格，然后是对象标识符$ id $ $ (0\leq id \leq 10^{9}) $，然后是另一个空格，以及给定对象的哈希值$ hash $ $ (0 \leq hash < h) $。对象标识符和该对象的哈希值为整数。

- "- id"从表中删除对象的操作格式。第一个字符是"-" (ASCII 45)，后跟一个空格，然后是对象标识符$ id $ $ (0\leq id  \leq10^{9}) $。对象标识符为整数。



可以保证对于所有的加法操作，$ id $的值是唯一的。它还保证初始数据是正确的，也就是说，总是可以向哈希表中添加对象，并且不会删除不存在的对象。



获得$20$分的输入限制是:



- $ 1 \leq n \leq 5000$

- $ 1 \leq n \leq 5000$



获得$50$分的输入限制是:



- $ 1 \leq h \leq 2·10^{4}$

- $ 1 \leq n \leq 2·10^{4}$



获得$100$分的输入限制为:



- $ 1 \leq h \leq 2·10^{5}$

- $ 1 \leq n \leq 2·10^{5}$



## 输出格式



打印单个数字-对哈希表的虚拟调用的总数。

请不要使用`%lld`说明符在С++中读写$64$位整数。最好使用`cin`、`cout`流和`%I64d`说明符。

## 样例 #1
### 样例输入 #1

10 2 7

+ 11 0

+ 22 2

+ 33 6

+ 44 0

+ 55 0

- 22

+ 66 0

### 样例输出 #1

7

## 样例 #2
### 样例输入 #2

5 1 6 + 123 0

+ 234 1

+ 345 2

- 234

+ 456 0

+ 567 0

### 样例输出 #2

4

2024/1/6 14:53