蓝桥杯刷题第二十三天

这篇具有很好参考价值的文章主要介绍了蓝桥杯刷题第二十三天。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

第一题:长草

题目描述
小明有一块空地,他将这块空地划分为 nm 列的小块,每行和每列的长度都为 1。
小明选了其中的一些小块空地,种上了草,其他小块仍然保持是空地。
这些草长得很快,每个月,草都会向外长出一些,如果一个小块种了草,则它将向自己的上、下、左、右四小块空地扩展,
这四小块空地都将变为有草的小块。请告诉小明,k 个月后空地上哪些地方有草。
输入描述
输入的第一行包含两个整数 n,m
接下来 n 行,每行包含 m 个字母,表示初始的空地状态,字母之间没有空格。如果为小数点,表示为空地,如果字母为 g,表示种了草。
接下来包含一个整数 k。 其中 2≤n,m≤1000,1≤k≤1000。
输出描述
输出 n 行,每行包含 m 个字母,表示 k 个月后空地的状态。如果为小数点,表示为空地,如果字母为 g,表示长了草。

dfs,对每个当前层的g进行长草,并且长出来的草都是下一层可以长的草

这样就可以确保每一层只对当前层进行操作

当然全变为g了,就不用继续了,直接break,这里要进行一下特判就行

好像不加也可以过,数据,,,

#include<iostream>
using namespace std;

const int N = 1010;
int n, m, k;
int ed[N][N];
char st[N][N];

bool check(){
  for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++)
      if(ed[i][j] == 0)  return true;
  return false;
}

void dfs(int u, int v, int d){
  int dx[] = {0, 0, -1, 1};
  int dy[] = {1, -1, 0, 0};
  for(int i = 0; i < 4; i++){
    int x = dx[i] + u, y = dy[i] + v;
    if(x >= 1 && y >= 1 && x <= n && y <= m && st[x][y] == '.'){
      st[x][y] = 'g';
      ed[x][y] = d;
    }
  }
}


int main(){
  scanf("%d%d", &n, &m);

  for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++){
      cin>>st[i][j];
      ed[i][j] = 1;
    }

  scanf("%d", &k);

  int x = 1;   //第一层
  while(x <= k){
    if(check()) break;   //全变为g不用再搜索了
    for(int i = 1; i <= n; i++)
      for(int j = 1; j <= m; j++)
        if(st[i][j] == 'g' && ed[i][j] == x)
          dfs(i, j, x + 1);
    x++;
  }

  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= m; j++)
      printf("%c", st[i][j]);
    puts("");
  }
  return 0;
}

第二题:蓝肽子序列

题目描述
L 星球上的生物由蛋蓝质组成,每一种蛋蓝质由一类称为蓝肽的物资首尾连接成一条长链后折叠而成。
生物学家小乔正在研究 L 星球上的蛋蓝质。她拿到两个蛋蓝质的蓝肽序列,想通过这两条蓝肽序列的共同特点来分析两种蛋蓝质的相似性。
具体的,一个蓝肽可以使用 1 至 5 个英文字母表示,其中第一个字母大写,后面的字母小写。一个蛋蓝质的蓝肽序列可以用蓝肽的表示顺序拼接而成。
在一条蓝肽序列中,如果选取其中的一些位置,把这些位置的蓝肽取出,并按照它们在原序列中的位置摆放,则称为这条蓝肽的一个子序列。蓝肽的子序列不一定在原序列中是连续的,中间可能间隔着一些未被取出的蓝肽。
如果第一条蓝肽序列可以取出一个子序列与第二条蓝肽序列中取出的某个子序列相等,则称为一个公共蓝肽子序列。
给定两条蓝肽序列,找出他们最长的那个公共蓝肽子序列的长度。
输入描述
输入两行,每行包含一个字符串,表示一个蓝肽序列。字符串中间没有空格等分隔字符。
其中有 ,两个字符串的长度均不超过 1000。
输出描述
输出一个整数,表示最长的那个公共蓝肽子序列的长度。

最长公共子序列问题

f[i, j] 表示从a里面选前i个数,和从b里面选前j个数,构成的最长长度

  1. a[i] != b[j] f[i][j] = max(f[i-1][j], f[i][j-1]), 等于最大的a上一个长度,或者b上一个长度

  1. a[i] == b[j] f[i][j] = max(f[i][j], f[i-1][j-1] + 1), 等于最大的本身和a,b上一个加一

现在问题是怎么变成蓝肽,去比较大小

遍历字符串,如果不是第一个字符,而且是大写 就把前面的字符形成的串加进去

如果是最后一个字符,而且是小写 当前字符加进去,然后再break

除了第二个如果情况,其余都要加进当前子字符

注意保存长度,和初始化一些值,因为没有封装成函数

#include<iostream>
#include<vector>
using namespace std;

const int N = 1010;
string a[N], b[N];
int f[N][N];

int main(){
  string s1, s2;
  cin>>s1; cin>>s2;

  string str = "";
  int n = s1.size(), m = s2.size();
  int k = 1;
  for(int i = 0; i < n; i++){
    if(i > 0 && s1[i] >= 'A' && s1[i] <= 'Z'){
      a[k++] = str;
      str = "";
    }
    if(i == n - 1) {
      str += s1[i];
      a[k++] = str;
      str = "";
      break;
    }
    str += s1[i];
  }
  n = k - 1;

  k = 1;
  for(int i = 0; i < m; i++){
    if(i > 0 && s2[i] >= 'A' && s2[i] <= 'Z'){
      b[k++] = str;
      str = "";
    }
    if(i == m - 1) {
      str += s2[i];
      b[k++] = str;
      str = "";
      break;
    }
    str += s2[i];
  }
  m = k - 1;

  for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++){
      f[i][j] = max(f[i-1][j], f[i][j-1]);
      if(a[i] == b[j]) f[i][j] = max(f[i][j], f[i-1][j-1] + 1);
    }

  cout<<f[n][m]<<endl;
  return 0;
}

第三题:迷宫与陷阱

题目描述
小明在玩一款迷宫游戏,在游戏中他要控制自己的角色离开一间由 N×N 个格子组成的 2D 迷宫。
小明的起始位置在左上角,他需要到达右下角的格子才能离开迷宫。
每一步,他可以移动到上下左右相邻的格子中(前提是目标格子可以经过)。
迷宫中有些格子小明可以经过,我们用 '.' 表示。
有些格子是墙壁,小明不能经过,我们用 '#' 表示。
此外,有些格子上有陷阱,我们用 'X' 表示。除非小明处于无敌状态,否则不能经过。
有些格子上有无敌道具,我们用 '%' 表示。
当小明第一次到达该格子时,自动获得无敌状态,无敌状态会持续 K 步。
之后如果再次到达该格子不会获得无敌状态了。
处于无敌状态时,可以经过有陷阱的格子,但是不会拆除/毁坏陷阱,即陷阱仍会阻止没有无敌状态的角色经过。
给定迷宫,请你计算小明最少经过几步可以离开迷宫?
输入描述
输入描述
第一行包含两个整数 N,K (1≤N≤1000,1≤K≤10)。
以下 N 行包含一个 N×N 的矩阵。
矩阵保证左上角和右下角是 '.'。
输出描述
一个整数表示答案。如果小明不能离开迷宫,输出 -1。

只过了60%,不知道为啥

跟迷宫问题差不多,加了个无敌状态

而且要用到当层的无敌状态,这就要创建结构体以及数组来确定了

其余的就是bfs文章来源地址https://www.toymoban.com/news/detail-420999.html

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;

const int N = 1010;
int d[N][N], vis[N][N][15];
int n, k;
char g[N][N];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
struct node{
  int x, y, k;
  node (int ax, int ay, int ak){
    x = ax, y = ay, k = ak;
  }
};

int bfs(){
  queue<node> q;
  vis[1][1][0] = 1;
  q.push({1, 1, 0});

  while(!q.empty()){
      auto t = q.front();
      q.pop();
      if(t.x == n && t.y == n)
        return d[n][n];
      for(int i = 0; i < 4; i++){
        int x = dx[i] + t.x, y = dy[i] + t.y;
        if(x < 1 || x > n && y < 1 || y > n || g[x][y] == '#') continue;

        if(g[x][y] == '%' && !vis[x][y][k]){
          vis[x][y][k] = 1;
          d[x][y] = d[t.x][t.y] + 1;
          q.push(node{x, y, k});
        } 
        else{
          if(t.k && !vis[x][y][t.k - 1]){
            vis[x][y][t.k - 1] = 1;
            d[x][y] = d[t.x][t.y] + 1;
            q.push(node{x, y, t.k - 1});
          }
          else if(g[x][y] == '.' && !t.k && !vis[x][y][0]){
            vis[x][y][0] = 1;
            d[x][y] = d[t.x][t.y] + 1;
            q.push(node{x, y, 0});
          }
        }
      }
  }

  return -1;
}

int main(){
  scanf("%d%d", &n, &k);

  for(int i = 1; i <= n; i++) 
    for(int j = 1; j <= n; j++)
      cin>>g[i][j];

  cout<<bfs()<<endl;
  return 0;
}

到了这里,关于蓝桥杯刷题第二十三天的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 蓝桥杯刷题篇①

    前言:hello各位童学们好呀!许久不见!本文为本人的蓝桥杯OJ的刷题笔记!文章隶属于专栏蓝桥杯,该专栏的目的是为了记录自己的刷题记录和学习过程,激励自己不断前行,为明年的ACM、ICPC、蓝桥杯等比赛做足准备,也希望可以帮助到一些同样在刷题道路上的小伙伴们!

    2024年02月09日
    浏览(51)
  • 7.10蓝桥杯刷题

       很巧妙的一道回溯算法的题目 只有两种选择,一个是加入到一集合中去,一个是加入到二集合中去,结束的条件是对应下标的索引值等于A.length的时候,同时满足sum1和sum2都是偶数的情况下 count++; 后序还可以考虑适当的剪枝进行优化,

    2024年02月16日
    浏览(40)
  • 蓝桥杯刷题014——求阶乘(二分法)

    蓝桥杯2022省赛题目 问题描述 满足 N ! 的末尾恰好有  K 个 0 的最小的 N 是多少? 如果这样的 N 不存在输出 −1 。 输入格式 一个整数 K 。 输出格式 一个整数代表答案。 样例输入 样例输出 评测用例规模与约定 对于 30% 的数据, 1≤K≤10^6. 对于 100% 的数据, 1≤K≤10^

    2023年04月12日
    浏览(34)
  • 蓝桥杯刷题015——最少刷题数(二分法+前缀和)

    问题描述 小蓝老师教的编程课有  N 名学生 , 编号依次是 1…N  。 第 i 号学生这学期刷题的数量是 Ai​  。 对于每一名学生, 请你计算他 至少 还要再刷多少道题 , 才能使得 全班刷题比他多的学生数不超过刷题比他少的学生数。 输入格式 第一行包含一个正整数 N 。 第二

    2023年04月14日
    浏览(41)
  • 蓝桥杯刷题冲刺 | 倒计时3天

    作者:指针不指南吗 专栏:蓝桥杯倒计时冲刺 🐾马上就要蓝桥杯了,最后的这几天尤为重要,不可懈怠哦🐾 题目 链接: 790. 数的三次方根 - AcWing题库 给定一个浮点数 n,求它的三次方根。 输入格式 共一行,包含一个浮点数 n。 输出格式 共一行,包含一个浮点数,表示问

    2023年04月09日
    浏览(61)
  • 蓝桥杯刷题冲刺 | 倒计时6天

    作者:指针不指南吗 专栏:蓝桥杯倒计时冲刺 🐾马上就要蓝桥杯了,最后的这几天尤为重要,不可懈怠哦🐾 题目 链接: 4941. 凑数 - AcWing题库 初始时,n=0。 每一轮操作都要依次完成两个步骤: 第一步,任选一个 非负 整数 a,将 n 增加 a,这一步所需付出的代价为 a。 第二

    2023年04月08日
    浏览(41)
  • 蓝桥杯刷题冲刺 | 倒计时1天

    作者:指针不指南吗 专栏:蓝桥杯倒计时冲刺 🐾蓝桥杯加油,大家一定可以🐾 我是菜菜,最近容易我犯的错误总结 + 一些tips 各位蓝桥杯加油加油 当输入输出数据不超过 1e6 时, scanf printf 和 cin cout 是没有差距的; 超过这个数据范围时,就是用 scanf printf 多次调式,自己手

    2023年04月09日
    浏览(36)
  • 蓝桥杯刷题冲刺 | 倒计时2天

    作者:指针不指南吗 专栏:蓝桥杯倒计时冲刺 🐾马上就要蓝桥杯了,最后的这几天尤为重要,不可懈怠哦🐾 题目 链接: 854. Floyd求最短路 - AcWing题库 给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环,边权可能为负数。 再给定 k 个询问,每个询问包含两个整数

    2023年04月10日
    浏览(43)
  • 蓝桥杯刷题016——最大子矩阵(尺取法+单调队列)

    题目来源:最大子矩阵 - 蓝桥云课 (lanqiao.cn) 问题描述 小明有一个大小为 N×M 的矩阵, 可以理解为一个 N 行 M 列的二维数组。 我们定义一个矩阵 m 的 稳定度 f(m)  为 f(m)=max(m)−min(m) , 其中 max(m) 表示矩阵 m 中的最大值, min(m) 表示矩阵 m 中的最小值。 现在小明想要从

    2023年04月16日
    浏览(33)
  • 密码学学习笔记(二十三):哈希函数的安全性质:抗碰撞性,抗第一原象性和抗第二原象性

    在密码学中,哈希函数是一种将任意长度的数据映射到固定长度输出的函数,这个输出通常称为哈希值。理想的哈希函数需要具备几个重要的安全性质,以确保数据的完整性和验证数据的来源。这些性质包括抗碰撞性、抗第一原象性和抗第二原象性。 抗碰撞性指的是在合理的

    2024年02月05日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包