题解 P2058 【海港】
STLGirlfriend
2018-08-06 19:31:31
为什么我不用队列都一次过，明明很简单，按题意模拟就行了呀 QAQ~
只要维护一个 `std::unordered_map<int, int>`，对于每一艘船，判断是否有船只到达时间超过 $24$ 小时，如果有就把当前船上的所有乘客的国籍从 `std::unordered_map<int, int>` 中删除，然后再统计当前到达的船上乘客的国籍，最后输出 `std::unordered_map<int, int>` 的大小，就 A 了呀 QWQ~
PS：因为数据太大，$x_{i, j}$ 要动态分配内存。
下面是萌萌哒代码（用了 `fread` 快读，事实上并不需要）：
```c++
#include <cstdio>
#include <cctype>
#include <unordered_map>
const int MaxN = 1e5;
const int Limit = 1e5;
const int DaySec = 86400;
char next() {
static const size_t BufSize = 1 << 17;
static char *fs, *ft, buf[BufSize];
if (fs == ft) {
ft = (fs = buf) + fread(buf, 1, BufSize, stdin);
if (fs == ft) return EOF;
}
return *fs++;
}
int nextInt() {
int x = 0;
char c;
while (!isdigit(c = next()));
while (isdigit(c)) { x = x * 10 + c - '0'; c = next(); }
return x;
}
int main() {
int n;
n = nextInt();
static int t[MaxN + 1], k[MaxN + 1];
static int *x[MaxN + 1];
for (int i = 1; i <= n; ++i) {
t[i] = nextInt();
k[i] = nextInt();
x[i] = new int[ k[i] ];
for (int j = 0; j < k[i]; ++j) x[i][j] = nextInt();
}
int p = 1;
std::unordered_map<int, int> cnt;
for (int i = 1; i <= n; ++i) {
while (!(t[i] - DaySec < t[p])) {
for (int j = 0; j < k[p]; ++j) if (--cnt[ x[p][j] ] == 0) cnt.erase(x[p][j]);
++p;
}
for (int j = 0; j < k[i]; ++j) ++cnt[ x[i][j] ];
printf("%d\n", cnt.size());
}
}
```