信息学奥赛一本通 1463：门票

【题目链接】

ybt 1463：门票

【题目考点】

1. 哈希表

相关知识见：【模板：哈希表】信息学奥赛一本通 1456：【例题2】图书管理

【解题思路】

解法1：链地址法实现哈希表

数据范围限制为65536 K B 65536KB65536KB。
哈希表中最多可能保存2 ∗ 10 6 2*10^62∗106个元素，平均每个元素占用内存65536 ∗ 1024 / ( 2 ∗ 10 6 ) ≈ 33 B 65536*1024/(2*10^6)\approx 33B65536∗1024/(2∗106)≈33B。
使用STL中的unordered_set类，内存开销比较大，当存储元素个数达到2 ∗ 10 6 2*10^62∗106时，容易发生内存超限。
因此本题必须手动实现哈希表。
开放地址法对内存空间需求较大，需要保证负载因子较小（一般为0.7）才可以降低哈希冲突的概率，因此表长会比存储的元素数量更大，有很多空间不能保存数据，对空间需求较高。
而链地址法的负载因子可以大于1，对内存空间需求相对较小，较为灵活。
参考【模板：哈希表】信息学奥赛一本通 1456：【例题2】图书管理中解法2可以以链地址法实现哈希表。
可以选择将哈希表写成类，或只是声明全局数组和函数来实现。

本题给定了初值a 0 = 1 a_0=1a0​=1，以及递推公式( A ⋅ a i + a i m o d B ) m o d C (A\cdot a_i+a_i\bmod B)\bmod C(A⋅ai​+ai​modB)modC，想要求出第一次出现重复项的编号。即当求出的值为a i a_iai​时，如果a i a_iai​在先前已经出现过，就输出i ii。
如果答案超过2 ∗ 10 6 2*10^62∗106，就输出-1。
我们可以根据a aa序列的初始值和递推式，依次递推求出a aa序列的每一项，设其中的一项为d dd。注意A ⋅ a i A\cdot a_iA⋅ai​这一步要在long long类型下进行计算。
当求出a i = d a_i=dai​=d时，首先在哈希表中查找是否存在d dd，

• 如果哈希表中存在d dd，则输出i ii，结束程序。
• 如果哈希表中不存在d dd，则将d dd插入哈希表。

循环次数为2 ∗ 10 6 2*10^62∗106，如果跳出了循环，则输出-1。

【题解代码】

解法1：链地址法实现哈希表

• 写法1：写全局数组和函数实现哈希表，链表中结点地址为int类型

#include<iostream>#include<algorithm>usingnamespacestd;#defineN2000003structNode{intval;intnext;}node[N];intp,data[N];//data[i]：哈希值为i的单链表的第一个结点的地址intHash(intkey){returnkey%N;}voidinsert(intkey){inth=Hash(key),np=++p;node[np].val=key;node[np].next=data[h];data[h]=np;}intcount(intkey){inth=Hash(key);for(inti=data[h];i!=0;i=node[i].next)if(node[i].val==key)return1;return0;}intmain(){inta,b,c,d=1;cin>>a>>b>>c;insert(d);for(inti=1;i<=2000000;++i){d=((longlong)a*d+d%b)%c;if(count(d)==1){cout<<i;return0;}elseinsert(d);}cout<<-1;return0;}

• 写法2：实现HashSet类，链表中结点地址为Node*类型

#include<bits/stdc++.h>usingnamespacestd;#defineN2000003structHash{unsignedoperator()(intkey){returnkey%N;}};template<classT,classHashFunc>structHashSet//开散列{structNode{T key;Node*next=nullptr;}node[N],*p=node,*data[N]={};HashFunc hash;voidinsert(T key){//头插法if(count(key)==1)//如果哈希表中已经存在key，则不插入return;inth=hash(key);Node*np=++p;np->key=key;;np->next=data[h];data[h]=np;}intcount(T key)//获取关键字key的个数{inth=hash(key);for(Node*i=data[h];i!=nullptr;i=i->next)if(i->key==key)return1;return0;}};HashSet<int,Hash>hs;intmain(){inta,b,c,d=1;cin>>a>>b>>c;hs.insert(d);for(inti=1;i<=2000000;++i){d=((longlong)a*d+d%b)%c;if(hs.count(d)==1){cout<<i;return0;}elsehs.insert(d);}cout<<-1;return0;}