NOIP2016 普及组 T3
题目描述
小 K 是一个海港的海关工作人员，每天都有许多船只到达海港，船上通常有很多来自不同国家的乘客。
小 K 对这些到达海港的船只非常感兴趣，他按照时间记录下了到达海港的每一艘船只情况；对于第 i 艘到达的船，他记录了这艘船到达的时间 t
i
(单位：秒)，船上的乘客数 k
i
，以及每名乘客的国籍 x
i,1
,x
i,2
,…,x
i,k
。
小K统计了 n 艘船的信息，希望你帮忙计算出以每一艘船到达时间为止的 24 小时（24 小时 =86400 秒）内所有乘船到达的乘客来自多少个不同的国家。
形式化地讲，你需要计算 n 条信息。对于输出的第 i 条信息，你需要统计满足 t
i
−86400<t
p
≤t
i
的船只 p，在所有的 x
p,j
中，总共有多少个不同的数。
输入格式
第一行输入一个正整数 n，表示小 K 统计了 n 艘船的信息。
接下来 n 行，每行描述一艘船的信息：前两个整数 t
i
和 k
i
分别表示这艘船到达海港的时间和船上的乘客数量，接下来 k
i
个整数 x
i,j
表示船上乘客的国籍。
保证输入的 t
i
是递增的，单位是秒；表示从小K第一次上班开始计时，这艘船在第 t
i
秒到达海港。
保证 1≤n≤10
5
，∑k
i
≤3×10
5
，1≤x
i,j
≤10
5
， 1≤t
i−1
≤t
i
≤10
9
。
其中 ∑k
i
表示所有的 k
i
的和。
输出格式
输出 n 行，第 i 行输出一个整数表示第 i 艘船到达后的统计信息。
输入输出样例
输入 #1复制
3
1 4 4 1 2 2
2 2 2 3
10 1 3
输出 #1复制
3
4
4
输入 #2复制
4
1 4 1 2 2 3
3 2 2 3
86401 2 3 4
86402 1 5
输出 #2复制
3
3
3
4
说明/提示
【样例解释 1】
第一艘船在第 1 秒到达海港，最近 24 小时到达的船是第一艘船，共有 4 个乘客，分别是来自国家 4,1,2,2，共来自 3 个不同的国家；
第二艘船在第 2 秒到达海港，最近 24 小时到达的船是第一艘船和第二艘船，共有 4+2=6 个乘客，分别是来自国家 4,1,2,2,2,3，共来自 4 个不同的国家；
第三艘船在第 10 秒到达海港，最近 24 小时到达的船是第一艘船、第二艘船和第三艘船，共有 4+2+1=7 个乘客，分别是来自国家 4,1,2,2,2,3,3，共来自 4 个不同的国家。
【样例解释 2】
第一艘船在第 1 秒到达海港，最近 24 小时到达的船是第一艘船，共有 4 个乘客，分别是来自国家 1,2,2,3，共来自 3 个不同的国家。
第二艘船在第 3 秒到达海港，最近 24 小时到达的船是第一艘船和第二艘船，共有 4+2=6 个乘客，分别是来自国家 1,2,2,3,2,3，共来自 3 个不同的国家。
第三艘船在第 86401 秒到达海港，最近 24 小时到达的船是第二艘船和第三艘船，共有 2+2=4 个乘客，分别是来自国家 2,3,3,4，共来自 3 个不同的国家。
第四艘船在第 86402 秒到达海港，最近 24 小时到达的船是第二艘船、第三艘船和第四艘船，共有 2+2+1=5 个乘客，分别是来自国家 2,3,3,4,5，共来自 4个 不同的国家。
【数据范围】
对于 10% 的测试点，n=1,∑k
i
≤10,1≤x
i,j
≤10,1≤t
i
≤10。
对于 20% 的测试点，1≤n≤10,∑k
i
≤100,1≤x
i,j
≤100,1≤t
i
≤32767。
对于 40% 的测试点，1≤n≤100,∑k
i
≤100,1≤x
i,j
≤100,1≤t
i
≤86400。
对于 70% 的测试点，1≤n≤1000,∑k
i
≤3000,1≤x
i,j
≤1000,1≤t
i
≤10
9
。
对于 100% 的测试点，1≤n≤10
5
,∑k
i
≤3×10
5
,1≤x
i,j
≤10
5
,1≤t
i
≤10
9
拿到这道题首先会发现题目壁话很多，建议先多读两遍！
拿到题发现不就是统计国籍数吗？一个哈希表直接解决！但他有个要求说必须是在24h（86400秒）内的
船只，所以可以尝试维护一个86400的窗口，每次输出窗口内的国籍数就解决了（哈希表来解决）！
但是滑动窗口有一个前提就是必须要有单调性，所以需要给时间排个序，巧的时题目正好说时间递增给出所以不用我们多次一举。
typedef struct {
int t;
int k;
int nation[300010];
}data;
void sliding_window(data*d,int n){
int ans=0;
int hash[300010]={0};
for(int right=0,left=0;right<n;right++){
//维护时间查为86400的窗口
while(d[right].t-d[left].t>86400){
for(int j=0;j<d[left].k;j++){
hash[d[left].nation[j]]--;
if(hash[d[left].nation[j]]==0)ans--;
}
left++;
}
for(int j=0;j<d[right].k;j++){
hash[d[right].nation[j]]++;
if(hash[d[right].nation[j]]==1)ans++;
}
printf("%d",ans);
}
}
int main(){
int n;
scanf(“%d”,&n);
data d[100010];
for(int i=0;i<n;i++){
scanf("%d %d",&d[i].t,&d[i].k);
for(int j=0;j<d[i].k;j++){
scanf("%d",d[i].nation[j]);
}
}
sliding_window(d,n);
return 0;
}
单独解释一下这里ans的作用，ans就是国籍数量，如果你发现left右移出窗口后，将该船只的国籍吐出后对应的有国籍==0
ans就–
right右移时有国籍的数量刚好为1就++
交了这个代码发先MLE了，发现应该动态分配nation数组
最终优化版
typedef struct {
int t;
int k;
int *nation; // 改为指针
} Data;
void sliding_window(Data d, int n) {
int ans = 0;
int hash = (int *)calloc(100010, sizeof(int)); // 国籍哈希表
int left = 0;
for (int right = 0; right < n; right++) {
// 维护时间窗口：移除超出86400秒的船
while (d[right].t - d[left].t >= 86400) {
for (int j = 0; j < d[left].k; j++) {
int nation = d[left].nation[j];
hash[nation]--;
if (hash[nation] == 0) {
ans--;
}
}
left++;
}
// 添加当前船的乘客
for (int j = 0; j < d[right].k; j++) {
int nation = d[right].nation[j];
if (hash[nation] == 0) {
ans++;
}
hash[nation]++;
}
printf("%d\n", ans);
}
}
int main() {
int n;
scanf(“%d”, &n);
Data *d = (Data *)malloc(n * sizeof(Data));
for (int i = 0; i < n; i++) {
scanf("%d %d", &d[i].t, &d[i].k);
d[i].nation = (int *)malloc(d[i].k * sizeof(int)); // 动态分配
for (int j = 0; j < d[i].k; j++) {
scanf("%d", &d[i].nation[j]);
}
}
sliding_window(d, n);
return 0;
}
