P2058 海港 题解

博客园同步

原题链接

简要题意：

有 $n$ 艘船先后入港，时间为 $t_i$（以 $s$ 作单位）.每艘船上有 $k_i$ 个乘客，他们有各自的国籍 $x_{i,j}$。你需要统计 在每搜船只入港为止的一天（ $86400s$）时间所有乘客有多少不同的国籍。

$1 \leq n,x_{i,j} \leq 10^5 , 1 \leq \sum_{i=1}^n k_i \leq 3 \times 10^5 , 1 \leq t_i \leq 10^9$

$t_i$ 从小到大给出。

100000个国家可海星

算法一

考虑一个简单模拟。

对于每艘船，往前搜索 $86400s$，将这个时间段内的国籍用哈希统计一遍。

时间复杂度： $\mathcal{O}(n^2 + g^2)$ 的。其中 $g = \sum k_i$.

实际得分： $70pts$.

算法二

如何优化？

考虑，已经统计过的船只会被算法一重复统计很多次。设法优化？

你会发现 当前答案的决策性是连续的，即当前还在决策范围内的船只。

当然我们不求极值，不用单调队列。

但我们可以用队列来维护 当前 $[t_i - 86400 , t_i]$ 中所有的船只。

入队时更新哈希值，出队时把哈希值减去。

如何更新答案？

如果原哈希值为 $0$，入队时答案 $+1$ 即可；

如果哈希值为 $1$，出队时答案 $-1$ 即可。

这是 哈希统计种类 的常见方法。

时间复杂度： $\mathcal{O}(n + k)$.

实际得分： $100pts$.

#include<bits/stdc++.h>
using namespace std;int n,k,p;
int h[300001]; 
queue<int>city,tim; //city 维护国籍，tim 维护时间
int ans=0;inline int read(){char ch=getchar();while(ch<'0' || ch>'9') ch=getchar();int x=0;while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();return x;}int main(){n=read();while(n--){k=read(),p=read();for(int i=1;i<=p;i++){int t=read();h[t]++; if(h[t]==1) ans++; //加了之后只有 1 个说明多了 1 种city.push(t),tim.push(k);}while(tim.front()+86400<=k){ //不在决策范围，出队h[city.front()]--;if(!h[city.front()]) ans--; //更新哈希值和答案city.pop(),tim.pop();}printf("%d\n",ans);}return 0;
}