1、普及數(shù)據(jù)結(jié)構(gòu)選講,anantheparty -hust cdqz,說明,提示，有大量題目是多組數(shù)據(jù)，需要處理到文件末，處理方式可以參考第一天講課中scanf的返回值 即 while(scanf(%d, S.top();S.pop();S.push(x);S.size();S.empty(); 每個操作都是O(1)的 很少使用STL,棧,可以快速手寫 int SM,h; Push:S+h=x; Pop:h-;,棧,可以快速手寫 int SM,h; Push:S+h=x; Pop:h-;,棧,HDU - 1022 Train Problem 給你一個排列，將第一個排列以一定的方式進棧出棧，詢問是否

2、可以試出棧順序為另一個排列 輸出是否，若答案為是，輸出操作,HDU 1022,Sample Input 3 123 321 3 123 312 Sample Output Yes. in in in out out out FINISH No. FINISH,HDU 1022,考慮棧的基本性質(zhì)LIFO，所以第一個出棧的一定是最后一個進棧的 所以用一個棧直接模擬即可 將第一個出棧之前的全部push，然后pop掉可行點，然后重復(fù)這個操作 如果無法操作完全說明答案為否,核心代碼,h=0;t=0;i=1;j=1; while(j=M?0:h+1)=x; Pop:t=(t+1=M?0:t+1);,隊列,

3、作用？ BFS，SPFA時用隊列存點 維護一個單調(diào)隊列 核心思想FIFO,隊列,Luogu 1540 你有一臺內(nèi)存為M(MQ;,鏈表,優(yōu)點:可以在任意位置插入刪除 每次訪問一個點必須遍歷它之前或者之后的所有節(jié)點 雙向鏈表: 單向鏈表:,鏈表,用處？ 用鄰接鏈表儲存一張圖 單向鏈表:只需要單向訪問，如鄰接鏈表 雙向鏈表:需要訪問一個節(jié)點的左右兩側(cè)，如模擬光標(biāo)移動并刪除插入各種字符,鏈表,Luogu 1160隊列安排 需要將編號為從1N的N(N100,000)個同學(xué)依次排成一排，除了一號同學(xué)外，每個同學(xué)i將拍在Ki的左邊或右邊 列隊完成后，會選擇M的同學(xué)，編號X1XM從隊列中刪除 求最后隊列從左到

4、右的同學(xué)的編號,Luogu 1160,由于要各種插入，刪除，顯然應(yīng)該用一個鏈表來維護 由于可以在一個人的左右兩側(cè)插入，需要用雙線鏈表維護,并查集,高效判斷動態(tài)連通性 實現(xiàn): int get_fa(int x) return x=fax?x:fax=get_fa(fax); ,并查集,HDU 5652 給你一個網(wǎng)格圖，你要從最下方走到最上方，有一些格子是山脈，不可通過 山脈會隨著時間Q生成 求從什么時候開始，上方和下方不再連通 T10 1N500 1M500 1QN*M,HDU 5652,很容易想到一個離線并查集的做法，我們先將所有即將生成的山脈放置在網(wǎng)格圖上，然后按時間倒敘，依次刪去山脈，判斷

5、什么時候變得連通即可,HDU 5652,我們再想想可以發(fā)現(xiàn)第二個做法 上下不連通有一個充要條件，就是左右的山脈存在一條八角連通的路徑 所以我們可以不用離線，直接用并查集判斷左右是否聯(lián)通即可,HDU 5652,當(dāng)然，由于數(shù)據(jù)規(guī)模不大，我們還可以二分+bfs完成，大家可以自己下來思考,常見STL,stack queue priority_queue vector map set,Vector,#include vector a; a.push_back(x);a.pop_back();a.size();ai;,map,#include mapm; mATP=5;,set,#include setS

6、; S.insert(x);S.erase(x);S.size();S.empty(); set:iterator i; i=S.upper_bound(x);i=S.lower_bound(x); i=S.find(x);if(i!=S.end(); for(i=S.begin();i!=S.end();i+);,雜題選講,anantheparty,雜題選講,Luogu 1090 NOIP2004提高 合并果子 現(xiàn)在有n堆果子，每堆果子有一個質(zhì)量，現(xiàn)在你要將所有果子合并成一堆，每次你可以合并兩堆果子，代價是兩堆的質(zhì)量和,Luogu 1090,可以看出，每次合并的代價就是每次合并的新的堆的質(zhì)量

7、，然后合成的次數(shù)是固定的，所以我們應(yīng)該讓小的堆盡可能多 也就是說我們每次選兩堆質(zhì)量最小的出來合成即可 然后我們用優(yōu)先隊列維護所有堆，每次取最小的兩堆合成后在放回去即可 同樣，這是一個維護最小的堆。,雜題選講,POJ 3250 Luogu 2866 一列牛n個(1 n 80,000)，從前往后站成一排，每個牛的頭發(fā)有個高度(1 hi 1,000,000,000)，每個?？梢钥匆婎^發(fā)比它矮且未被遮擋的牛，每個牛會遮擋他前方所有頭發(fā)的高度小于等于他的牛 所有牛能看到的牛的數(shù)量和,Sample Input 6 10 3 7 4 12 2 Sample Output 5,Luogu 2866,從前往后掃

8、，考慮A被遮擋時，遮擋他的牛B一定看得到他，而這時B后面的牛顯然看不到A，A和B之間顯然沒有比A高的，所以每個牛對答案的貢獻就只有1 然后從前往后維護一個單調(diào)棧，維護當(dāng)前沒有貢獻的牛，每次push之前將所有小于當(dāng)前的點pop，貢獻+,雜題選講,HDU - 3183 Luogu 1106 給你一個位數(shù)為n的數(shù)(n=1000)，和k。求刪除k位數(shù)字后，新的數(shù)字最小是多少(出時忽略前導(dǎo)0),Sample Input 178543 4 1000001 1 100001 2 12345 2 54321 2 Sample Output 13 1 0 123 321,HDU 3183,因為刪除的是k位，所以

9、最后剩下的數(shù)字一定是(n-k)位的(不刪除前導(dǎo)0) 對于位數(shù)相同的數(shù)比較大小，高位越小的數(shù)字顯然更小 所有假設(shè)我們存在一個 576.這樣的數(shù)字，刪除7會讓第二高位變成6，若刪除后面的數(shù)字，結(jié)果的第二位就是7，顯然沒有刪除7優(yōu) 所以我們在前段維持一個單調(diào)上升的序列就可以了 可以用單調(diào)棧維護,核心代碼,h=0;p=1; n=strlen(s+1); for(int i=1;i=n;i+)ai=si-0;/ai記錄由高到低每位數(shù)字 for(int i=1;i=n;i+) while(k,下發(fā)文件附完整代碼,雜題選講,HDU 6058,HDU 6058,題意大概是說，給你一個長度為N的排列，遍歷每個區(qū)

10、間，對于每個區(qū)間中第k大的數(shù)A，會對答案有A的貢獻，求最后的貢獻和,HDU 6058,這個題k只有80，顯然是一個突破點 對于這種計數(shù)題，我們可以想到，分別考慮每個位置的數(shù)的貢獻，即，在多少個區(qū)間內(nèi)一個數(shù)是第k大的 然后我們可以想到，如果我們知道了每個數(shù)左邊k個比它大以及右邊k個比它大的數(shù)的位置，我們就可以O(shè)(k)的求出這個數(shù)對答案的貢獻(為左右兩個區(qū)間的長度相乘) 然后現(xiàn)在問題就轉(zhuǎn)換成，如何在合法時間內(nèi)，求出每個數(shù)左右k個比它大的數(shù),HDU 6058,我們可以想到，1的左右k個，一定比k大，然后我們就可以求出1的貢獻了,我們發(fā)現(xiàn)這個操作只需要從1開始暴力向左右走k步就可以了，于是我們用鏈表維護整個排列，從小到大計算貢獻，算完每個數(shù)的貢獻后，將這個數(shù)從鏈表中刪除就可以了，每次貢獻的計算復(fù)雜度為O(k)，所有總的時間復(fù)雜度為O(nk),核心代碼,n=read(),k=read()-1;/k減一表示有幾個數(shù)比所求位大 r0=1;ln+1=n;ans=0; for(int i=1;i=n;i+) ai=read