交友視頻網(wǎng)站建設(shè)網(wǎng)絡(luò)推廣靠譜嗎
STL綜合
- 一、數(shù)據(jù)結(jié)構(gòu)
- 1. 隊(duì)列
- 2. 映射
- 二、隊(duì)列例題
- 1. 約瑟夫環(huán)(數(shù)據(jù)加強(qiáng))
- 2. 打印隊(duì)列
- 3. 小組隊(duì)列
- 4. 日志統(tǒng)計(jì) 2.0
- 三、映射真題
- 1. 眼紅的 Medusa
- 2. 美食評(píng)委
一、數(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 n n 個(gè)人報(bào)數(shù),報(bào)到 m m m 的人出列,再由下一個(gè)人重新從 1 1 1 開始報(bào)數(shù),以此類推,輸出依次出圈人的編號(hào)。
輸入描述
一行兩個(gè)整數(shù) n , m n,m n,m。
輸出描述
一行 n n n 個(gè)整數(shù),相鄰整數(shù)用一個(gè)空格隔開,按順序輸出每個(gè)出圈人的編號(hào)
樣例1
輸入
10 3
輸出
3 6 9 2 7 1 8 5 10 4
提示
對(duì)于 50 % 50\% 50% 的數(shù)據(jù), n , m ≤ 50 n,m\le 50 n,m≤50
對(duì)于 80 % 80\% 80% 的數(shù)據(jù), n ≤ 1000 , m ≤ 1 0 6 n\le1000,m\le10^6 n≤1000,m≤106
對(duì)于 100 % 100\% 100% 的數(shù)據(jù), 1 ≤ n ≤ 5000 , 1 ≤ m ≤ 1 0 9 1\le n\le5000,1\le m\le10^9 1≤n≤5000,1≤m≤109
程序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 m>n 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 1~9 1~9 間的優(yōu)先級(jí),優(yōu)先級(jí)越高表示任務(wù)越急。
打印機(jī)的運(yùn)作方式如下:首先從打印隊(duì)列里取出一個(gè)任務(wù) J J J,如果隊(duì)列里有比 J J J 更急的任務(wù),則直接把 J J J 放到打印隊(duì)列尾部,否則打印任務(wù) J J J(此時(shí)不會(huì)把它放回打印隊(duì)列)。
給定打印隊(duì)列中各個(gè)任務(wù)的優(yōu)先級(jí),以及所關(guān)注的任務(wù)在隊(duì)列中的位置(隊(duì)首位置為 0 0 0),求該任務(wù)完成的時(shí)刻。所有任務(wù)都需要 1 1 1 分鐘打印。
例如,打印隊(duì)列為 { 1 , 1 , 9 , 1 , 1 , 1 } \{ 1,1,9,1,1,1 \} {1,1,9,1,1,1},目前處于隊(duì)首的任務(wù)最終完成時(shí)刻為 5 5 5。
輸入描述
多組數(shù)據(jù),第一行一個(gè)整數(shù) T T T,表示了有 T T T 組數(shù)據(jù)。
每組數(shù)據(jù),第一行兩個(gè)整數(shù) n , m n,m n,m,分別表示隊(duì)列中任務(wù)數(shù)量,以及所關(guān)注任務(wù)的位置。
接下來一行 n n n 個(gè)數(shù),分別表示 n n 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 % 20\% 20% 的數(shù)據(jù), 0 ≤ m < n ≤ 10 0≤m<n≤10 0≤m<n≤10。
對(duì)于 60 % 60\% 60% 的數(shù)據(jù), 0 ≤ m < n ≤ 100 0≤m<n≤100 0≤m<n≤100。
對(duì)于 100 % 100\% 100% 的數(shù)據(jù), T ≤ 10 , 0 ≤ m < n ≤ 1000 T≤10,0≤m<n≤1000 T≤10,0≤m<n≤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 m m 個(gè)小組, n n n 個(gè)元素,每個(gè)元素屬于且僅屬于一個(gè)小組。
支持以下操作:
push x
:使元素 x x x 進(jìn)隊(duì),如果前邊有 x x x 所屬小組的元素, x x x 會(huì)排到自己小組最后一個(gè)元素的下一個(gè)位置,否則 x x x 排到整個(gè)隊(duì)列最后的位置。pop
:出隊(duì),彈出隊(duì)頭并輸出出隊(duì)元素,出隊(duì)的方式和普通隊(duì)列相同,即排在前邊的元素先出隊(duì)。
輸入描述
第一行有兩個(gè)正整數(shù) n , m n,m n,m,分別表示元素個(gè)數(shù)和小組個(gè)數(shù),元素和小組均從 0 0 0 開始編號(hào)。
接下來一行 n n n 個(gè)非負(fù)整數(shù) A i A_i Ai? ,表示元素 i i i 所在的小組。
接下來一行一個(gè)正整數(shù) T T T,表示操作數(shù)。
接下來 T T 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 % 30\% 30% 的數(shù)據(jù), 1 ≤ n ≤ 100 , 1 ≤ m ≤ 10 , T ≤ 50 1≤n≤100,1≤m≤10,T≤50 1≤n≤100,1≤m≤10,T≤50。
對(duì)于 100 % 100\% 100% 的數(shù)據(jù), 1 ≤ n ≤ 1 0 5 , 1 ≤ m ≤ 300 , T ≤ 1 0 5 1≤n≤10^5,1≤m≤300,T≤10^5 1≤n≤105,1≤m≤300,T≤105,輸入保證操作合法。
參考答案
#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 N N 行。其中每一行的格式是
ts id
,表示在 t s \tt ts ts 時(shí)刻編號(hào) i d \tt id id 的帖子收到一個(gè)"贊"。
現(xiàn)在小猴想統(tǒng)計(jì)有哪些帖子曾經(jīng)是"熱帖"。如果一個(gè)帖子曾在任意一個(gè)長度為 D D D 的時(shí)間段內(nèi)收到不少于 K K K 個(gè)贊,小猴就認(rèn)為這個(gè)帖子曾是"熱帖"。
具體來說,如果存在某個(gè)時(shí)刻 T T T 滿足該帖在 [ T , T + D ) [T,T+D) [T,T+D) 這段時(shí)間內(nèi)(注意是左閉右開區(qū)間)收到不少于 K K K 個(gè)贊,該帖就曾是"熱帖"。
除此之外,小猴還想知道哪個(gè)長度為 D D 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=5,D=3,K=2 N=5,D=3,K=2, N N 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 ] [2,4] [2,4] 內(nèi)“熱帖”的個(gè)數(shù)只有 1 1 1 個(gè),其中編號(hào)為 1 1 1 的帖子在時(shí)間 [ 2 , 4 ] [2,4] [2,4] 中只出現(xiàn)了一次,雖然它曾經(jīng)是"熱帖"。
給定日志,請(qǐng)你幫助小猴統(tǒng)計(jì)出"黃金時(shí)間段"內(nèi)的"熱帖"種類數(shù),以及輸出所有曾是"熱帖"的帖子編號(hào)。
輸入描述
第一行包含三個(gè)整數(shù) N , D , K N,D,K N,D,K。
以下 N N N 行每行一條日志,包含兩個(gè)整數(shù) t s , i d \tt ts,id ts,id。
輸出描述
輸出兩行:
第一行,表示"黃金時(shí)間段"內(nèi)的帖子種類數(shù)。
第二行,按從小到大的順序輸出熱帖 i d \tt id id。每個(gè) i d \tt id 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 % 50\% 50% 的數(shù)據(jù), 1 ≤ K ≤ N ≤ 1000 1≤K≤N≤1000 1≤K≤N≤1000。
對(duì)于 100 % 100\% 100% 的數(shù)據(jù), 1 ≤ K ≤ N ≤ 2 × 1 0 5 , 0 ≤ i d , t s 1≤K≤N≤2×10^5,0≤\tt{id,ts} 1≤K≤N≤2×105,0≤id,ts ≤ 1 0 5 ≤10^5 ≤105。
參考程序
#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, m n,m,表示有 n n n 個(gè)人獲得科技創(chuàng)新獎(jiǎng), m m m 個(gè)人獲得特殊貢獻(xiàn)獎(jiǎng)。
第二行 n n n 個(gè)正整數(shù),表示獲得科技創(chuàng)新獎(jiǎng)的人的編號(hào)。
第三行 m m 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 % 60\% 60% 的數(shù)據(jù), 0 ≤ n , m ≤ 1000 0 \leq n, m \leq 1000 0≤n,m≤1000,獲得獎(jiǎng)項(xiàng)的人的編號(hào) < 2 × 1 0 9 \lt 2 \times 10^9 <2×109;
對(duì)于 100 % 100\% 100% 的數(shù)據(jù), 0 ≤ n , m ≤ 1 0 5 0 \leq n, m \leq 10^5 0≤n,m≤105,獲得獎(jiǎng)項(xiàng)的人的編號(hào) < 2 × 1 0 9 \lt 2 \times 10^9 <2×109。
輸入數(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 1~n 1~n,第 i i i 個(gè)菜品的美味值是 d i d_i di?。小猴可以自己選擇對(duì)那些選手的菜品進(jìn)行打分,但是必須滿足以下兩個(gè)條件:
- 至少選擇兩位選手的菜品;
- 選擇的第一個(gè)選手和最后一位選手的菜品美味值必須相同。
小猴所選的第一個(gè)菜品和最后一個(gè)菜品之間(不包含第一個(gè)和最后一個(gè)菜品)的部分菜品可以選擇不要,請(qǐng)你幫助小猴計(jì)算所選菜品美味值的總和的最大值是多少?
輸入描述
第一行一個(gè)整數(shù) n n n;
第二行 n n n 個(gè)整數(shù) d i d_i di?。
輸出描述
一行一個(gè)整數(shù),表示所選菜品美味值的總和的最大值。
樣例1
輸入
5 1 2 3 1 2
輸出
8
樣例2
輸入
5 100 1 1 -3 1
輸出
3
提示
對(duì) 40 % 40\% 40% 的數(shù)據(jù)保證: 2 ≤ n ≤ 5000 , d i > 0 2≤n≤5000,d_i>0 2≤n≤5000,di?>0;
對(duì) 100 % 100\% 100% 的數(shù)據(jù)保證: 2 ≤ n ≤ 2 × 1 0 5 , ? 1 0 9 ≤ d i ≤ 1 0 9 2≤n≤2×10^5,-10^9\le d_i\le10^9 2≤n≤2×105,?109≤di?≤109。