传统题 1000ms 256MiB

哈希冲突

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem: 哈希冲突

时间限制:1s

空间限制:256MB

Background:

​ 通常,中学中形如 y=f(x)y=f(x) 的式子为我们所熟知,被称为函数。实际上,设该函数的定义域为集合 AA ,值域为集合 BB ,则我们可称该式子为集合 AA 中元素到集合 BB 中元素的一个映射。

​ 定义“离散化”:设存在一组整数,这组整数共有 nn 个整数,而这组数据的极差为 DD 。若 D>>nD>>n (即 DD 远大于 nn ),则称这组数据的离散化程度高。反之,则称这组数据的离散化程度低。

​ 在实际应用中,时常会出现这样的情况:存在一组共有 nn 个整数的数据,尽管 nn 很小,即这一组数据的量并不大,但是这一组数据的离散化程度非常高。譬如统计某人的所有网友到他所在地的距离(单位:米),网友的数量 nn 可能并不大,但是若要统计到此人距离为 dd 的人数时,我们不能开一个大小达到 1e61e6 (即 1x1061x 10 ^6 )的数组,因为这会造成严重的空间浪费,是我们所不能接受的。这时候,我们就需要一个映射 y=f(x)y=f(x) ,使得对于每一个距离 dd ,经过映射后的值控制在 nn 附近,并且对于不同的 dd ,他们映射的值不一样。此时,这样的从原距离的集合到新的集合的映射被我们称为哈希函数。

​ 然而,最终的结果常常事与愿违。由于数据的随机性,经过哈希函数的映射后,可能会存在两个不同的距离 d1,d2d1,d2 ,使得 f(d1)=f(d2)f(d1)=f(d2) ,此时,我们称 d1,d2d1,d2 这两个数产生了哈希冲突。

​ 现在,原力清理大师对此非常感兴趣,并找了一组数据,创建了一个哈希函数做映射,以更深入地了解哈希函数的奥义。这组数据由 nn 个整数组成,每个数的范围都在 00n1n-1 之间(太大了原力清理大师怕自己做不出来 QAQQAQ )。设原数组为数组 aa ,原力清理大师希望将原来的数组通过自定义的哈希函数 ff ,按照下标从小到大的顺序,映射到另一个新的长度为 nn 的数组 bb 中,其中哈希函数 ffb[a[i]]=i(0in1)b[a[i]]=i (0\leq i\leq n-1) ,即 f(a[i])f(a[i])ii 映射到数组 bb 中的下标。很明显,由于原力清理大师的火候不够,原数组经过映射后将会产生大量的哈希冲突。原力清理大师相当恼火,希望你能告诉他会产生多少次哈希冲突,即存在多少个不同的 d1,d2d1,d2 ,使得 f(d1)=f(d2)f(d1)=f(d2) ,函数 ff 的定义见上文。同时,原力清理大师还希望你给出最终的 bb 数组,其中,数组未被赋值的位置默认为 1-1 ,产生哈希冲突的位置取两个数的平均数。最终结果均保留六位小数( 1-1 除外)。

Input Format

第一行一个整数 nn ,代表数组的长度。

第二行共 nn 个整数,代表数组中 ai(0in1)a_i (0\leq i\leq n-1) 的值 (0ain1)(0\leq a_i\leq n-1) ,未被赋值则默认为 1-1

Output Format

第一行输出一个整数,代表新数组中哈希冲突的数量。

第二行输出 nn 个数,代表经过映射后新数组中每一位的值,输出结果保留六位小数。

Input Example1:

4
1 2 0 3

Output Example1:

0
2.000000 0.000000 1.000000 3.000000

Input Example2:

4
3 1 0 1

Output Example2:

1
2.000000 2.000000 -1.000000 0.000000

Explanation:

样例一中, a[1]=0,a[2]=1,a[0]=2,a[3]=3a[1]=0,a[2]=1,a[0]=2,a[3]=3 ,不存在哈希冲突,故为 00

样例二中, a[3]=0,a[1]=1,a[0]=2,a[3]=0,a[1]=1,a[0]=2, ,又出现了 a[1]=3a[1]=3 ,产生哈希冲突,取平均得到 a[1]=2a[1]=2

对于 100100% 的数据,满足 1n1e51\leq n\leq 1e5 (含义见题目描述), 0ain10\leq a_i\leq n-1

NNU2024新生赛第二场

未参加
状态
已结束
规则
IOI
题目
10
开始于
2024-8-25 8:00
结束于
2024-8-28 8:00
持续时间
72 小时
主持人
参赛人数
139