一、數(shù)據(jù)結(jié)構(gòu)

1. 隊(duì)列

功能	代碼
定義	queue<tp>q
入隊(duì)	.push(x)
出隊(duì)	.pop()
隊(duì)頭	.front()
隊(duì)尾	.back()
為空	.empty()
大小	.size()

2. 映射

功能	代碼
定義	map<tp1,tp2>name
增/改	mp[key]=value
刪除	.erase(key)
全刪	.clear()
頭部	.begin()
尾部	.end()
key 出現(xiàn)	.count(key)
為空	.empty()
大小	.size()
查找	.find(key)
鍵	it->first
值	it->second

二、隊(duì)列例題

1. 約瑟夫環(huán)（數(shù)據(jù)加強(qiáng)）

題目描述

$n$ 個(gè)人報(bào)數(shù)，報(bào)到 $m$ 的人出列，再由下一個(gè)人重新從 $1$ 開始報(bào)數(shù)，以此類推，輸出依次出圈人的編號(hào)。

輸入描述

一行兩個(gè)整數(shù)$n,m$。

輸出描述

一行 $n$ 個(gè)整數(shù)，相鄰整數(shù)用一個(gè)空格隔開，按順序輸出每個(gè)出圈人的編號(hào)

樣例1

輸入

10 3

輸出

3 6 9 2 7 1 8 5 10 4

提示

對(duì)于 $50\%$ 的數(shù)據(jù)，$n,m\le 50$
對(duì)于 $80\%$ 的數(shù)據(jù)，$n\le 1000,m\le 10^6$
對(duì)于 $100\%$ 的數(shù)據(jù)，$1\le n\le 5000,1\le m\le 10^9$

程序1: 暴力

#include<bits/stdc++.h>
using namespace std;
int n,m;
queue<int>q;
int main(){cin>>n>>m;for(int i=1;i<=n;i++)q.push(i);for(int i=1;i<=n;i++){//一共有n個(gè)人需要出圈for(int j=1;j<=m-1;j++){//前1~m-1的人不用出圈q.push(q.front());//備份一份本體到隊(duì)尾q.pop();//本體刪除}cout<<q.front()<<" ";//輸出出圈人q.pop();//出圈人出圈}return 0;
}

問題：直接模擬會(huì)非常耗時(shí)，尤其是 $m>n$ 的時(shí)候，可以考慮使用模運(yùn)算作答。

參考答案

#include<bits/stdc++.h>
using namespace std;
int n,m;
queue<int>q;
int main(){cin>>n>>m;for(int i=1;i<=n;i++)q.push(i);for(int i=1;i<=n;i++){for(int j=1;j<=(m-1)%q.size();j++){//模運(yùn)算，記得不要直接m%=nq.push(q.front());q.pop();}cout<<q.front()<<" ";q.pop();}return 0;
}

2. 打印隊(duì)列

題目描述

學(xué)生會(huì)里只有一臺(tái)打印機(jī)，但是有很多文件需要打印，因此打印任務(wù)不可避免地需要等待。有些打印任務(wù)比較急，有些不那么急，所以每個(gè)任務(wù)都有一個(gè) $1～9$ 間的優(yōu)先級(jí)，優(yōu)先級(jí)越高表示任務(wù)越急。
打印機(jī)的運(yùn)作方式如下：首先從打印隊(duì)列里取出一個(gè)任務(wù) $J$，如果隊(duì)列里有比 $J$ 更急的任務(wù)，則直接把 $J$ 放到打印隊(duì)列尾部，否則打印任務(wù) $J$（此時(shí)不會(huì)把它放回打印隊(duì)列）。
給定打印隊(duì)列中各個(gè)任務(wù)的優(yōu)先級(jí)，以及所關(guān)注的任務(wù)在隊(duì)列中的位置（隊(duì)首位置為 $0$），求該任務(wù)完成的時(shí)刻。所有任務(wù)都需要 $1$ 分鐘打印。
例如，打印隊(duì)列為 { 1 , 1 , 9 , 1 , 1 , 1 } \{ 1,1,9,1,1,1 \} {1,1,9,1,1,1}，目前處于隊(duì)首的任務(wù)最終完成時(shí)刻為 $5$。

輸入描述

多組數(shù)據(jù)，第一行一個(gè)整數(shù) $T$，表示了有 $T$ 組數(shù)據(jù)。
每組數(shù)據(jù)，第一行兩個(gè)整數(shù) $n,m$，分別表示隊(duì)列中任務(wù)數(shù)量，以及所關(guān)注任務(wù)的位置。
接下來一行 $n$ 個(gè)數(shù)，分別表示 $n$ 個(gè)任務(wù)的優(yōu)先級(jí)。

輸出描述

每組數(shù)據(jù)輸出一行，表示所關(guān)注任務(wù)的完成時(shí)刻。

樣例1

輸入

3
1 0
5
4 2
1 2 3 4
6 0
1 1 9 1 1 1

輸出

1
2
5

提示

對(duì)于 $20\%$ 的數(shù)據(jù)，$0\le m<n\le 10$。
對(duì)于 $60\%$ 的數(shù)據(jù)，$0\le m<n\le 100$。
對(duì)于 $100\%$ 的數(shù)據(jù)，$T\le 10,0\le m<n\le 1000$。

參考答案

#include<bits/stdc++.h>
using namespace std;
int t,n,m;
int cnt[10];
struct task{int id,prio;//編號(hào)和優(yōu)先級(jí)
};
bool check(int p){//查找打印優(yōu)先級(jí)for(int i=p+1;i<=9;i++)//遍歷更高的優(yōu)先級(jí)if(cnt[i]!=0)//有更高優(yōu)先級(jí)的任務(wù)等待打印return true;//不打印return false;//打印
}
void solve(){memset(cnt,0,sizeof(cnt));//清空優(yōu)先級(jí)計(jì)數(shù)queue<task>q;cin>>n>>m;for(int i=0,p;i<n;i++){//id從0開始cin>>p;//輸入優(yōu)先級(jí)cnt[p]++;//增加對(duì)應(yīng)優(yōu)先級(jí)任務(wù)的計(jì)數(shù)q.push({i,p});//存儲(chǔ)任務(wù)}int ans=0;while(!q.empty()){auto[id,p]=q.front();//取出隊(duì)首q.pop();if(check(p))//不可以打印q.push({id,p});else{ans++;//增加做任務(wù)的次數(shù)cnt[p]--;//減少對(duì)應(yīng)優(yōu)先級(jí)任務(wù)的計(jì)數(shù)if(id==m){//是否為關(guān)注任務(wù)cout<<ans<<endl;return;}}}
}
int main(){cin>>t;while(t--)solve();return 0;
}

3. 小組隊(duì)列

題目描述

有 $m$ 個(gè)小組，$n$ 個(gè)元素，每個(gè)元素屬于且僅屬于一個(gè)小組。
支持以下操作：

• push x：使元素 $x$ 進(jìn)隊(duì)，如果前邊有 $x$ 所屬小組的元素，$x$ 會(huì)排到自己小組最后一個(gè)元素的下一個(gè)位置，否則 $x$ 排到整個(gè)隊(duì)列最后的位置。
• pop：出隊(duì)，彈出隊(duì)頭并輸出出隊(duì)元素，出隊(duì)的方式和普通隊(duì)列相同，即排在前邊的元素先出隊(duì)。

輸入描述

第一行有兩個(gè)正整數(shù) $n,m$，分別表示元素個(gè)數(shù)和小組個(gè)數(shù)，元素和小組均從 $0$ 開始編號(hào)。
接下來一行 $n$ 個(gè)非負(fù)整數(shù) $A_i$ ，表示元素 $i$ 所在的小組。
接下來一行一個(gè)正整數(shù) $T$，表示操作數(shù)。
接下來 $T$ 行，每行為一個(gè)操作。

輸出描述

對(duì)于每個(gè)出隊(duì)操作輸出一行，為出隊(duì)的元素。

樣例1

輸入

4 2
0 0 1 1
6
push 2
push 0
push 3
pop
pop
pop

輸出

2
3
0

提示

對(duì)于 $30\%$ 的數(shù)據(jù)，$1\le n\le 100,1\le m\le 10,T\le 50$。
對(duì)于 $100\%$ 的數(shù)據(jù)，$1\le n\le 10^5,1\le m\le 300,T\le 10^5$，輸入保證操作合法。

參考答案

#include<bits/stdc++.h>
using namespace std;
int t,n,m;
int a[100010];//每個(gè)人所屬的隊(duì)伍編號(hào)
queue<int>q;//隊(duì)伍編號(hào)
queue<int>team[305];//隊(duì)伍成員的隊(duì)列數(shù)組
int main(){cin>>n>>m;for(int i=0;i<n;i++)cin>>a[i];cin>>t;while(t--){string op;cin>>op;if(op=="push"){int x;cin>>x;if(team[a[x]].empty())//如果x所屬隊(duì)伍之前沒有人入隊(duì)q.push(a[x]);//將x所屬隊(duì)伍入隊(duì)team[a[x]].push(x);//將x入隊(duì)到對(duì)應(yīng)隊(duì)伍中} else {int x=q.front();//取出下一個(gè)要出隊(duì)的隊(duì)伍編號(hào)cout<<team[x].front()<<endl;//輸出當(dāng)前隊(duì)首隊(duì)伍中的第一個(gè)人的編號(hào)team[x].pop();//將當(dāng)前隊(duì)首隊(duì)伍中的第一個(gè)人出隊(duì)if(team[x].empty())//如果當(dāng)前隊(duì)首隊(duì)伍中沒有人了q.pop();//將當(dāng)前隊(duì)伍從隊(duì)伍中刪除}}return 0;
}

4. 日志統(tǒng)計(jì) 2.0

題目描述

小猴維護(hù)著一個(gè)程序員論壇。現(xiàn)在他收集了一份"點(diǎn)贊"日志，日志共有 $N$ 行。其中每一行的格式是 ts id，表示在 $\mathtt{ts}$ 時(shí)刻編號(hào) $\mathtt{id}$ 的帖子收到一個(gè)"贊"。
現(xiàn)在小猴想統(tǒng)計(jì)有哪些帖子曾經(jīng)是"熱帖"。如果一個(gè)帖子曾在任意一個(gè)長度為 $D$ 的時(shí)間段內(nèi)收到不少于 $K$ 個(gè)贊，小猴就認(rèn)為這個(gè)帖子曾是"熱帖"。
具體來說，如果存在某個(gè)時(shí)刻 $T$ 滿足該帖在 $[T,T+D)$ 這段時(shí)間內(nèi)（注意是左閉右開區(qū)間）收到不少于 $K$ 個(gè)贊，該帖就曾是"熱帖"。
除此之外，小猴還想知道哪個(gè)長度為 $D$ 的時(shí)間段內(nèi)的"熱帖"種類最多，小猴稱這個(gè)段時(shí)間為"黃金時(shí)間段"。這里統(tǒng)計(jì)帖子的出現(xiàn)次數(shù)只能使用該黃金時(shí)間段內(nèi)的帖子，也就是說在黃金時(shí)間段內(nèi)的帖子之前可能是"熱帖"，但是僅在黃金時(shí)間段內(nèi)卻可能不是"熱帖"。
例如，$N=5,D=3,K=2$，$N$ 個(gè)帖子依次是 { 1 , 1 } , { 2 , 1 } , { 3 , 2 } , { 4 , 2 } , { 5 , 3 } \{1,1\},\{2,1\},\{3,2\},\{4,2\},\{5,3\} {1,1},{2,1},{3,2},{4,2},{5,3}（以 { t s , i d } \{\tt ts,id\} {ts,id} 的形式依次給出每個(gè)帖子的信息），那么在黃金時(shí)間段 $[2,4]$ 內(nèi)“熱帖”的個(gè)數(shù)只有 $1$ 個(gè)，其中編號(hào)為 $1$ 的帖子在時(shí)間 $[2,4]$ 中只出現(xiàn)了一次，雖然它曾經(jīng)是"熱帖"。
給定日志，請(qǐng)你幫助小猴統(tǒng)計(jì)出"黃金時(shí)間段"內(nèi)的"熱帖"種類數(shù)，以及輸出所有曾是"熱帖"的帖子編號(hào)。

輸入描述

第一行包含三個(gè)整數(shù) $N,D,K$。
以下 $N$ 行每行一條日志，包含兩個(gè)整數(shù) $\mathtt{ts},\mathtt{id}$。

輸出描述

輸出兩行：
第一行，表示"黃金時(shí)間段"內(nèi)的帖子種類數(shù)。
第二行，按從小到大的順序輸出熱帖 $\mathtt{id}$。每個(gè) $\mathtt{id}$ 之間空格隔開, 如果沒有任何熱帖就輸出 ?1。

樣例1

輸入

7 10 2
0 1
0 10
10 10
10 1
9 1
100 3
100 3

輸出

1
1 3

樣例2

輸入

7 10 1
0 1
0 10
10 10
10 1
9 1
100 3
100 3

輸出

2
1 3 10 

樣例3

輸入

7 10 3
0 1
0 10
10 10
10 1
9 1
100 3
100 3

輸出

0
-1

提示

對(duì)于 $50\%$ 的數(shù)據(jù)，$1\le K\le N\le 1000$。
對(duì)于 $100\%$ 的數(shù)據(jù)，$1\le K\le N\le 2\times 10^5,0\le \mathtt{id},\mathtt{ts}$ $\le 10^5$。

參考程序

#include<bits/stdc++.h>
using namespace std;
const int MAXN=200010;
int n,d,k,cnt;
int sum[MAXN];
int isHot[MAXN];
struct LOG{int ts,id;bool operator<(const LOG&rhs)const{return ts<rhs.ts;}
}logs[MAXN];
queue<LOG>q;//某個(gè)長度為D的時(shí)間段的熱搜情況
int main(){cin>>n>>d>>k;for(int i=1;i<=n;i++)cin>>logs[i].ts>>logs[i].id;sort(logs+1,logs+n+1);int ans=0;for(int i=1;i<=n;i++){while(!q.empty()&&q.front().ts<=logs[i].ts-d){if(sum[q.front().id]==k)//點(diǎn)贊個(gè)數(shù)剛好是k條cnt--;//減少熱帖個(gè)數(shù)sum[q.front().id]--;q.pop();}//把當(dāng)前記錄放入日志q.push(logs[i]);sum[logs[i].id]++;if(sum[logs[i].id]==k){cnt++;//新增一個(gè)熱帖isHot[logs[i].id]=1;//標(biāo)記為熱帖}ans=max(ans,cnt);}cout<<ans<<endl;if(ans==0)cout<<"-1\n";else{for(int i=1;i<=n;i++)if(isHot[i])cout<<i<<" ";}return 0;
}

三、映射真題

1. 眼紅的 Medusa

題目描述

雖然 Miss Medusa 到了北京，領(lǐng)了科技創(chuàng)新獎(jiǎng)，但是她還是覺得不滿意。原因是：他發(fā)現(xiàn)很多人都和她一樣獲了科技創(chuàng)新獎(jiǎng)，特別是其中的某些人，還獲得了另一個(gè)獎(jiǎng)項(xiàng)——特殊貢獻(xiàn)獎(jiǎng)。而越多的人獲得了兩個(gè)獎(jiǎng)項(xiàng)，Miss Medusa就會(huì)越眼紅。于是她決定統(tǒng)計(jì)有哪些人獲得了兩個(gè)獎(jiǎng)項(xiàng)，來知道自己有多眼紅。

輸入格式

第一行兩個(gè)整數(shù) $n,m$，表示有 $n$ 個(gè)人獲得科技創(chuàng)新獎(jiǎng)，$m$ 個(gè)人獲得特殊貢獻(xiàn)獎(jiǎng)。
第二行 $n$ 個(gè)正整數(shù)，表示獲得科技創(chuàng)新獎(jiǎng)的人的編號(hào)。
第三行 $m$ 個(gè)正整數(shù)，表示獲得特殊貢獻(xiàn)獎(jiǎng)的人的編號(hào)。

輸出格式

輸出一行，為獲得兩個(gè)獎(jiǎng)項(xiàng)的人的編號(hào)，按在科技創(chuàng)新獎(jiǎng)獲獎(jiǎng)名單中的先后次序輸出。

樣例1

輸入

4 3
2 15 6 8
8 9 2

輸出

2 8

提示

對(duì)于 $60\%$ 的數(shù)據(jù)，$0\le n,m\le 1000$，獲得獎(jiǎng)項(xiàng)的人的編號(hào) $<2\times 10^9$；
對(duì)于 $100\%$ 的數(shù)據(jù)，$0\le n,m\le 10^5$，獲得獎(jiǎng)項(xiàng)的人的編號(hào) $<2\times 10^9$。
輸入數(shù)據(jù)保證第二行任意兩個(gè)數(shù)不同，第三行任意兩個(gè)數(shù)不同。

參考答案

#include<bits/stdc++.h>
using namespace std;
map<int,bool>mp;
int n,m,awd[100010];
int main(){cin>>n>>m;for(int i=1;i<=n;i++)cin>>awd[i];for(int i=1,id;i<=m;i++)cin>>id,mp[id]=true;for(int i=1;i<=n;i++)if(mp[awd[i]]==true)cout<<awd[i]<<" ";return 0;
}

2. 美食評(píng)委

題目描述

一年一度的美食比賽火熱進(jìn)行中，小猴作為評(píng)委需要對(duì)一些選手的菜品打分，所有菜品從左到右排成一排，編號(hào)依次為 $1～n$，第 $i$ 個(gè)菜品的美味值是 $d_i$。小猴可以自己選擇對(duì)那些選手的菜品進(jìn)行打分，但是必須滿足以下兩個(gè)條件：

• 至少選擇兩位選手的菜品；
• 選擇的第一個(gè)選手和最后一位選手的菜品美味值必須相同。

小猴所選的第一個(gè)菜品和最后一個(gè)菜品之間（不包含第一個(gè)和最后一個(gè)菜品）的部分菜品可以選擇不要，請(qǐng)你幫助小猴計(jì)算所選菜品美味值的總和的最大值是多少？

輸入描述

第一行一個(gè)整數(shù) $n$；
第二行 $n$ 個(gè)整數(shù) $d_i$。

輸出描述

一行一個(gè)整數(shù)，表示所選菜品美味值的總和的最大值。

樣例1

輸入

5
1 2 3 1 2

輸出

8

樣例2

輸入

5
100 1 1 -3 1

輸出

3

提示

對(duì) $40\%$ 的數(shù)據(jù)保證：$2\le n\le 5000,d_i>0$；
對(duì) $100\%$ 的數(shù)據(jù)保證：$2\le n\le 2\times 10^5,?10^9\le d_i\le 10^9$。