收拾妥當，沈笑夫拿出《初中組駕駛學科奧賽基礎知識》，翻到基本數據結構這章，認真研讀這道題目：
第一題：海港
【題目描述】
小K是一個海港的海關工作人員，每天都有許多船只到達海港，船上通常有很多來自不同國家的乘客。
小K對這些到達海港的船只非常感興趣，他按照時間記錄下了到達海港的每一艘船只情況；
對于第i艘到達的船，他記錄了這艘船到達的時間ti (單位：秒)，船上的乘客數量ki，以及每名乘客的國籍 x(i，1)， x(i，2)，…，x(i，k);。
小K統計了n艘船的信息，希望你幫忙計算出以每一艘船到達時間為止的24小時(24小時=86400秒）內所有乘船到達的乘客來自多少個不同的國家。
形式化地講，你需要計算n條信息。對于輸出的第i條信息，你需要統計滿足 ti – 86400 < tp <= ti的船只p，在所有的x(p，j)中，總共有多少個不同的數。
【輸入格式】第一行輸入一個正整數n，表示小K統計了 n艘船的信息。
接下來的n行，每行描述一艘船的信息：前兩個整數ti和ki分別表示這艘船到達海港的時間和船上的乘客數量，接下來ki個整數x(i，j)表示船上乘客的國籍。
保證輸入的ti是遞增的，單位是秒；表示從小K第一次上班開始計時，這艘船在第 ti 秒到達海港。
保證 1≤n≤10 ^5 ，∑ki≤3??10 ^5 ， 1≤x(i，j)≤10 ^5 ， 1≤t(i??1)<ti≤10 ^9
其中∑ki表示所有的ki的和，∑ki = k1 + k2 +...+ kn。
【輸出格式】
輸出n行，第i行輸出一個整數表示第i艘船到達后的統計信息。
【輸入樣例 1】
3
1 4 4 1 2 2
2 2 2 3
10 1 3
【輸出樣例1】
3
4
4
【樣例1說明】
第1艘船在第1秒到達海港，最近24小時到達的船是第1艘船，共有4個乘客，分別是來自國家4，1，2，2，共來自3個不同的國家。
第2艘船在第2秒到達海港，最近24小時到達的船是第1艘船和第2艘船，共有4+2=6個乘客，分別是來自國家4，1，2，2，2，3，共來自4個不同的國家。
第3艘船在第10秒到達海港，最近24小時到達的船是第1艘船、第2艘船和第3艘船，共有4+2+1=7個乘客，分別是來自國家4，1，2，2，2，3，3，共來自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
【樣例2說明】
第1艘船在第1秒到達海港，最近24小時到達的船是第1艘船，共有4個乘客，分別是來自國家1，2，2，3，共來自3個不同的國家。
第2艘船在第3秒到達海港，最近24小時到達的船是第1艘船和第2艘船，共有4+2=6個乘客，分別是來自國家1，2，2，3，2，3，共來自3個不同的國家。
第3艘船在第86401秒到達海港，最近24小時到達的船是第2艘船和第3艘船，共有2+2=4個乘客，分別是來自國家2，3，3，4，共來自3個不同的國家。
第4艘船在第86402秒到達海港，最近24小時到達的船是第2艘船、第3艘船和第4艘船，共有2+2+1=5個乘客，分別是來自國家2，3，3，4，5，共來自4個不同的國家。
【數據規模與約定】
對于 10%的測試點， n = 1，∑ki≤10，1≤xi，j≤10，1≤ti≤10；
對于 20%的測試點， 1≤n≤10，∑ki≤100，1≤xi，j≤100，1≤ti≤32767 ；
對于 40%的測試點， 1≤n≤100，∑ki≤100，1≤xi，j≤100，1≤ti≤86400 ；
對于 70%的測試點， 1≤n≤1000，∑ki≤3000，1≤xi，j≤1000，1≤ti≤109 ；
對于 100%的測試點， 1≤n≤105，∑ki≤3×105，1≤xi，j≤105，1≤ti≤109 。
沈笑夫一邊做題，一邊寫解題報告：
“最早我看到這道題就用普通數組來存組這堆數據，一個一維數組存t，一個一維數組來存k。
但是，編了一半就發現了爆空間的問題，于是刪掉它，用向量vector來編它，再定義一個ans數組存答案。
每一次計算出從這艘船開始向前一直找到超過86400秒的一艘船，刪掉它們的內存，再從剩下的第一條船開始計算，統計(統計過程用桶排序式來)，一直到目前的一條船。
代碼如下：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<ctime>
#include&lttype>
#include<iomanip>
#include
<algorithm&amp;gt;
#include&amp;lt;vector&amp;gt;
#include&amp;lt;map&amp;gt;”
沈笑夫心想：這道題直接做是過不了的，它就是不斷的將先來的弄出去，相當于隊列一樣用一個隊列維護時間t，每次看隊首元素有沒有相隔24小時。
如果有，則l++，否則入隊統計。
對于數據的存儲可能有點困難，n*∑ki的數組是開不下的，但是他是按照每艘船的順序給出來的，如果可以轉化為一條鏈就好了。
第一個方法是vector，似乎有點慢；第二個方法是queue，這個可以用數組模擬，效率比較高。
每次刪除一條船就都從隊列中刪除信息，開一個vis數組記錄一下人數。
這里是不能用bool數組或者每次都掃一下vis數組的，可以動態改變答案。
??前綴和也是行不通的，不能滿足區間減性質。
當數組大小是n*m這種乘積類型時，可以考慮能不能轉化成一條鏈狀的形式。動態統計答案是一種有效處理多次統計答案的問題的方式。
沈笑夫一邊做題，一邊想，這駕駛學科奧賽，沒有數學和信息學的底子，恐怕還真不行。
這無人駕駛，動不動就是編程、就是程序，就是遠程控制，當然需要數學和信息學知識。
沈笑夫忽然對自己說：
“在未來，不會編程的，都將是文盲。”
什么樣的人會是未來人工智能時代的領袖呢？其實，這個問題的答案很顯然——當然是學過數學、信息學的人！
沈笑夫翻開《初中組駕駛學科奧賽基礎知識》，看到《計算機科學》這一章：
“信息學在 1960—1970 年代從數學中分出，但一直與數學相互促進。
正與圖靈獎獲得者John Hopcroft 所說:信息學前30 年大量使用離散數學，而現在則離不開隨機數學。
比如，機器學習就是數學與信息學的一個交叉領域。
無人駕駛、智能駕駛，正在大量應用數學建模和信息學技術。
數學、信息學將在目前的‘機器人計劃'和陸海空‘無人駕駛'研制中發揮更大作用……
駕駛學科奧賽，離不開數學和信息學！”
沈笑夫心想，看來，自己還得加把油，把數學和信息學底子打扎實！
【精彩東方文學 www.nuodawy.com】 提供武動乾坤等作品手打文字版最新章節首發，txt電子書格式免費下載歡迎注冊收藏。