蓝桥杯寒假训练营第二次排位赛题解

A

顺子日期指的就是在日期的 yyyymmdd 表示法中，存在任意连续的三位数是一个顺子的日期。2022不是闰年，写个day数组，存12个月每个月的天数，循环可得出所有日期，接着可以在每个日期判断是否存在连续的3位数，若存在则该日期为顺子日期，结果+1

（当然填空题可以一个一个数出来直接输出答案）

代码一

#include <iostream>
using namespace std;
int day[13]={0,31,28,31,30,31,30,31,31,30,31,30,31}; //day[x]表示第x月
bool check(int q[]){//判断是否存在连续3位数
    for(int i=3;i<=5;i++)//2022mmdd前3个数必不能组成连续数，故从q[3]开始找
      if(q[i]==(q[i+1]-1)&&q[i+1]==(q[i+2]-1)){ 
        return true;
      }
    return false;
}
int main()
{ 
  int q[8]={2,0,2,2};//注意第一个数为数组第0位
  int res=0;
  for(int i=1;i<=12;i++){
      q[4]=i/10%10;
      q[5]=i%10;
      for(int j=1;j<=day[i];j++){
          q[6]=j/10%10;
          q[7]=j%10;
          if(check(q)){
            res++;
            // for(int i=0;i<8;i++)cout<<q[i]<<" ";
            // cout<<endl;
          }
      }
    }
    cout<<res;
  return 0;
}

代码二（输出结果直接打印）

#include <cstdio>
int main() {
    puts("14");
    return 0;
}

B

从箱子里取衣服，最上面的衣服总是后放进去的，后进先出用栈写，输入是out取衣服时，会从栈顶取衣服，直到栈顶为所求则停止取衣服，n次操作结束后输出栈顶即可

#include <iostream>
#include <stack> 
#include <string>
using namespace std;
int main()
{
  stack <string> a;
  int n;
  string op, cloth; 
  cin >> n;
  for(int i = 0; i < n; i++)
  {
    cin >> op >> cloth;
    if(op == "in")
        a.push(cloth);//放入衣服
    else if (op == "out"){
        while(a.top()!=cloth)//如果栈顶不为所求衣服直接出栈
            a.pop();
        a.pop();//退出循环的条件为a.top()==cloth，所以此时栈顶为所求,应弹出栈
    }

  }
  if (a.empty())
    cout << "Empty";
  else 
    cout << a.top();

  return 0;
}

C

5 7
0 0 * * * 0 0
0 0 * 0 * 0 0
* * * 0 * * 0
* 0 * * * 0 0
* * * 0 * * 0

根据该样例得图

黑色为障碍，白色为重要区域，因为洪水淹没，所以从最外层搜索，如果有空洪水就可以沿着空一直往里走，所以要dfs搜索一下(画叉号的是搜索有空的）

将所有外面能进来的格子填上数，如图空格子染蓝色。最后所有白色格子数就是最终答案

代码一

#include<bits/stdc++.h>
using namespace std;
int n,m,s=0;
int kx[5]={0,1,-1,0,0}; //设好方向
int ky[5]={0,0,0,1,-1};
int a[501][501];
void search(int x,int y){
    a[x][y]=2;//先标记2表示被淹没了
    for(int i=1;i<=4;i++){//向四个方向搜索 
        int x0=x+kx[i];
        int y0=y+ky[i];
        if(x0>0&&x0<=n&&y0>0&&y0<=m&&a[x0][y0]==0)search(x0,y0);
    }//如果新的数在整个数组范围内并且不是障碍(能走),那么就搜索从这个格子能走到其他哪些格子 
}
int main(){
    cin>>n>>m;
    char e;
    for(int i=1;i<=n;i++){//输入 
        for(int j=1;j<=m;j++){
            cin>>e;
            if(e=='*')a[i][j]=1;//如果是障碍就输入1 
            else a[i][j]=0;//可以过就是0 
        }
    }
    for(int i=1;i<=n;i++){//搜索第一列和最后一列的格子 
        if(a[i][1]==0)search(i,1);//如果有能过的就搜索 
        if(a[i][m]==0)search(i,m);
    }
    for(int i=1;i<=m;i++){//搜索第一行和最后一行的格子 
        if(a[1][i]==0)search(1,i);
        if(a[n][i]==0)search(n,i);
    }
    for(int i=1;i<=n;i++){//最后搜索整张图没有被淹的格子（0表示没淹没） 
        for(int j=1;j<=m;j++){
            if(a[i][j]==0)s++;
        }
    }
    cout<<s;//输出 
    return 0;
}

代码二（拓宽地图一圈，只搜索一次，剩下一样）

#include <bits/stdc++.h>
using namespace std;
int n, m;
const pair<int, int> dxy[]{{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
vector<vector<char>> mat;
void dfs(const int &x, const int &y) {
    mat[x][y] = '*';
    for(auto &&i : dxy) {
        auto &&dx = i.first + x, &&dy = i.second + y;
        if(dx < 0 or dy < 0 or dx >= n + 2 or dy >= m + 2 or mat[dx][dy] == '*')
            continue;
        dfs(dx, dy);
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    mat.resize(n + 2, vector<char>(m + 2, '0'));
    int ans{};
    for(auto &&i = 1; i <= n; ++i)
        for(auto && j = 1; j <= m; ++j)
            cin >> mat[i][j];
    dfs(0, 0);
    for (auto &&line : mat)
        for (auto &&cell : line)
            ans += cell == '0';
    cout << ans;
    return 0;
}

D

求区间 $l$ 到 $r$ 的最小值，用 $f_{ij}$ 表示从 $a_i$ 开始长度为 $2^j$ 的区间中的最小值

把区间 $l$ 到 $r$ 拆成可以用 $f_{ij}$ 表示的两部分，两部分的最小值即为区间最小值

#include <bits/stdc++.h>
#define Maxn 100010
using namespace std;
int n, m, a[Maxn], f[Maxn][33];
int Query(int l, int r) {
    int w = log2(r-l+1);
    return min(f[l][w], f[r - (1 << w) + 1][w]);
}

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        f[i][0] = a[i]; // f[i][j] ==> 从a[i]开始长度为 2^j 的区间中最小值 
    }
    for(int j = 1; j <= 20; ++j) {
        for(int i = 1; i <= n; ++i) {
            if(i + (1 << j) - 1 <= n) {
                f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
            }
        }
    }
    int l = 1,r = m;
    while(l <= n - m + 1 and r <= n) {
        printf("%d\n", Query(l, r));
        l++;r++;
    }
    return 0;
}

另一种方法，滑动窗口单调队列

P1886 滑动窗口 /【模板】单调队列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

后面我们也会介绍这种方法，这里直接给出代码，有兴趣可以先去学习

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    using i64 = long long;
    i64 n, m;
    cin >> n >> m;
    vector<i64> arr(n);
    for(auto &&i : arr)
        cin >> i;
    deque<i64> que;
    for(int i = 0; i < n; ++i) {
        while(not que.empty() and i - que.front() >= m)
            que.pop_front();
        while(not que.empty() and arr[que.back()] > arr[i])
            que.pop_back();
        que.emplace_back(i);
        if(i >= m - 1)
            cout << arr[que.front()] << '\n';
    }
    return 0;
}

E

从题目的难点主要在于快速将一个公民移到医疗队列的队首。我们希望，这个插入的时间复杂度最好能是 $O(1)$。但是无论是链表，队列还是栈这些 $O(1)$ 插入的数据结构，他们查找一个元素的时间的复杂度都是 $O(n)$ ，也就是说，将一个公民移动到队列首时，时间复杂度是 $O(n + 1)$，也就是 $O(n)$。

再看题目的数据，最大坏的情况会达到 $10^6 \times 10^6$ （当每次操作都是将最后一个元素添加到队首时），$O(n)$ 的时间复杂度妥妥的TLE。为此，我们需要优化我们的算法。

思路一

从上面的分析我们也可以知道，链表，队列，栈这些数据结构在实现医疗队列的时候慢是因为查找元素的过程，我们不妨想一想，要是我们不查找元素，直接插入元素到队首会不会更好呢。这样，我们的插入的时间复杂度就变成了 $O(1)$，速度便提上去了。但是，这样插入到队首，队列中还会存在这个元素，我们怎么知道这个元素是插入过的还是没插入过的呢，为此，我们还需要引入其他的方法来进行一个标记——公民的加急的次数。

怎么用呢？当我们每次进行服务时，我们可以检查一下我们当前服务的公民的加急的次数，如果它的加急次数和档案中不同的，那么我们就不对他服务，直接让他出队即可（这样就可以去掉移动后依然留在队伍中的旧公民了）。如果加急次数和档案中相同，我们再对其服务，这样，我们服务的对象，一定是真正需要服务的公民。

为此，我们只需要记录我们公民的加急次数即可。我们可以开一个长度为 $p$ 的数组（档案），这个数组（档案）储存了每个公民 $i$ 的加急次数 $m_i$ ，当一个公民 $j$ 的加急事件发生时，我们直接记录加急次数，随后将其直接插入队首即可。这样我们就实现了 $O(1)$ 的将一个公民移到医疗队列的队首。

AC代码如下

#include <bits/stdc++.h>
using namespace std;
using people = pair<int, int>; // 代表公民的结构体
#define num first              // 编号
#define times second           // 加急次数
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, p;
    cin >> n >> p;
    deque<people> q;        // 双端队列模拟医疗队列
    vector<int> m(p, 0);    // 储存公民加急次数的档案
    for (int i = 1; i <= p; i++)
        q.emplace_back(i, m[i]); // 初始化队伍，记录公民的编号和加急次数
    while (n--) {
        int opt;
        cin >> opt;
        if (opt == 1) {     // 服务队首公民时
            people one = q.front();
            q.pop_front();
            while (one.times != m[one.num]) {   //查询档案，信息对不上就让它出队（不加回）
                one = q.front();
                q.pop_front();
            }
            q.push_back(one);   // 直到信息正确，对其服务，加回队尾
        } else if (opt == 2) {  // 加急事件发生时
            int x;
            cin >> x;
            m[x]++;     // 该公民档案上的加急次数加一
            q.emplace_front(x, m[x]);    // 直接将该公民添加到队首
        } else {    // 查看队首真正需要服务的公民时
            people one = q.front();
            while (one.times != m[one.num]) {
                q.pop_front();
                one = q.front();
            }
            cout << one.num << '\n'; // 直到信息正确，打印其信息
        }
    }
    return 0;
}

思路二

既然我们知道，查询是这个题目TLE的核心原因，那么我们容易想到一个查询特别快的数据结构——数组。我们可以想到，如果我们可以将数组的 $O(1)$ 查询和链表的 $O(1)$ 插入结合，那么我们就可以实现一个非常完美的数据结构来实现医疗队列，而这个数据结构也就是我们的数组链表。

数组链表的数组体现在每个元素的地址都用一个指针（迭代器）数组储存下来了，这样我们查询一个元素的时候，我们直接访问数组即可查询。

数组链表的链表则体现在插入时，我们可以和普通的链表一样插入元素。不过需要注意的是，插入和删除元素的时候我们需要修改对应的数组索引，避免索引失效。

AC代码如下

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, p;
    cin >> n >> p;
    list<int> q;
    // 存放迭代器的数组
    vector<list<int>::iterator> arr(p + 1);
    for(auto &&i = 1; i <= p; ++i)
        arr[i] = q.insert(q.end(), i);  // push_back 并记录位置
    while(n--) {
        int opt;
        cin >> opt;
        if(opt == 1) {
            int tmp = q.front();
            q.pop_front();
            arr[tmp] = q.insert(q.end(), tmp);
        } else if(opt == 2) {
            int x;
            cin >> x;
            q.erase(arr[x]);    // 在就先删掉
            arr[x] = q.insert(q.begin(), x);    // push_front 并记录位置
        } else
            cout << q.front() << '\n';
    }
    return 0;
}