第二周STL基础
P3156 【深基15.例1】询问学号
题目理解
我们可以把这个题目想象成一个 “学生学号登记与查询” 的场景： 有 n 名同学按顺序进入教室，我们需要把他们的学号 “登记” 下来。
之后老师会问 m 次：“第 i 个进教室的同学学号是多少？” 我们要快速给出答案。
#include<bits/stdc++.h>
using namespace std;
int a[2000001];//注意不要把数组开在主函数里
int main()
{
int n,m,x;
cin >> n >> m;
for(int i=1;i<=n;i++)
cin >> a[i];
for(int i=1;i<=m;i++)
{
cin >> x;//询问学号
cout << a[x] <<'\n';
}
}
P1104 生日
题目理解
这个题目是一个 “按生日排序”的问题：我们需要根据同学的出生日期，将他们按年龄从大到小（即生日从早到晚）排序。如果生日相同，输入靠后的同学要先输出。
简单来说，生日越早（年份越小、月份越小、日期越小），年龄越大，要排在前面；如果生日完全相同，后输入的同学排在前面。
方法一：使用结构体和自定义排序规则
#include<bits/stdc++.h>
using namespace std;
// 定义long long为int，简化大整数类型的书写
#define int long long
// 结构体node：存储每个对象的完整信息
struct node{
int n,y,r,id; //分别表示年月日和输入顺序
string s; // 姓名
};
// 自定义排序规则函数cmp，用于sort函数，决定两个元素x和y的前后顺序
bool cmp(node x, node y){
// 第一步：先按年份排序，年份小的（更早）排在前面
if(x.n != y.n) return x.n < y.n;
// 第二步：年份相同则按月份排序，月份小的排在前面
else if(x.y != y.y) return x.y < y.y;
// 第三步：月份相同则按日期排序，日期小的排在前面
else if(x.r != y.r) return x.r < y.r;
// 第四步：年月日都相同，输入顺序靠后的（id大的）排在前面
return x.id > y.id;
}
// 定义结构体数组，存储所有对象（大小200足够处理小规模数据）
node a[200];
// 主函数（用signed代替int，配合#define int long long避免编译警告）
signed main(){
int n;
cin >> n;
for(int i = 1; i <= n; i++){
// 依次读入姓名、年、月、日
cin >> a[i].s >> a[i].n >> a[i].y >> a[i].r;
a[i].id = i; // 记录输入顺序（第i个输入的id为i）
}
// 对数组a进行排序，从a[1]到a[n]，使用自定义规则cmp
sort(a + 1, a + n + 1, cmp);
// 按排序后的顺序输出每个对象的姓名
for(int i = 1; i <= n; i++){
cout << a[i].s << '\n';
}
}
方法二：都是基本语句
核心：构造一个唯一的"排序键"，让map自动按规则排序
键的构成：年1000000 + 月10000 + 日*100 + (n-i)
解释：
-
年、月、日放大后相加，保证先按年排序，再按月，再按日（日期早的键更小）
-
(n-i)确保生日相同时，后输入的人键更大（因为i越小，n-i越大）
例如n=3，i=0时n-i=3，i=1时n-i=2，i=2时n-i=1，后输入的i更大，n-i更小？
修正：实际是i越大（越晚输入），n-i越小，所以相同生日时，键小的先输出，即后输入的先输出
#include<bits/stdc++.h>
using namespace std;
// 定义int为long long类型，避免大整数溢出
#define int long long
signed main(){
int n;
cin >> n;
// 定义一个map（键值对容器），键为整数，值为字符串
//map会自动按照键的从小到大排序，这是核心用法
map<int,string> p;
for(int i = 0; i < n; i++){
string v; // 存储姓名
int a,b,c; // 存储年、月、日
cin >> v >> a >> b >> c;
p[a*1000000 + b*10000 + c*100 + (n - i)] = v;
}
// 遍历map，按键的从小到大顺序输出姓名
// 因为map自动排序，此时输出顺序就是符合要求的排序结果
for(auto &it : p){
cout << it.second << '\n'; // it.second是map中存储的姓名
}
}
P2952 [USACO09OPEN] Cow Line S
题目理解
这道题可以理解为一个 “双端队列的模拟问题”，核心是处理一系列对队列的 “插入” 和 “删除” 操作，具体场景如下：
有一个特殊的队列，支持从左边和右边两个方向进行操作。
总共有 n 条操作指令，每条指令分为两类：
加入指令（A 开头）：
格式为 A R 或 A L，表示往队列的右边（R） 或左边（L） 加入一头新奶牛。每头奶牛有唯一编号，按加入顺序依次为 1、2、3……
删除指令（D 开头）：
格式为 D L x 或 D R x，表示从队列的左边（L） 或右边（R） 连续删除 x 头奶牛（如果队列已空，则无需操作）。
最终需要按从左到右的顺序，输出队列中剩余奶牛的编号。
简单来说，就是模拟一个 “两头都能进出” 的队伍，根据指令完成奶牛的加入和离开，最后输出剩下的奶牛编号即可。双端队列（deque）的特性正好适合处理这种 “两端操作” 的场景。
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >>n;
// 双端队列deque，支持从队头和队尾高效插入、删除操作
deque<int> q;
// 计数器cnt，用于生成奶牛的编号（按加入顺序1、2、3...递增）
int cnt = 0;
for(int i = 1;i <= n;i++){
char f;
cin >> f;
if(f == 'A'){ // 处理“加入队列”的指令
cnt++; // 生成新的奶牛编号
char a;
cin >> a;
if(a == 'R'){ // 从右边加入即队列的后面
q.push_back(cnt);
}
else{ // 从左边加入即队列的前面
q.push_front(cnt);
}
}
else { // 处理“离开队列”的指令
char a;
int x;
cin >> a >> x;
if(a == 'L'){ // 从左边离开x头奶牛
for(int j = 0;j < x;j++){
if(!q.empty()) q.pop_front();
}
}
else{ // 从右边离开x头奶牛
for(int j = 0;j < x;j++){
if(!q.empty()) q.pop_back();
}
}
}
}
// 按从左到右的顺序输出最终队列中的奶牛编号
for(auto it:q){
cout << it << '\n';
}
}
P5266 【深基17.例6】学籍管理
题目理解
这道题要求设计一个学籍管理系统，支持四种操作，分别是插入 / 修改学生信息、查询学生成绩、删除学生信息、统计学生数量。所有操作的总次数不超过 10⁵次，需要高效处理这些操作。
#include<bits/stdc++.h>
using namespace std;
#define int long long // 定义int为long long类型，适配可能的大数值场景
signed main(){
int n;
cin >> n;
// 定义无序映射（哈希表）p，键为学生姓名（string），值为成绩（int）
// 用于快速存储和查找学生信息，平均时间复杂度O(1)
unordered_map<string,int> p;
for(int i = 0;i < n;i++){
int f; // 操作类型标识（1-插入/修改，2-查询，3-删除，4-统计数量）
string s; // 存储学生姓名
cin >> f ; // 读取操作类型
if(f == 1){ // 操作1：插入或修改学生成绩
int sco; // 学生成绩
cin >> s >> sco; // 读取姓名和成绩
p[s] = sco; // 若姓名存在则更新成绩，不存在则新增记录
cout << "OK"; // 输出操作成功提示
}
else if(f == 2){ // 操作2：查询学生成绩
cin >> s; // 读取要查询的姓名
if(p.count(s) == 0) // 判断姓名是否存在（count返回键的出现次数，0表示不存在）
cout << "Not found"; // 不存在则输出提示
else
cout << p[s]; // 存在则输出对应成绩
}
else if(f == 3){ // 操作3：删除学生信息
cin >> s; // 读取要删除的姓名
if(p.count(s) == 0) // 判断姓名是否存在
cout << "Not found"; // 不存在则输出提示
else {
p.erase(s); // 存在则删除该记录（erase移除键值对）
cout << "Deleted successfully"; // 输出删除成功提示
}
}
else { // 操作4：统计当前学生数量
cout << p.size(); // size()返回映射中键值对的数量，即当前学生总数
}
cout << '\n'; // 每个操作的输出后换行
}
}
P1125 [NOIP 2008 提高组] 笨小猴
题目理解
输入：一个由小写字母组成的单词（字符串）。
操作步骤：
统计单词中每个字母的出现次数（例如 "abac" 中 'a' 出现 2 次，'b' 出现 1 次，'c' 出现 1 次）。
找出这些出现次数中的最大值和最小值。
计算 “最大值 - 最小值” 的差值，判断这个差值是否为质数（大于等于 2 且只能被 1 和自身整除的数）。
输出结果：
如果差值是质数，输出 “Lucky Word” 并换行，再输出这个差值。
如果差值不是质数（或不存在有效差值，比如所有字母出现次数相同且差值为 0），输出 “No Answer” 并换行，再输出 0。
简单来说，就是通过分析单词中字母的出现频率差异，判断这个差异是否为质数，从而确定该单词是否为 “幸运单词”。
#include<bits/stdc++.h>
using namespace std;
// 判断一个数是否为质数的函数
bool pd(int x){
if(x < 2) return false; // 小于2的数不是质数
for(int i = 2;i < x;i++){
if(x%i==0) return false; // 能被i整除，不是质数
}
return true; // 是质数
}
int main(){
string s;
cin >> s;
int p[30] = {0}; // 数组p用于统计每个小写字母的出现次数，下标0-25对应a-z
for(char i : s){
p[i-'a']++; // 统计每个字母的出现次数，例如 'a'-'a'=0，对应p[0]
}
int ma = 0,mi = INT_MAX; // ma记录出现次数最多的次数，mi记录出现次数最少的次数
for(int i = 0;i < 26;i++){
if(p[i] == 0) continue; // 跳过出现次数为0的字母
ma = max(p[i],ma); // 更新最大次数
mi = min(p[i],mi); // 更新最小次数
}
// 判断最大次数与最小次数的差是否为质数
if(pd(ma-mi)){
cout << "Lucky Word" << '\n' << ma - mi << '\n';
}
else cout << "No Answer" << '\n' << 0 << '\n';
}
B3614 【模板】栈
题目理解
这道题要求我们实现一个栈数据结构，并支持四种操作：
push(x)：向栈中添加一个元素x。
pop()：弹出栈顶元素；若栈为空，输出Empty。
query()：查询栈顶元素；若栈为空，输出Anguei!。
size()：输出栈中元素的个数。
同时题目包含多组测试数据：首先输入数据组数T，每组数据先输入操作次数n，再输入n条操作指令，最后按要求输出每组操作的结果。
#include<bits/stdc++.h>
using namespace std;
#define int long long // 定义int为long long类型，适配可能的大数值场景
signed main(){
int T;
cin >> T; // 读取测试数据组数T
while(T--){ // 循环处理每组测试数据
int n;
cin >> n; // 读取当前组的操作次数n
// 定义栈p，存储字符串类型（因为要处理push的元素和输出格式）
stack<string> p;//放到while循环里面，否则上一个样例数据还在
for(int i = 0;i < n;i++){
string s;
cin >> s; // 读取操作类型
if(s == "push"){ // 处理push操作
string x;
cin >> x; // 读取要入栈的元素x
p.push(x); // 将x压入栈顶
}
else if(s == "pop"){ // 处理pop操作
if(p.empty()) // 若栈为空
cout <<"Empty" << '\n'; // 输出Empty
else
p.pop(); // 否则弹出栈顶元素
}
else if(s == "query"){ // 处理query操作
if(p.empty()) // 若栈为空
cout << "Anguei!"; // 输出Anguei!
else
cout << p.top(); // 否则输出栈顶元素
cout << '\n'; // 操作输出换行
}
else { // 处理size操作
cout << p.size(); // 输出栈中元素个数
cout << '\n'; // 操作输出换行
}
}
}
}
P4387 【深基15.习9】验证栈序列
题目理解
这道题要求我们判断给定的入栈序列和出栈序列是否匹配，即是否存在一种合法的栈操作顺序，使得入栈序列按给定顺序入栈后，能按照出栈序列的顺序出栈。
题目包含多组测试数据：首先输入询问次数q，每组询问包含序列长度n、入栈序列pushed和出栈序列popped，我们需要对每组数据判断是否匹配，输出Yes或No。
#include<bits/stdc++.h>
using namespace std;
int main(){
int T;
cin >> T; // 读取询问次数T
while(T--){ // 循环处理每组询问
int n;
cin >> n; // 读取当前组的序列长度n
int a[n+1],b[n+1]; // 分别存储入栈序列和出栈序列
for(int i = 0;i < n;i++) cin >> a[i]; // 读入栈序列
for(int i = 0;i < n;i++) cin >> b[i]; // 读出栈序列
stack<int> q; // 定义栈q，用于模拟入栈出栈过程
int t = 0; // 出栈序列的指针，记录当前要匹配的出栈元素位置
for(int i = 0;i < n;i++){ // 按入栈序列依次入栈
q.push(a[i]);
// 当栈不为空、出栈指针未越界且栈顶元素与当前出栈序列元素匹配时，出栈
while(!q.empty()&&t < n&&q.top() == b[t]){
q.pop(); // 弹出栈顶元素
t++; // 出栈指针后移
}
}
// 若栈为空，说明所有元素都能按出栈序列匹配，输出Yes；否则输出No
if(!q.empty()) cout << "No";
else cout << "Yes";
cout <<'\n';
}
}
P1102 A-B 数对
题目理解
#include<bits/stdc++.h>
using namespace std;
#define int long long // 定义int为long long类型，避免数值溢出
signed main(){
int n,c;
cin >> n >> c; // 读取数列长度n和给定正整数c
unordered_map<int,int> p; // 哈希表p，用于统计每个数字的出现次数
for(int i = 0;i < n;i++){
int x;
cin >> x; // 读取数列中的每个数字
p[x]++; // 统计数字x的出现次数
}
int sum = 0; // 存储满足A - B = C的数对个数
for(auto &it:p){ // 遍历哈希表中的每个键值对（数字及其出现次数）
// 判断是否存在数字it.first + c（即A = B + C）
if(p.count(it.first + c))
// 数对个数为A的出现次数乘以B的出现次数
sum += it.second * p[it.first + c];
}
cout << sum <<'\n'; // 输出满足条件的数对总数
}
P5250 【深基17.例5】木材仓库
题目理解
#include<bits/stdc++.h>
using namespace std;
#define int long long // 定义int为long long类型，避免数值溢出
set<int>::iterator x, z, y; // 定义set迭代器，用于遍历和操作集合
signed main(){
ios::sync_with_stdio(0); // 关闭同步，加速输入输出
cin.tie(0),cout.tie(0); // 解除cin和cout的绑定，进一步加速
int n;
cin >> n; // 读取操作次数
set<int> v; // 用set存储木材长度，自动保持有序
for(int i = 0;i < n;i++){
int f,l;
cin >> f >> l; // f是操作类型，l是木材长度
if(f == 1){ // 操作1：进货
// insert返回pair<iterator, bool>，second为true表示插入成功
if(!v.insert(l).second){
cout << "Already Exist" << '\n'; // 木材已存在，输出提示
}
}
else{ // 操作2：出货
if(v.empty()) { // 仓库为空
cout << "Empty";
}
else {
// 先检查是否存在长度为l的木材
if(v.count(l)) {
cout << l << '\n'; // 存在则直接输出并删除
v.erase(v.find(l));
continue;
}
// 查找第一个不小于l的木材位置
auto z = y = x = v.lower_bound(l);
if(x == v.begin()){ // 所有木材都大于l，取最小的（最接近的）
cout << *x;
v.erase(x);
}
else if(x == v.end()){ // 所有木材都小于l，取最大的（最接近的）
cout << *(--z);
v.erase(z);
}
else { // 存在比l小和比l大的木材，比较哪个更接近
if(l-*(--z) > *x-l){ // 比l大的木材更接近
cout << *x;
v.erase(x);
}
else { // 比l小的木材更接近（或相等时取较短的）
cout << *(--y);
v.erase(y);
}
}
}
cout <<'\n';
}
}
}
P1090 [NOIP 2004 提高组] 合并果子
题目理解
这道题是一个最小体力消耗的合并问题，核心是通过合理的合并顺序，使总体力消耗最小。
场景：将多堆果子合并成一堆，每次合并两堆，消耗的体力是两堆重量之和。
目标：找到一种合并顺序，使得所有合并操作的体力消耗总和最小。 关键思路：每次选择当前重量最小的两堆进行合并，这样能保证每次合并的消耗尽可能小，从而总消耗最小（这是典型的 “哈夫曼编码” 思想的应用）。
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >>n; // 读取果子的种类数n
// 定义小根堆（优先队列），用于每次快速获取最小的两堆果子
priority_queue<int,vector<int>,greater<>> p;
for(int i = 0;i < n;i++){
int x;
cin >> x; // 读取每种果子的数目
p.push(x); // 将果子数目加入小根堆
}
int sum = 0; // 存储总体力消耗
while(p.size()>1){ // 当堆中果子堆数大于1时，继续合并
int a = p.top(); // 获取第一堆最小的果子数目
p.pop(); // 弹出该堆
int b = p.top(); // 获取第二堆最小的果子数目
p.pop(); // 弹出该堆
sum += a+b; // 累加本次合并的体力消耗
p.push(a+b); // 将合并后的新堆加入小根堆
}
cout << sum; // 输出最小的总体力消耗
}
