牛客练习赛50 B tokitsukaze and Hash Table 并查集

链接https://ac.nowcoder.com/acm/contest/1080/B来源牛客网题目描述tokitsukaze有n个数需要按顺序把他们插入哈希表中哈希表的位置为0到n-1。插入的规则是刚开始哈希表是空的。对于一个数x在哈希表中如果(x mod n)的位置是空的就把x放在(x mod n)的位置上。如果不是空的就从(x mod n)往右开始找到第一个空的位置插入。若一直到n-1都不是空的就从位置0开始继续往右找第一个空的位置插入。因为哈希表总共有n个空位需要插入n个数所以每个数都能被插入。现在tokitsukaze想知道把这n个数按顺序插入哈希表后哈希表中的每个位置分别对应的是哪个数。输入描述:第一行包含一个正整数n(1≤n≤10^6)。 第二行包含n个非负整数x(0≤x≤10^9)这些数按从左到右的顺序依次插入哈希表。输出描述:输出一行n个数第i个数表示哈希表中位置为i所对应的数。(0≤i≤n-1)示例1输入4 1 2 6 5输出5 1 2 6说明插入1时1 mod 41是空的在位置1插入。 插入2时2 mod 42是空的在位置2插入。 插入6时6 mod 42不是空的找到下一个空的位置为3所以在位置3插入。 插入5时5 mod 41不是空的找到下一个空的位置为0所以在位置0插入。示例2输入4 3 0 7 11输出0 7 11 3说明插入3时3 mod 43是空的在位置3插入。 插入0时0 mod 40是空的在位置0插入。 插入7时7 mod 43不是空的找到下一个空的位置为1所以在位置1插入。 插入11时11 mod 43不是空的找到下一个空的位置为2所以在位置2插入。题解解法一用并查集维护空位。在位置x插入一个数后合并x和(x1)%n即可。要注意合并的时候(x1)%n必须当爹才能达到维护的效果。解法二用set维护所有空位每次lower_bound找到第一个可用空位即可。(可能会卡常)我用set写的代码连续交了5发有一发超时set的时间是并查集的两三倍。下边给出两种代码并查集代码#includebits/stdc.h using namespace std; typedef long long ll; const int maxn1e65; int father[maxn]; int ans[maxn]; int get(int x){ return xfather[x]?x:father[x]get(father[x]); } int main(){ int n; scanf(%d,n); for(int i1;in;i) father[i]i; for(int i1;in;i){ int x; scanf(%d,x); int yx%n; int fget(y); ans[f]x; int zget((f1)%n); father[f]z; } for(int i0;in;i) printf(%d ,ans[i]); return 0; }set代码#includebits/stdc.h using namespace std; typedef long long ll; const int maxn1e65; int a[maxn]; setint s; setint::iterator it; int main(){ int n; scanf(%d,n); for(int i0;in;i) s.insert(i); for(int i0;in;i){ int x; scanf(%d,x); int yx%n; its.lower_bound(y); if(its.end()) its.begin(); a[*it]x; s.erase(it); } for(int i0;in;i) printf(%d ,a[i]); return 0; }