华师一附中OI组

标题: P2058 海港 [打印本页]

作者: 倚窗倾听风吹雨 时间: 2018-8-24 09:22
标题: P2058 海港
https://www.luogu.org/problemnew/show/P2058

题目描述
小K是一个海港的海关工作人员，每天都有许多船只到达海港，船上通常有很多来自不同国家的乘客。

小K对这些到达海港的船只非常感兴趣，他按照时间记录下了到达海港的每一艘船只情况；对于第i艘到达的船，他记录了这艘船到达的时间ti (单位：秒)，船上的乘客数 k_i  ，以及每名乘客的国籍x
i,1 ,xi,2，xi,k
      。

小K统计了 n 艘船的信息，希望你帮忙计算出以每一艘船到达时间为止的 24小时( 24 小时= 86400 秒）内所有乘船到达的乘客来自多少个不同的国家。

形式化地讲，你需要计算 n 条信息。对于输出的第 i 条信息，你需要统计满足ti−86400<tp ≤ti  的船只 p ，在所有的 xp,j  中，总共有多少个不同的数。

输入输出格式
输入格式：
第一行输入一个正整数 n ，表示小K统计了n 艘船的信息。

接下来 n 行，每行描述一艘船的信息：前两个整数 t_i  和 k_i  分别表示这艘船到达海港的时间和船上的乘客数量，接下来 k_i  个整数x i,j表示船上乘客的国籍。

保证输入的 t_i  是递增的，单位是秒；表示从小K第一次上班开始计时，这艘船在第 t_i  秒到达海港。

保证 1≤n≤10  ∑ki≤3∗10 1≤x(i,j)≤10 1≤t(i−1)≤ti≤10

  其中 ∑ki 表示所有的 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=74+2+1=7 个乘客，分别是来自国家 4,1,2,2,2,3,3 ，共来自4个不同的国家。

【样例解释2】

第一艘船在第 11 秒到达海港，最近 2424 小时到达的船是第一艘船，共有 44 个乘客，分别是来自国家 1,2,2,32,3 ，共来自 3 个不同的国家。

第二艘船在第 33 秒到达海港，最近 2424 小时到达的船是第一艘船和第二艘船，共有 4+2=64+2=6 个乘客，分别是来自国家 1,2,2,3,2,3 ，共来自 3 个不同的国家。

第三艘船在第 86401 秒到达海港，最近 2424 小时到达的船是第二艘船和第三艘船，共有 2+2=42+2=4 个乘客，分别是来自国家 2,3,3,42,3,3,4 ，共来自 3个不同的国家。

第四艘船在第 86402 秒到达海港，最近 24 小时到达的船是第二艘船、第三艘船和第四艘船，共有 2+2+1=5 个乘客，分别是来自国家 2,3,3,4,5，共来自 4 个不同的国家。

【数据范围】

作者: 倚窗倾听风吹雨 时间: 2018-8-24 09:25
一开始存船的信息空间太大存不下，只有70分；

#include<iostream>
using namespace std;
int n,k,c,pi;
bool ans[1010];
struct node
{
int t,k;
bool con[1010];
}s[1010];
int main()
{
cin>>n;
for(int i=1;i<=1000;i++)
s[i].con[i]=0;
for(int i=1;i<=n;i++)
{
cin>>s[i].t;
cin>>k;
for(int j=1;j<=k;j++)
{
cin>>c;
s[i].con[c]=1;
}
}
for(int i=1;i<=n;i++)
{
pi=0;
for(int j=1;j<=1000;j++)
ans[j]=0;
for(int j=1;j<=i;j++)
if(s[i].t-s[j].t<86400)
for(int l=1;l<=1000;l++)
if(s[j].con[l])ans[l]=1;
for(int j=1;j<=1000;j++)
if(ans[j])pi++;
cout<<pi<<endl;
}
}

复制代码

后来发现数据范围可以存人的信息，AC

#include<iostream>
#include<queue>
using namespace std;
int n,ti,r,k,m=1,con[100010],ans;
struct node
{
int t,c;
}p[300010];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>ti>>k;
while(k--)
{
cin>>p[++r].c;
p[r].t=ti;
if(!con[p[r].c])ans++;
con[p[r].c]++;
}
while(m<=r && ti-p[m].t>=86400)
{
con[p[m].c]--;
if(!con[p[m].c])ans--;
m++;
}
cout<<ans<<endl;
}
}

复制代码

作者: admin 时间: 2019-11-6 17:18
这其实是一个的统计题目，前面40%的数据直接开一个大数组，记录每个的国籍的人的数量，来一个加一个，还不用减，然后统计非0数的数量输出，代码如下：

#include <iostream>
using namespace std;
const int mn=1010;
const int mk=3030;
int n,t[mn],k[mn],x[mn][mk];
int s[mk]; ///记录每个国籍的人有多少个
int i,j,ans;
int main()
{
cin>>n;
for (i=1; i<=n; i++)
{
cin>>t[i]>>k[i];
for (j=1; j<=k[i]; j++) cin>>x[i][j];
}
for(i=1; i<=n; i++)
{
for (j=1; j<=k[i]; j++) ///枚举所有人
s[x[i][j]]++;///对应的国家人数加一
for (ans=0,j=1; j<=mk-1; j++) if (s[j]>0) ans++;
cout<<ans<<endl;
}
}

复制代码

交上去果然得到40分。

作者: admin 时间: 2019-11-6 17:28
70%的数据有时间超过86400秒的问题，那么我们保存下来的那些在86400秒之前的数据减掉，然后输出就是，这个可以用双指针法，i是后指针指着当前的位置，m是前指针，指着前面第一个符合条件的位置。加上这么一段：

while (t[i]-t[m]>=86400) ///前面超过时间的人
{
for (j=1; j<=k[m]; j++) ///枚举所有人
s[x[m][j]]--;///对应的国家人数减
m++;///下一次从这里开始统计
}

复制代码

注意m的初值是0，交上去果然得到70分。

作者: admin 时间: 2019-11-6 17:40
100%的数据需要更大的空间，改const int mn=100010;const int mk=300030;发现程序爆内存了。too large for field，于是想在数据读入的时候不要一个人一个人的处理，将所有的国籍的人一起合并记下来，删除的时候也一次删除，但是发现还是要开很大的数组，搞不定，于是想使用vector试试。

欢迎光临华师一附中OI组 (http://hsyit.cn/)