← 返回比赛

已结束 GESP春节巅峰赛#17

← 上一题下一题 →

A4737 | $线性探查法$

来源官方 / 2025

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

给定一个大小为 $N$ 的哈希表，并定义以下哈希函数： $$ H(X) = X \mathbin{\mathrm{mod}} N $$ 这里，$X \mathbin{\mathrm{mod}} N$ 表示 $X$ 除以 $N$ 后的余数。 接下来给出 $Q$ 个查询，对于每个查询 $i$，若 $X_i$ 已在哈希表中，请你输出其在哈希表中的位置；否则将其插入哈希表，再输出其插入的位置。 我们使用线性探查法解决哈希冲突，即对于要插入的元素 $X$，若 $H(X)$ 已经存在其他元素，则依次检查 $H(X + 1), H(X + 2), H(X + 3), \cdots$ 直至找到内容为空的单元。 $\large{数据范围}$ - $1 \le Q \le N \le 10^5$ - $1 \le X_i \le 10^{12}$

输入格式

对于每个测试文件，格式如下： $\tt{N\ Q}$ $\tt{X_1}$ $\tt{X_2}$ $\tt{\vdots}$ $\tt{X_Q}$

输出格式

对于每个查询 $i$，若 $X_i$ 已在哈希表中，输出其位置，否则将其插入到哈希表，并输出插入的位置。

输入输出样例

输入 #1

输出 #1

$\bf{样例\ 1：}$ $X_1 = 13$，$H(13) = 13 \mathbin{\mathrm{mod}} 5 = 3$，所以将 $13$ 插入表中位置 $3$ 处；此时表中元素： 0123413 $X_2 = 28$，$H(28) = 28 \mathbin{\mathrm{mod}} 5 = 3$，但是 $3$ 处已有元素 $13$，所以继续尝试 $H(29) = 29 \mathbin{\mathrm{mod}} 5 = 4$，将 $28$ 插入表中位置 $4$ 处；此时表中元素： 012341328 $X_3 = 52$，$H(52) = 52 \mathbin{\mathrm{mod}} 5 = 2$，将 $52$ 插入表中位置 $2$ 处；此时表中元素： 01234521328 $X_4 = 2$，$H(2) = 2 \mathbin{\mathrm{mod}} 5 = 2$，但是 $2$ 处已有元素 $52$，继续尝试 $H(2 + 1) = 3, H(2 + 2) = 4, H(2 + 3) = 0$，将 $2$ 插入表中位置 $0$ 处；此时表中元素： 012342521328 $X_5 = 100$，$H(100) = 100 \mathbin{\mathrm{mod}} 5 = 0$，但是 $0$ 处已有元素 $52$，继续尝试 $H(100 + 1) = 1$，将 $100$ 插入表中位置 $1$ 处；此时表中元素： 012342100521328

C++ 编辑器

输入

输出