题目链接：点击打开链接
题目大意：略。
解题思路：平方探测法处理哈希表，但是该题只能正增长：with positive increments only。即，hi=(h(key)+i*i)%m （0 ≤ i ≤ m-1），注意：类似样例中“15”是插入不进的这种数，理论上应该是 [0,size-1] == size 次，但是这里还要额外 +1 次，因为这 1 次是出于 di==size 时的探测才知道是否进入循环了，所以该次也要算进去。
AC 代码
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a) #define ssclr(ss) ss.clear(), ss.str("") #define INF 0x3f3f3f3f #define MOD 1000000007 using namespace std; typedef long long ll; const int maxn=1e4+10; int vis[maxn], times[maxn*10]; int isPrime(int x) { if(x<2) return 0; for(int i=2;i<=sqrt(x);i++) if(x%i==0) return 0; return 1; } int main() { int p,n,q,a; scanf("%d%d%d",&p,&n,&q); while(!isPrime(p)) p++; for(int i=0;i<n;i++) { scanf("%d",&a); int cnt=1; for(int j=0;j<p;j++) { int idx=(j*j+a)%p; if(vis[idx]==0) { vis[idx]=a; break; } cnt++; } times[a]=cnt; if(cnt==p+1) printf("%d cannot be inserted.\n",a); } double sum=0; for(int i=0;i<q;i++) { scanf("%d",&a); if(times[a]==0) { int cnt=1; for(int j=0;j<p;j++) { int idx=(j*j+a)%p; if(vis[idx]==0) { //vis[idx]=a; // 这里不能给它放上位置，会影响后面的数据到该位置时，误以为原本就有数据，则继续探测，影响结果 break; } cnt++; } times[a]=cnt; } sum+=times[a]; } printf("%.1f\n",sum/q); return 0; }
