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 个不同的国家。

【数据范围】

倚窗倾听风吹雨

一开始存船的信息空间太大存不下，只有70分；

1. #include<iostream>
   
2. using namespace std;
   
3. int n,k,c,pi;
   
4. bool ans[1010];
   
5. struct node
   
6. {
   
7.     int t,k;
   
8.     bool con[1010];
   
9. }s[1010];
   
10. int main()
    
11. {
    
12.     cin>>n;
    
13.     for(int i=1;i<=1000;i++)
    
14.         s[i].con[i]=0;
    
15.     for(int i=1;i<=n;i++)
    
16.     {
    
17.         cin>>s[i].t;
    
18.         cin>>k;
    
19.         for(int j=1;j<=k;j++)
    
20.         {
    
21.             cin>>c;
    
22.             s[i].con[c]=1;
    
23.         }
    
24.     }
    
25.     for(int i=1;i<=n;i++)
    
26.     {
    
27.         pi=0;
    
28.         for(int j=1;j<=1000;j++)
    
29.             ans[j]=0;
    
30.         for(int j=1;j<=i;j++)
    
31.             if(s[i].t-s[j].t<86400)
    
32.                 for(int l=1;l<=1000;l++)
    
33.                 if(s[j].con[l])ans[l]=1;
    
34.         for(int j=1;j<=1000;j++)
    
35.             if(ans[j])pi++;
    
36.         cout<<pi<<endl;
    
37.     }
    
38. 
    
39. }
    

复制代码

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

1. #include<iostream>
   
2. #include<queue>
   
3. using namespace std;
   
4. int n,ti,r,k,m=1,con[100010],ans;
   
5. struct node
   
6. {
   
7.     int t,c;
   
8. }p[300010];
   
9. int main()
   
10. {
    
11.     cin>>n;
    
12.     for(int i=1;i<=n;i++)
    
13.     {
    
14.         cin>>ti>>k;
    
15.         while(k--)
    
16.         {
    
17.             cin>>p[++r].c;
    
18.             p[r].t=ti;
    
19.             if(!con[p[r].c])ans++;
    
20.             con[p[r].c]++;
    
21.         }
    
22.         while(m<=r && ti-p[m].t>=86400)
    
23.         {
    
24.             con[p[m].c]--;
    
25.             if(!con[p[m].c])ans--;
    
26.             m++;
    
27.         }
    
28.         cout<<ans<<endl;
    
29.     }
    
30. }
    

复制代码

admin

这其实是一个的统计题目，前面40%的数据直接开一个大数组，记录每个的国籍的人的数量，来一个加一个，还不用减，然后统计非0数的数量输出，代码如下：

1. #include <iostream>
   
2. using namespace std;
   
3. const int mn=1010;
   
4. const int mk=3030;
   
5. int n,t[mn],k[mn],x[mn][mk];
   
6. int s[mk]; ///记录每个国籍的人有多少个
   
7. int i,j,ans;
   
8. int main()
   
9. {
   
10.         cin>>n;
    
11.         for (i=1; i<=n; i++)
    
12.         {
    
13.                 cin>>t[i]>>k[i];
    
14.                 for (j=1; j<=k[i]; j++) cin>>x[i][j];
    
15.         }
    
16.         for(i=1; i<=n; i++)
    
17.         {
    
18.                 for (j=1; j<=k[i]; j++) ///枚举所有人
    
19.                         s[x[i][j]]++;///对应的国家人数加一
    
20.                 for (ans=0,j=1; j<=mk-1; j++) if (s[j]>0) ans++;
    
21.                 cout<<ans<<endl;
    
22.         }
    
23. 
    
24. }

复制代码

交上去果然得到40分。

admin

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

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

复制代码

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

admin

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