[NOIP2016 普及組] 海港

題目背景

NOIP2016 普及組 T3

題目描述

小 K 是一個海港的海關工作人員，每天都有許多船只到達海港，船上通常有很多來自不同國家的乘客。

小 K 對這些到達海港的船只非常感興趣，他按照時間記錄下了到達海港的每一艘船只情況；對于第 $i$ 艘到達的船，他記錄了這艘船到達的時間 $t_i$ (單位：秒)，船上的乘客數 $k_i$，以及每名乘客的國籍 $x_{i,1},x_{i,2},\dots ,x_{i,k}$。

小K統計了 $n$ 艘船的信息，希望你幫忙計算出以每一艘船到達時間為止的 $24$ 小時（$24$ 小時 $=86400$ 秒）內所有乘船到達的乘客來自多少個不同的國家。

形式化地講，你需要計算 $n$ 條信息。對于輸出的第 $i$ 條信息，你需要統計滿足 $t_i?86400<t_p\le 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\le n\le 10^5$，$\sum{k_i} \le 3\times 10^5 $ ，$1\le x_{i,j}\le 10^5$， $1\le t_{i?1}\le t_i\le 10^9$。

其中 $\sum k_i$ 表示所有的 $k_i$ 的和。

輸出格式

輸出 $n$ 行，第 $i$ 行輸出一個整數表示第 $i$ 艘船到達后的統計信息。

樣例 #1

樣例輸入 #1

3
1 4 4 1 2 2
2 2 2 3
10 1 3

樣例輸出 #1

3
4
4

樣例 #2

樣例輸入 #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,\sum k_i\le 10,1\le x_{i,j}\le 10,1\le t_i\le 10$。
• 對于 $20\%$ 的測試點，$1\le n\le 10,\sum k_i\le 100,1\le x_{i,j}\le 100,1\le t_i\le 32767$。
• 對于 $40\%$ 的測試點，$1\le n\le 100,\sum k_i\le 100,1\le x_{i,j}\le 100,1\le t_i\le 86400$。
• 對于 $70\%$ 的測試點，$1\le n\le 1000,\sum k_i\le 3000,1\le x_{i,j}\le 1000,1\le t_i\le 10^9$。
• 對于 $100\%$ 的測試點，$1\le n\le 10^5,\sum k_i\le 3\times 10^5,1\le x_{i,j}\le 10^5,1\le t_i\le 10^9$。題意

記錄當前船的24小時內船上人員的國籍數量

數據約束

所有數據都在int內，如果10^5左右，如果是一維數組完全沒問題，如果是二維就需要小心了

• 百分之40的數據，t都在24小時內，如果單純賺分也容易，直接統計下國籍數就行
• 百分之70的數據，數據量比較小，簡單的結構體里面包含一個國籍的數組儲存，數據點也能過
• 最后的百分之30，數據量每個船人數最多在10^5 ,如果隊列的每個結構體中數組都開這么長，直接會MLE 內存溢出了（相當于10^5 * 8 * 10^4的二維數組，G了）

思路

1. 記錄國籍數量且是24小時內，每個船都有k個人，要去重記錄，所以直接考慮用全局定義一個數組去記錄，國籍數做下標就行，例如：
2. 由于要遍歷24小時的，且要將國籍超出24小時的及時刪除，所以每個船的船員的都要記錄國籍。可以使用隊列儲存，超過24小時也能直接刪除。隊列 的每個數據項為結構體，結構體儲存時間、人數、船員信息
3. 根據數據約束分析，結構體因為儲存了數組，數組開到10^5，最終隊列儲存后容易內存溢出，所以優化處理：數組換成動態數組vector ，節省內存開銷 ，over。

參考代碼40分版

#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int a[N];
queue < node > qb;
int main() {
//	方法一：直接計不同國籍數目; 40分版 int n,t,k,num=0,gj;cin>>n;while(n--){cin>>t>>k;for(int i=0;i<k;i++){cin>>gj;if(a[gj]==0){ //新的國籍 num++;a[gj]=1;}}cout<<num<<endl; }}

參考代碼

#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int a[N];
struct node{int t;//時間int k;//船數 vector<int> g; 
//	int g[N];//只能拿70分 
} boat; 
queue < node > qb;
int main() {//結構體壓入棧，根據時間 >24H則出棧int n,t,k,num=0,gj;cin>>n;while(n--){node tb;cin>>tb.t>>tb.k;for(int i=0;i<tb.k;i++){cin>>gj;if(a[gj]==0){ //新的國籍 num++;a[gj]=1;}else{a[gj]++;	}
//			tb.g[i] = gj;tb.g.push_back(gj);}qb.push(tb);//判斷是否時間超過24h node temp;temp = qb.front();while(tb.t-temp.t>=86400){for(int i=0;i<temp.k;i++){a[temp.g[i]]--; //注意是對頭元素的國籍人數判斷！寫成隊尾就容易RE if(a[temp.g[i]]==0) num--;}qb.pop();//隊頭出列；temp = qb.front(); }cout<<num<<endl; }
}