蓝桥杯16天刷题计划一一Day01（STL练习）

作者：blue

时间：2025.3.26

[TOC]

P1540 [NOIP 2010 提高组] 机器翻译 - 洛谷 (luogu.com.cn)

这是一道很典型的队列题目，因为题目中很明显的说：“若内存中已存入 M 个单词，软件会清空最早进入内存的那个单词，腾出单元来，存放新单词。”非常符合队列先进先出的思想，所以我们可以用队列来模仿内存。

然后值得考虑的一个问题是：我们如何快速的判断当前这个单词是否在内存中呢？

如果遍历内存的话，时间的消耗是O(m)的，但我们注意到题目条件

“第二行为 N 个非负整数，按照文章的顺序，每个数（大小不超过 1000）代表一个英文单词。”

这说明最多也就只有1000个单词（单词都是以非负整数的形式表示），所以，我们可以使用Hash表来记录当前内存中单词是否存在，存在为1，不存在为0，这样我们维护内存时同时维护Hash表，这样就可以用O(1)的时间来判断单词是否在内存中了。

#include <iostream>
#include <queue>
using namespace std;
queue<int> mem; //队列模拟内存 
int Hash[1005]; //用于快速判断内存中是否存在单词 
int main()
{
   
    int m,n;
    int ans=0;
    int letter;//单词 
    cin>>m>>n;
    for(int i=1;i<=n;i++){
   
        cin>>letter;
        if(Hash[letter]==0){
   //内存中没有 
            ans++;//查字典
            mem.push(letter);
            Hash[letter]=1;//放入内存 
            //注意无论内存满没满，都要先放进队列里，然后再对内存做判断 
            if(mem.size()>m){
   //内存满了
                int temp=mem.front();
                Hash[temp]=0;
                mem.pop();//清空最早进入内存的单词  
            } 
        } 
    }
    cout<<ans; 
    return 0;
}

P1996 约瑟夫问题 - 洛谷 (luogu.com.cn)

经典的约瑟夫环问题，在这里我们选择采用list来模拟这个过程，整个过程比较简单，主要要掌握list的增删与迭代器遍历的使用。

#include <iostream>
#include <list>
using namespace std;
list<int> circle;
int main()
{
       
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) circle.push_back(i);//围成一圈 
    list<int>::iterator it = circle.begin();//迭代器 
    while(circle.size()>1){
   
        for(int i=1;i<m;i++){
   //模拟报数过程,注意这里自己也算个数,所以<m即可 
            it++;
            if(it==circle.end()) it=circle.begin();//到末尾了就重新去到头 
        } 
        cout<<*it<<" ";
        list<int>::iterator next = ++it;//记录下一个将指向的位置 
        if(next==circle.end()) next=circle.begin();
        circle.erase(--it);//删除当前位置需要的数 
        it=next;
    }
    cout<<*it;
    return 0;
}

P1886 滑动窗口 /【模板】单调队列 - 洛谷 (luogu.com.cn)

这题是利用单调队列解决滑动窗口的模板题。我们这里用双端队列（deque）来模拟滑动窗，双端队列的特点是可以从头出也可以从尾出。我们以维护窗口最小值的代码为例，来讲解一下维护的过程：

首先看队列是否为空，如果空的话，当前元素就可以入队（不过在这里我们在队列中存储下标即可，为什么呢？因为这样方便我们判断哪些数超出了窗口范围了），

如果队不空，就要做判断，如果当前队尾元素比当前i指向的元素小，那就保留，否则就要出队，给i指向的元素让位，在这种维护规则下，我们队列里的数据，从队头到队尾，就都是单调递增的，故而称之为单调队列，那谁是当前窗口最小的呢？显然是队头。

那么如何判断当前队头是不是在窗口内呢？因为i是窗口现在扫描到的最新的位置，k是窗口长度，所以窗口的首位置就应该是i-k+1，所以如果队头比i-k+1还小，那就肯定不在窗口内，直接从队头出队。

i=k时第一个窗口就填满了，故而i>=k时窗口总是满的，可以输出。

#include <iostream>
#include <queue>
using namespace std;
const int N=1e6+10;
int a[N];
deque<int> dq;//双端队列模拟滑动窗 
int main()
{
       
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];

    //维护最窗口最小值
    for(int i=1;i<=n;i++){
   
        while(!dq.empty()&&a[dq.back()]>a[i]) dq.pop_back();
        dq.push_back(i);
        while(dq.front()<i-k+1) dq.pop_front();
        if(i>=k) cout<<a[dq.front()]<<" ";//窗口已经满了，可以输出
    } 
    cout<<endl;
    dq.clear();//清空队列 
    //维护窗口最大值
    for(int i=1;i<=n;i++){
   
        while(!dq.empty()&&a[dq.back()]<a[i]) dq.pop_back();
        dq.push_back(i);
        while(dq.front()<i-k+1) dq.pop_front();
        if(i>=k) cout<<a[dq.front()]<<" ";//窗口已经满了
    } 
    return 0;    
}

P2947 [USACO09MAR] Look Up S - 洛谷 (luogu.com.cn)

本题是单调栈经典题目

单调栈的应用场景：通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了。

感觉单调栈的想法和单调队列的很像，题目要求向右看齐，即找任意一个元素的右边第一个比自己大的元素，这时我们就可以利用单调栈。

首先，找右边比自己大的就倒序遍历数据，在栈不空的情况下，如果当前元素大于栈顶元素，那么栈顶元素就不是其仰望的对象，故栈顶元素出栈，直到栈顶元素比当前元素大了，那此时栈顶元素即为当前元素右边最近的仰望对象，这样我们维护出来的栈从栈顶到栈底总是单调递增的，故而称为单调栈。请读者自己模拟一遍这个过程，就会非常清楚，单调栈在其中的应用。

#include <iostream>
#include <stack>
using namespace std;
const int N=1e5+10;
int h[N];//存储奶牛们的身高 
int ans[N];//存放答案
stack<int> st;//单调栈 
int main()
{
   
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>h[i];
    for(int i=n;i>=1;i--){
   //因为是向右看齐，所以我们倒序遍历 
        //注意是找最近的仰望对象，所以等于的也要出栈 
        while(!st.empty()&&h[i]>=h[st.top()]) st.pop();
        if(st.empty()) ans[i]=0;//栈空，证明没有仰望对象了
        else ans[i]=st.top();//栈不空，说明现在栈顶是它的仰望对象 
        st.push(i);//入栈，存的是下标
    } 
    for(int i=1;i<=n;i++) cout<<ans[i]<<endl; 
    return 0; 
}

P1090 [NOIP 2004 提高组] 合并果子 - 洛谷 (luogu.com.cn)

本题是优先队列的经典应用。

题目要求我们找出能将所有堆果子合并为一堆果子，并且要求体力值最小。读完题目我们不难发现，最佳的方案其实就是每次选取两堆最小数目的果子进行合并，那我们如何找到两堆最小的果子呢，第一个想法是排序，但是每次都要排序实在是太过麻烦，而且每次合并后又会产生新的一堆果子，所以如果有这么一个数据结构，我每次放数据进去就会自动排序就好了。

诶！还真有，优先队列可以做到，它可以进行自动排序，对于这道题，我们设置一个小顶堆，每次找两个最小数量的果子，就是取两次堆顶，然后合并后放回堆中，直到堆里只有一个元素，就是剩一堆的时候，就结束。

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main()
{
   
    int n,x;
    int ans=0;
    priority_queue<int,vector<int>,greater<int> > q;//小顶堆 
    cin>>n;
    while(n--)//输入 
    {
   
        cin>>x;
        q.push(x); 
    } 
    while(q.size()!=1)//当只剩下一堆果子时循环结束 
    {
   
        int a=q.top(); //从堆顶取出最小的两堆合并 
        q.pop();
        int b=q.top();
        q.pop();
        ans+=a+b;
        q.push(a+b);
    }
    cout<<ans;
    return 0;
}

P2085 最小函数值 - 洛谷 (luogu.com.cn)

优先队列太重要了，我们再练习一道有关优先队列结构体排序的题目。

这道题的意思其实就是给你N条带A，B，C参数的式子，然后让你不断变化变量x（从1开始，每次自增1），然后找出m个最小的值。

所以最主要的地方还是在找最小，我们可以这样做，设计一个node结构体来存储式子的ABC参数，和变量X与函数值Y，然后创建一个节点类型为node类型的优先队列（所以我们要掌握，结构体优先队列怎么控制小顶堆），然后我们每次取堆顶，因为堆顶是最小的，然后取出来之后自增变量x，然后更新y，重新放回堆里。然后重复这个过程。

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
typedef struct node{
    
    int a;
    int b;
    int c;
    int x;
    int y;//函数值 
}node;
bool operator <(const node &a,const node &b){
   
    return a.y>b.y;//最小值优先 
} 
int fun(node p){
   
    return p.a*p.x*p.x+p.b*p.x+p.c;
}
const int N=1e4+5;
node a[N];
int main()
{
   
    int n,m; 
    vector<int> ans;
    priority_queue<node> que;//找最小函数值 
    cin>>n>>m;
    for(int i=0;i<n;i++){
   
        cin>>a[i].a>>a[i].b>>a[i].c;
        a[i].x=1;
        a[i].y=fun(a[i]);
        que.push(a[i]);
    }
    while(ans.size()<m){
   
        node temp=que.top();
        que.pop();
        ans.push_back(temp.y);
        temp.x++;
        temp.y=fun(temp);
        que.push(temp);
    }
    for(int i=0;i<ans.size();i++) cout<<ans[i]<<" ";
    return 0;
}