专栏文章

题解：P11615 【模板】哈希表

SSoviet_Onion
P11615题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@miqa0egi
此快照首次捕获于
2025/12/04 01:23
3 个月前
此快照最后确认于
2025/12/04 01:23
3 个月前
查看原文

P11615 【模板】哈希表

暴力思路

第一眼看到题面，立刻使用了 STL 中的 map 按题意进行映射。代码实现非常简单。时间复杂度约为 O(Nlog⁡N)O(N\log N)，有较大常数。
CPP
#include<iostream>
#include<unordered_map>
#define ll unsigned long long
using namespace std;
unordered_map<ll,ll>m;
int n;
ll x,y,ans;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%llu%llu",&x,&y);
		ans+=i*m[x];
		m[x]=y;
	}
	printf("%llu\n",ans);
	return 0;
}
结果也一样简洁明了：鲜艳的 TLE。

优化

可以使用另一种映射 unordered_map，可以减小常数。
但是结果一样，仍然超时。

正解：在线哈希表

哈希表，就是对于上述思路的优化。题目中给定的 xx 在 [0,264)[0,2^{64}) 内，范围非常大。哈希就像离散化，将 [0,264)[0,2^{64}) 范围的数通过哈希函数 H(x)=x mod PH(x)=x \bmod P 映射到一个较小的范围内，比如 10610^6。其中 PP 是一个相对较小的质数，我们取 106+310^6+3。
所以我们需要开 106+1010^6+10 个 unordered_map，对于每次询问，直接输出 mx mod P,xm_{x\bmod P,x} 的值，然后对其进行更改。可这样以大幅度节省时间。如果只是使用映射，会被出题人卡掉一个点。各位可以去看出题人题解中的详细 hack 方法。
这样的时间复杂度是 O(Nlog⁡N)O(N\log N)，但是常数较小，有时可以达到 O(1)O(1) 复杂度。
注意 PP 不要开太大，容易 MLE。
CPP
#include<iostream>
#include<unordered_map>
#define ll unsigned long long
#define getchar() (tt==ss&&(tt=(ss=In)+fread(In,1,1<<20,stdin),ss==tt)?EOF:*ss++)
using namespace std;
char In[1<<20],*ss=In,*tt=In;
const int N=1e6+10;
const int P=1e6+3;
ll read(void){ll f=1,res=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){res=res*10+(ch-'0');ch=getchar();}return res*f;}
void write(ll x){if(x<0){putchar('-');x=-x;}if(x>=10) write(x/10);putchar((x%10)+'0');return;}
unordered_map<ll,ll>m[N];
ll a,b,r,ans;
int n;
int main(){
	n=read();
	for(int i=1;i<=n;i++){
		a=read(),b=read();
		r=a%P;
		ans+=i*m[r][a];
		m[r][a]=b;
	}
	write(ans),putchar('\n');
	return 0;
}

离线做法

非常简单且跑得飞快。
先读入所有询问，然后以 xx 为第一关键字，以读入顺序为第二关键字排序。依次处理后再以读入顺序排序，就可以直接得到答案。该做法的瓶颈在于 sort 排序，所以时间复杂度是 O(Nlog⁡N)O(N\log N)。但是 sort 比较优秀，常数远远小于映射，可以跑到一秒以内。
CPP
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#define pb push_back
#define ll unsigned long long
#define getchar() (tt==ss&&(tt=(ss=In)+fread(In,1,1<<20,stdin),ss==tt)?EOF:*ss++)
using namespace std;
char In[1<<20],*ss=In,*tt=In;
const int N=5e6+10;
struct Node1{
	ll x;
	ll y;
	int id;
	friend bool operator <(const Node1 a,const Node1 b){
		if(a.x!=b.x) return a.x<b.x;
		return a.id<b.id;
	}
}a[N];
struct Node2{
	ll ans;
	int id;
	friend bool operator <(const Node2 a,const Node2 b){
		return a.id<b.id;
	}
}b[N];
int n;
ll res;
ll read(void){ll f=1,res=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){res=res*10+(ch-'0');ch=getchar();}return res*f;}
int main(){
	n=read();
	for(int i=1;i<=n;i++){
		a[i].x=read();
		a[i].y=read();
		a[i].id=i;
	}
	sort(a+1,a+n+1);
	for(int i=1;i<=n;){
		int l=i,r=i;
		while(i<=n&&a[r].x==a[l].x) r=++i;
		r--;
		for(int j=l;j<=r;j++) b[j]={(j-1<l?0ll:a[j-1].y),a[j].id};
	}
	sort(b+1,b+n+1);
	for(int i=1;i<=n;i++){
		res+=i*b[i].ans;
	}
	printf("%llu\n",res);
	return 0;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...