C++知识点总结(57):STL综合

news/2024/11/17 17:24:07/

STL综合

  • 一、数据结构
    • 1. 队列
    • 2. 映射
  • 二、队列例题
    • 1. 约瑟夫环(数据加强)
    • 2. 打印队列
    • 3. 小组队列
    • 4. 日志统计 2.0
  • 三、映射真题
    • 1. 眼红的 Medusa
    • 2. 美食评委

一、数据结构

1. 队列

功能代码
定义queue<tp>q
入队.push(x)
出队.pop()
队头.front()
队尾.back()
为空.empty()
大小.size()

2. 映射

功能代码
定义map<tp1,tp2>name
增/改mp[key]=value
删除.erase(key)
全删.clear()
头部.begin()
尾部.end()
key 出现.count(key)
为空.empty()
大小.size()
查找.find(key)
it->first
it->second

二、队列例题

1. 约瑟夫环(数据加强)

题目描述

n n n 个人报数,报到 m m m 的人出列,再由下一个人重新从 1 1 1 开始报数,以此类推,输出依次出圈人的编号。

输入描述

一行两个整数 n , m n,m n,m

输出描述

一行 n n n 个整数,相邻整数用一个空格隔开,按顺序输出每个出圈人的编号

样例1

输入

10 3

输出

3 6 9 2 7 1 8 5 10 4

提示

对于 50 % 50\% 50% 的数据, n , m ≤ 50 n,m\le 50 n,m50
对于 80 % 80\% 80% 的数据, n ≤ 1000 , m ≤ 1 0 6 n\le1000,m\le10^6 n1000,m106
对于 100 % 100\% 100% 的数据, 1 ≤ n ≤ 5000 , 1 ≤ m ≤ 1 0 9 1\le n\le5000,1\le m\le10^9 1n5000,1m109

程序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个人需要出圈for(int j=1;j<=m-1;j++){//前1~m-1的人不用出圈q.push(q.front());//备份一份本体到队尾q.pop();//本体删除}cout<<q.front()<<" ";//输出出圈人q.pop();//出圈人出圈}return 0;
}

问题:直接模拟会非常耗时,尤其是 m > n m>n m>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++){//模运算,记得不要直接m%=nq.push(q.front());q.pop();}cout<<q.front()<<" ";q.pop();}return 0;
}

2. 打印队列

题目描述

学生会里只有一台打印机,但是有很多文件需要打印,因此打印任务不可避免地需要等待。有些打印任务比较急,有些不那么急,所以每个任务都有一个 1 ∼ 9 1∼9 19 间的优先级,优先级越高表示任务越急。
打印机的运作方式如下:首先从打印队列里取出一个任务 J J J,如果队列里有比 J J J 更急的任务,则直接把 J J J 放到打印队列尾部,否则打印任务 J J J(此时不会把它放回打印队列)。
给定打印队列中各个任务的优先级,以及所关注的任务在队列中的位置(队首位置为 0 0 0),求该任务完成的时刻。所有任务都需要 1 1 1 分钟打印。
例如,打印队列为 { 1 , 1 , 9 , 1 , 1 , 1 } \{ 1,1,9,1,1,1 \} {1,1,9,1,1,1},目前处于队首的任务最终完成时刻为 5 5 5

输入描述

多组数据,第一行一个整数 T T T,表示了有 T T T 组数据。
每组数据,第一行两个整数 n , m n,m n,m,分别表示队列中任务数量,以及所关注任务的位置。
接下来一行 n n n 个数,分别表示 n n n 个任务的优先级。

输出描述

每组数据输出一行,表示所关注任务的完成时刻。

样例1

输入

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

输出

1
2
5

提示

对于 20 % 20\% 20% 的数据, 0 ≤ m < n ≤ 10 0≤m<n≤10 0m<n10
对于 60 % 60\% 60% 的数据, 0 ≤ m < n ≤ 100 0≤m<n≤100 0m<n100
对于 100 % 100\% 100% 的数据, T ≤ 10 , 0 ≤ m < n ≤ 1000 T≤10,0≤m<n≤1000 T10,0m<n1000

参考答案

#include<bits/stdc++.h>
using namespace std;
int t,n,m;
int cnt[10];
struct task{int id,prio;//编号和优先级
};
bool check(int p){//查找打印优先级for(int i=p+1;i<=9;i++)//遍历更高的优先级if(cnt[i]!=0)//有更高优先级的任务等待打印return true;//不打印return false;//打印
}
void solve(){memset(cnt,0,sizeof(cnt));//清空优先级计数queue<task>q;cin>>n>>m;for(int i=0,p;i<n;i++){//id从0开始cin>>p;//输入优先级cnt[p]++;//增加对应优先级任务的计数q.push({i,p});//存储任务}int ans=0;while(!q.empty()){auto[id,p]=q.front();//取出队首q.pop();if(check(p))//不可以打印q.push({id,p});else{ans++;//增加做任务的次数cnt[p]--;//减少对应优先级任务的计数if(id==m){//是否为关注任务cout<<ans<<endl;return;}}}
}
int main(){cin>>t;while(t--)solve();return 0;
}

3. 小组队列

题目描述

m m m 个小组, n n n 个元素,每个元素属于且仅属于一个小组。
支持以下操作:

  • push x:使元素 x x x 进队,如果前边有 x x x 所属小组的元素, x x x 会排到自己小组最后一个元素的下一个位置,否则 x x x 排到整个队列最后的位置。
  • pop:出队,弹出队头并输出出队元素,出队的方式和普通队列相同,即排在前边的元素先出队。

输入描述

第一行有两个正整数 n , m n,m n,m,分别表示元素个数和小组个数,元素和小组均从 0 0 0 开始编号。
接下来一行 n n n 个非负整数 A i A_i Ai ,表示元素 i i i 所在的小组。
接下来一行一个正整数 T T T,表示操作数。
接下来 T T T 行,每行为一个操作。

输出描述

对于每个出队操作输出一行,为出队的元素。

样例1

输入

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

输出

2
3
0

提示

对于 30 % 30\% 30% 的数据, 1 ≤ n ≤ 100 , 1 ≤ m ≤ 10 , T ≤ 50 1≤n≤100,1≤m≤10,T≤50 1n100,1m10,T50
对于 100 % 100\% 100% 的数据, 1 ≤ n ≤ 1 0 5 , 1 ≤ m ≤ 300 , T ≤ 1 0 5 1≤n≤10^5,1≤m≤300,T≤10^5 1n105,1m300,T105,输入保证操作合法。

参考答案

#include<bits/stdc++.h>
using namespace std;
int t,n,m;
int a[100010];//每个人所属的队伍编号
queue<int>q;//队伍编号
queue<int>team[305];//队伍成员的队列数组
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所属队伍之前没有人入队q.push(a[x]);//将x所属队伍入队team[a[x]].push(x);//将x入队到对应队伍中} else {int x=q.front();//取出下一个要出队的队伍编号cout<<team[x].front()<<endl;//输出当前队首队伍中的第一个人的编号team[x].pop();//将当前队首队伍中的第一个人出队if(team[x].empty())//如果当前队首队伍中没有人了q.pop();//将当前队伍从队伍中删除}}return 0;
}

4. 日志统计 2.0

题目描述

小猴维护着一个程序员论坛。现在他收集了一份"点赞"日志,日志共有 N N N 行。其中每一行的格式是 ts id,表示在 t s \tt ts ts 时刻编号 i d \tt id id 的帖子收到一个"赞"。
现在小猴想统计有哪些帖子曾经是"热帖"。如果一个帖子曾在任意一个长度为 D D D 的时间段内收到不少于 K K K 个赞,小猴就认为这个帖子曾是"热帖"。
具体来说,如果存在某个时刻 T T T 满足该帖在 [ T , T + D ) [T,T+D) [T,T+D) 这段时间内(注意是左闭右开区间)收到不少于 K K K 个赞,该帖就曾是"热帖"。
除此之外,小猴还想知道哪个长度为 D D D 的时间段内的"热帖"种类最多,小猴称这个段时间为"黄金时间段"。这里统计帖子的出现次数只能使用该黄金时间段内的帖子,也就是说在黄金时间段内的帖子之前可能是"热帖",但是仅在黄金时间段内却可能不是"热帖"。
例如, N = 5 , D = 3 , K = 2 N=5,D=3,K=2 N=5,D=3,K=2 N N N 个帖子依次是 { 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} 的形式依次给出每个帖子的信息),那么在黄金时间段 [ 2 , 4 ] [2,4] [2,4] 内“热帖”的个数只有 1 1 1 个,其中编号为 1 1 1 的帖子在时间 [ 2 , 4 ] [2,4] [2,4] 中只出现了一次,虽然它曾经是"热帖"。
给定日志,请你帮助小猴统计出"黄金时间段"内的"热帖"种类数,以及输出所有曾是"热帖"的帖子编号。

输入描述

第一行包含三个整数 N , D , K N,D,K N,D,K
以下 N N N 行每行一条日志,包含两个整数 t s , i d \tt ts,id ts,id

输出描述

输出两行:
第一行,表示"黄金时间段"内的帖子种类数。
第二行,按从小到大的顺序输出热帖 i d \tt id id。每个 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

提示

对于 50 % 50\% 50% 的数据, 1 ≤ K ≤ N ≤ 1000 1≤K≤N≤1000 1KN1000
对于 100 % 100\% 100% 的数据, 1 ≤ K ≤ N ≤ 2 × 1 0 5 , 0 ≤ i d , t s 1≤K≤N≤2×10^5,0≤\tt{id,ts} 1KN2×105,0id,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;//某个长度为D的时间段的热搜情况
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)//点赞个数刚好是k条cnt--;//减少热帖个数sum[q.front().id]--;q.pop();}//把当前记录放入日志q.push(logs[i]);sum[logs[i].id]++;if(sum[logs[i].id]==k){cnt++;//新增一个热帖isHot[logs[i].id]=1;//标记为热帖}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 到了北京,领了科技创新奖,但是她还是觉得不满意。原因是:他发现很多人都和她一样获了科技创新奖,特别是其中的某些人,还获得了另一个奖项——特殊贡献奖。而越多的人获得了两个奖项,Miss Medusa就会越眼红。于是她决定统计有哪些人获得了两个奖项,来知道自己有多眼红。

输入格式

第一行两个整数 n , m n, m n,m,表示有 n n n 个人获得科技创新奖, m m m 个人获得特殊贡献奖。
第二行 n n n 个正整数,表示获得科技创新奖的人的编号。
第三行 m m m 个正整数,表示获得特殊贡献奖的人的编号。

输出格式

输出一行,为获得两个奖项的人的编号,按在科技创新奖获奖名单中的先后次序输出。

样例1

输入

4 3
2 15 6 8
8 9 2

输出

2 8

提示

对于 60 % 60\% 60% 的数据, 0 ≤ n , m ≤ 1000 0 \leq n, m \leq 1000 0n,m1000,获得奖项的人的编号 < 2 × 1 0 9 \lt 2 \times 10^9 <2×109
对于 100 % 100\% 100% 的数据, 0 ≤ n , m ≤ 1 0 5 0 \leq n, m \leq 10^5 0n,m105,获得奖项的人的编号 < 2 × 1 0 9 \lt 2 \times 10^9 <2×109
输入数据保证第二行任意两个数不同,第三行任意两个数不同。

参考答案

#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. 美食评委

题目描述

一年一度的美食比赛火热进行中,小猴作为评委需要对一些选手的菜品打分,所有菜品从左到右排成一排,编号依次为 1 ∼ n 1∼n 1n,第 i i i 个菜品的美味值是 d i d_i di。小猴可以自己选择对那些选手的菜品进行打分,但是必须满足以下两个条件:

  • 至少选择两位选手的菜品;
  • 选择的第一个选手和最后一位选手的菜品美味值必须相同。


小猴所选的第一个菜品和最后一个菜品之间(不包含第一个和最后一个菜品)的部分菜品可以选择不要,请你帮助小猴计算所选菜品美味值的总和的最大值是多少?

输入描述

第一行一个整数 n n n
第二行 n n n 个整数 d i d_i di

输出描述

一行一个整数,表示所选菜品美味值的总和的最大值。

样例1

输入

5
1 2 3 1 2

输出

8

样例2

输入

5
100 1 1 -3 1

输出

3

提示

40 % 40\% 40% 的数据保证: 2 ≤ n ≤ 5000 , d i > 0 2≤n≤5000,d_i>0 2n5000,di>0
100 % 100\% 100% 的数据保证: 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 2n2×105,109di109


http://www.ppmy.cn/news/1547761.html

相关文章

Prompt设计技巧和高级PE

目录 PD and PE:INTRODUCTION AND ADVANCED METHODS 1.Instructions 2.Basic Knowledge - Prompt 2.1 Prompt 2.2 Prompt Cases 2.3 Prompt Engineering 3. LLM 的局限 4. Prompt 设计技巧和方法 4.1 Chain of thought prompting 4.2 Encouraging the model to be fa…

postgresql 创建序列

序列 序列是什么&#xff1f; 序列对象&#xff08;也叫序列生成器&#xff09;就是用CREATE SEQUENCE 创建的特殊的单行表。一个序列对象通常用于为行或者表生成唯一的标识符。 在持久层框架如Hibernate(JPA)、Mybatis中经常会用到Sequences(函数)去创建主键值&#xff0c;Po…

ThriveX 博客管理系统前后端项目部署教程

前端 前端项目地址&#xff1a;https://github.com/LiuYuYang01/ThriveX-Blog 控制端项目地址&#xff1a;https://github.com/LiuYuYang01/ThriveX-Admin Vercel 首先以 Vercel 进行部署&#xff0c;两种方式部署都是一样的&#xff0c;我们以前端项目进行演示 首先我们先…

git 同步上游仓库到远端仓库

首先知道什么是本地仓库&#xff0c;远端仓库&#xff0c;上游仓库 本地仓库&#xff1a;你从远端仓库克隆到本地 PC 上的仓库 远端仓库&#xff1a;从上游仓库 fork 过来的仓库&#xff0c;可以理解为自己的仓库 上游仓库&#xff1a;公司的仓库&#xff0c;所有权不在于你 当…

adb 如何通过wifi连接手机

1. 电脑通过USB线连接手机 1.1手机开启开发者模式 以小米手机为例&#xff1a;连续点击OS版本系统&#xff08;设置–>我的设备–>全部参数&#xff09; 1.2在开发者模式下&#xff0c;启动允许USB安装与USB调试 操作步骤&#xff1a;设置>更多设置>开发者选项&g…

鸿蒙实战:页面跳转

文章目录 1. 实战概述2. 实现步骤2.1 创建项目2.2 准备图片素材2.3 编写首页代码2.4 创建第二个页面 3. 测试效果4. 实战总结 1. 实战概述 实战概述&#xff1a;本实战通过ArkUI框架&#xff0c;在鸿蒙系统上开发了一个简单的两页面应用。首页显示问候语和“下一页”按钮&…

简易的学生信息管理系统制作——C语言实现

菜单代码 #include "head.h" int main(int argc, const char *argv[]) {int ch,k;//登录注册while(1){printf("\t1、注册\n");printf("\t2、登录\n");printf("\t0、退出\n");printf("请输入你的选择&#xff1a;");scanf(&…

npm、yarn、pnpm 切换查看镜像源笔记

默认的官方镜像&#xff1a;https://registry.npmjs.org&#xff0c;切换国内淘宝镜像&#xff0c;访问下载更快。 一、npm设置 npm config set registry https://registry.npmmirror.com/2、查看源 npm config get registry3、切回官方镜像 npm config set registry https:…