题解

这道题可以用队列，我们可以在队列里保存国籍和时间，因为这道题没有让我们统计某国籍人的人数。

代码很好理解，还是看注释吧：

#include <bits/stdc++.h>
using namespace std;
int n, t, k, x, cnt[100005], ans; // cnt表示当前1天内的统计信息
queue<int> qx, qt; // qx表示国籍 qt表示时间
int main()
{
    scanf("%d", &n);
    while (n--)
    {
        scanf("%d%d", &t, &k);
        while (k--)
        {
            scanf("%d", &x);
            // 给它塞进去
            qx.push(x);
            qt.push(t);
            cnt[x]++;
            if (cnt[x] == 1) ans++; // 新来的一种国籍，ans++
        }
        while (!qx.empty() && qt.front() <= t - 86400) // 如果非空且第一个超时了
        {
            // 给他扔出去
            cnt[qx.front()]--;
            if (cnt[qx.front()] == 0) ans--; // 这个国籍的人全删光了，ans也--了
            qx.pop();
            qt.pop();
        }
        printf("%d\n", ans);
    }
    return 0;
}

没了？对。

$AC$ $Code$

#include <bits/stdc++.h>
using namespace std;
int n, t, k, x, cnt[100005], ans;
queue<int> qx, qt;
int main()
{
    scanf("%d", &n);
    while (n--)
    {
        scanf("%d%d", &t, &k);
        while (k--)
        {
            scanf("%d", &x);
            qx.push(x);
            qt.push(t);
            cnt[x]++;
            if (cnt[x] == 1) ans++;
        }
        while (!qx.empty() && qt.front() <= t - 86400)
        {
            cnt[qx.front()]--;
            if (cnt[qx.front()] == 0) ans--;
            qx.pop();
            qt.pop();
        }
        printf("%d\n", ans);
    }
    return 0;
}

竟然没人发题解，我来发一个。

从这句话中和容易想到队列：希望你帮忙计算出以每一艘船到达时间为止的24小时(24小时=86400秒）

用队列储存时间，时间超过24小时出队。

这题数据太大了，所以不能一个船一个船的存。

这题没给每艘船上的人数限制，但是给了国籍的总数限制，所以可以以人为单位来存。

想清楚后这题就变得十分简单了。

话不多说，代码如下：

#include <bits/stdc++.h>
using namespace std;
const int hour = 86400;
int n , ti , ki , xij , ans , flag[100005];
//flag 存24小时之内所有人的国籍数量 flag[1] == 3 表示1国家的人有3个
struct person{
	int t , x;
	//t表示时间，x表示国籍
};
queue <person> q;
//建立一个person型的队列
int main(){
	cin >> n;
	while(n--){
		cin >> ti >> ki;
		for(int i = 1; i <= ki; i++){
			cin >> xij;
			if(!flag[xij])//国家xij的人还没出现过
				ans++;//就将答案加一
			flag[xij]++;
			q.push((person){ti , xij});//把这个人加入队列里
		}
		person head = q.front();
		//head表示24小时内最先入队的人
		while(ti - head.t >= hour){//若他不在24小时之内
			flag[head.x]--;
			if(!flag[head.x])//若这个国家的人了
				ans--;//就将答案减一
			q.pop();//出队
			head = q.front();
		}
		cout << ans << '\n';
		//输出答案
	}
	return 0;//好习惯
}

这道题折磨我好久，必须发一个

#include <bits/stdc++.h>
using namespace std;
int s,i,n,t,k,r,w[100001],x[300002],y[300002];//w数组表示的是当前为这个国籍的人数，x数组表示的是当前这个人的国籍，y数组表示的是当前的时间 
int main(){
	cin>>n;
	while(n--){
		cin>>t>>k;//普通的输入输出 
		while(k--){
			y[++r]=t;
			cin>>x[r];
			if (!w[x[r]]){
				s++;//如果当前这个国籍没有人，将答案加1 
			}
			w[x[r]]++;//增加 
		}
		while(t-y[i]>=86400){//如果时间超过了 
			w[x[i]]--;//当前这个人的国籍的人的数量减1
            if(!w[x[i]]){
			    s--;
			}//如果当前这个人的国籍没人，那么答案减1 
            i++;//下一个人 
		}
		cout<<s<<endl;//输出答案 
	}
	return 0;
}