蓝桥杯刷题第二十五天

第一题:全球变暖

题目描述

你有一张某海域 NxN 像素的照片,"."表示海洋、"#"表示陆地,如下所示:

.......

.##....

.##....

....##.

..####.

...###.

.......

其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有 2 座岛屿。

由于全球变暖导致了海面上升,科学家预测未来几十年,岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋),它就会被淹没。

例如上图中的海域未来会变成如下样子:

.......

.......

.......

.......

....#..

.......

.......

请你计算:依照科学家的预测,照片中有多少岛屿会被完全淹没。

输入描述

第一行包含一个整数 N (1≤N≤1000)。

以下 N 行 N 列代表一张海域照片。

照片保证第 1 行、第 1 列的像素都是海洋。、

输出一个整数表示答案。

输入输出样例

示例

输入

7
.......
.##....
.##....
....##.
..####.
...###.
.......

输出

1

 dfs,岛屿问题

一个岛屿不会被淹没,要有一块大陆上下左右都不和海洋相邻

flag表示一个岛屿中有一块大陆是这样的,就不需要再遍历了

其余情况继续遍历,并且把对应变成海洋,这里用*来代替,就不用开状态数组了

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

const int N = 1010;
char g[N][N];
int n, cnt, olds, news;
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
bool flag;

void dfs(int u, int v){
  if(!flag) {
    cnt = 0;
    for(int i = 0; i < 4; i++){
      int x = dx[i] + u, y = dy[i] + v;
      if(g[x][y] != '.') cnt++;
    }
    if(cnt == 4) {
      news++;
      flag = true;
    }
  }

  g[u][v] = '*';
  for(int i = 0; i < 4; i++){
    int x = dx[i] + u, y = dy[i] + v;
    if(x >= 1 && x <= n && y >= 1 && y <= n && g[x][y] == '#')
      dfs(x, y);
  }

}

int main(){
  cin>>n;

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

  for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
      if(g[i][j] == '#'){
        olds++;
        flag = false;
        dfs(i ,j);
      }

  cout<<olds-news<<endl;
  return 0;
}

 新的方法,叫什么弗拉基米得算法,通过这可以遍历到每个连通块中的各个陆地

首先遍历,如果当前没有被遍历,而且为陆地,比较边界数量和总数量得值,如果相等,即要被淹没,所以就要加进去

然后是一个BFS,使用stl队列实现,如果该陆地相邻有海洋,那么他就是边界

是陆地而且没有遍历过的话,就放进队列再找

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

const int N = 1010;
char g[N][N];
bool st[N][N];
int n;
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};

void dfs(int ax,int ay, int& total, int& bound){
    queue<pair<int, int>> q;
    q.push({ax, ay});
    st[ax][ay] = true;
    
    while(q.size()){
        auto t = q.front();
        q.pop();
        total++;
        bool is_bound = false;
        
        for(int i = 0; i < 4; i++){
            int x = t.first + dx[i], y = t.second + dy[i];
            if(x < 1 || x > n && y < 1 || y > n ) continue;
            if(st[x][y]) continue;
            if(g[x][y] == '.'){
                is_bound = true;
                continue;
            }
            q.push({x, y});
            st[x][y] = true;
        }
        if(is_bound) bound++;
    }
    
}

int main(){
  cin>>n;

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

  int cnt = 0;
  for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
        if(!st[i][j] && g[i][j] == '#'){
            int total = 0, bound = 0;
            dfs(i ,j ,total, bound);
            if(total == bound)
                cnt++;
        }
    
  cout<<cnt<<endl;  
  return 0;
}

第四题:搬砖

问题描述

这天,小明在搬砖。

他一共有 n 块砖, 他发现第 i 砖的重量为 wi​, 价值为 vi​ 。他突然想从这些 砖中选一些出来从下到上堆成一座塔, 并且对于塔中的每一块砖来说, 它上面 所有砖的重量和不能超过它自身的价值。

他想知道这样堆成的塔的总价值(即塔中所有砖块的价值和)最大是多少。

输入格式

输入共 n+1 行, 第一行为一个正整数 n, 表示砖块的数量。

后面 n 行, 每行两个正整数 wi​,vi​ 分别表示每块砖的重量和价值。

输出格式

一行, 一个整数表示答案

样例说明

选择第 1、2、4块砖, 从上到下按照 2、1、4 的顺序堆成一座塔, 总价值 为 4+1+5=10

评测用例规模与约定

对于 20% 的数据, 保证 0n≤10;

对于 100% 的数据, 保证 n≤1000;wi​≤20;vi​≤20000 。

样例输入

5
4 4
1 1
5 2
5 5
4 3

样例输出

10

明确排序指标很关键,这是数学,要推导和多做题

然后剩下就是01背包问题了,直接套模板

j <= 2000 因为题目范围

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

typedef pair<int, int> PII;
const int N = 1010;
PII a[N];
int n, f[20004];

bool cmp(PII x, PII y){
  return x.first + x.second < y.first + y.second;
}

int main(){
  cin>>n;

  for(int i = 0; i < n ; i++){
    int w, v;
    cin>>w>>v;
    a[i] = {w, v};
  }

  sort(a, a + n, cmp);
  for(int i = 0; i < n; i++){
    int w = a[i].first, v = a[i].second;
    for(int j = 20000; j >= w; j--)
      if(v >= j - w) f[j] = max(f[j], f[j - w] + v);
  }
  
  int maxv = 0;
  for(int i = 0; i <= 20000; i++) maxv = max(maxv, f[i]);

  cout<<maxv<<endl;
  return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/7410.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Vue--构建亚马逊多账号的后台数据展示

效果展示&#xff1a; 根据自创的账号个数来创建对应的表格个数 移动到对应商品时展示该商品的日出售变化情况 设计思路&#xff1a; 获取亚马逊平台个人账号数据传入自定义组件<WeekTable> <WeekTable>组件获取到数据后&#xff0c;就会重载DOM元素内容。我们在组…

Ae 入门系列之七:文本动画

Ae 提供了多种制作文本动画的方法。既可以在时间轴面板上基于基本属性手动添加关键帧&#xff0c;还可以使用专门的文本动画制作工具&#xff0c;或者直接使用动画预设。有关文本图层的基础知识请参阅&#xff1a;《Ae&#xff1a;文本图层操作基础》提示&#xff1a;文本动画的…

员工培训Employee Training

前言 加油 原文 员工培训常用会话 ❶ When is our training session? 我们的课程培训在什么时候? ❷ You shouldn’t be absent at training sessions. 你不能缺席课程培训。 ❸ You should follow these rules and regulations. 你应该遵守这些规章制度。 ❺ The staff…

ROS实践11 自定义头文件并调用

文章目录运行环境&#xff1a;思路&#xff1a;1.1 编写头文件1.2 includepath添加头文件路径1.3 编写可执行文件1.4 配置文件1.5 编译运行运行环境&#xff1a; ubuntu20.04 noetic 宏基暗影骑士笔记本 思路&#xff1a; 类和函数&#xff1a; 头文件 声明 可执行文件 定义…

测试行业3年经验,从大厂裸辞后,面试阿里、字节全都一面挂,被面试官说我的水平还不如应届生

测试员可以先在大厂镀金&#xff0c;以后去中小厂毫无压力&#xff0c;基本不会被卡&#xff0c;事实果真如此吗&#xff1f;但是在我身上却是给了我很大一巴掌... 所谓大厂镀金只是不卡简历而已&#xff0c;如果面试答得稀烂&#xff0c;人家根本不会要你。况且要不是大厂出来…

Leetcode6365. 最少翻转操作数题解

题目在此&#xff1a;力扣 首先&#xff0c;先祝福自己本周周赛过了三题。耶耶耶耶耶耶&#xff01;虽然第一题因为脑子不好使想了半天&#xff0c;还WA了一次。衷心祈祷今年力扣能上1800分&#xff01;&#xff01;&#xff01; 这道题&#xff0c;我看了一些通过人数&#x…

【面试】Java高频面试题(2023最新整理)

文章目录一、java基础1、JDK 和 JRE 有什么区别&#xff1f;2、 和 equals 的区别是什么&#xff1f;3、final 在 java 中有什么作用&#xff1f;4、java 中的 Math.round(-1.5) 等于多少&#xff1f;5、String 属于基础的数据类型吗&#xff1f;6、String str"i"与 …

JUC并发编程高级篇第三章之CAS[Unsafe和原子增强类]

文章目录1、CAS的简介1.1、什么是CAS1.2、使用CAS的前后对比1.3、CAS如何做到不加锁的情况&#xff0c;保证数据的一致性1.4、什么是Unsafe类1.5、CAS方法参数详解1.6、CAS的原理1.7、 CAS的缺点2、原子操作类2.1、基本类型原子类2.2、数据类型原子类2.3、引用类型原子类2.4、对…

66-插入排序

目录 1.直接插入排序 2.折半插入排序 3.在数组arr[l...r]上使用插入排序 类似打扑克牌&#xff0c;整理牌的时候&#xff0c;都是把乱的牌向已经码好的牌中插入——天然的插入排序。 1.直接插入排序 每次选择无序区间的第一个元素&#xff0c;插入到有序区间的合适位置&am…

chatGPT中国入口-ChatGPT评论文章-ChatGPT怎么用

国内怎么玩chatGPT 如果您在国内使用ChatGPT&#xff0c;主要的问题可能是连接OpenAI服务器的速度和稳定性。由于OpenAI位于美国&#xff0c;可能受到中国的网络限制和防火墙的影响&#xff0c;造成访问速度比较慢或不稳定。为了解决这个问题&#xff0c;您可以采取以下方法&a…

idea常用快捷键,包的介绍,访问修饰符

这里有的是我自己定义的快捷键&#xff0c;可以到图片是指定位置查看对应的快捷键是什么。删除当前行&#xff0c;Ctrld复制当前行&#xff0c;自己配置CtrlShift向下箭头补全代码 alt /注释Ctrl /自动导入包在上面位置把两个选项选中&#xff0c;在要导入包的红色位置输入al…

(C++)模板分离编译面对的问题

什么是分离编译模板的分离编译什么是分离编译 一个程序&#xff08;项目&#xff09;由若干个源文件共同实现&#xff0c;而每个源文件单独编译生成目标文件&#xff0c;最后将所有目标文件链接起来形成单一的可执行文件的过程称为分离编译模式。 模板的分离编译 假如有以下…

Spring入门(万字详细附代码讲解)

1.Spring介绍 Spring其实就是一种开源框架,指的是Spring Framework,具有良好的生态,这也是Spring经久不衰的原因 用一句话概括,Spring就是一个集成了众多工具和方法的IOC容器 2.IOC容器 什么是IOC容器呢? IOC的中文翻译过来就是控制反转,IOC容器其实就是控制反转容器 那什…

2022蓝桥杯省赛——卡片

问题描述 小蓝有 k 种卡片, 一个班有 n 位同学, 小蓝给每位同学发了两张卡片, 一位同学的两张卡片可能是同一种, 也可能是不同种, 两张卡片没有顺序。没有两位同学的卡片都是一样的。 给定 n, 请问小蓝的卡片至少有多少种? 输入格式 输入一行包含一个正整数表示 n 。 输出…

Vue中的slot插槽

目录 &#xff08;一&#xff09;什么是slot插槽 (1)slot插槽的作用 (2)插槽的好处和使用场景 &#xff08;3&#xff09;slot插槽的分类 1、默认插槽 2、具名插槽 3、作用域插槽 &#xff08;一&#xff09;什么是slot插槽 (1)slot插槽的作用 slot具有“占坑”的作用…

Hadoop MapReduce各阶段执行过程以及Python代码实现简单的WordCount程序

视频资料&#xff1a;黑马程序员大数据Hadoop入门视频教程&#xff0c;适合零基础自学的大数据Hadoop教程 文章目录Map阶段执行过程Reduce阶段执行过程Python代码实现MapReduce的WordCount实例mapper.pyreducer.py在Hadoop HDFS文件系统中运行Map阶段执行过程 把输入目录下文件…

【GoF 23 概念理解】AOP面向切面编程

1. 什么是AOP——面向切面编程 AOP是一种编程范式&#xff0c;提供了一种从宁一个角度来考虑程序结构以完善面向对象编程&#xff08;OOP&#xff09; AOP是一个思想上的变化——主从换位&#xff0c;让原本主动调用的模块变成了被动等待&#xff0c;甚至在毫不知情的情况下被…

CodeTON Round 4 (Div. 1 + Div. 2, Rated, Prizes!)A~E

比赛连接&#xff1a;Dashboard - CodeTON Round 4 (Div. 1 Div. 2, Rated, Prizes!) - Codeforces A. Beautiful Sequence 题意&#xff1a; t(1≤t≤500)组测试每组给定大小为n(1≤n≤100) 的序列&#xff0c;判断它是否存在一个子序列是好序列。一个序列是好序列当且仅当至…

GPT-3:大语言模型小样本学习

论文标题&#xff1a;Language Models are Few-Shot Learners论文链接&#xff1a;https://arxiv.org/abs/2005.14165论文来源&#xff1a;OpenAI一、概述自然语言处理已经从学习特定任务的表示和设计特定任务的架构转变为使用任务无关的预训练和任务无关的架构。这种转变导致了…

Python - Huffman Tree 霍夫曼树实现与应用

目录 一.引言 二.Huffman Tree 理论 1.定义 2.结构 3.构造 三.Huffman Tree 实现 1.生成霍夫曼树 2.编码霍夫曼编码 3.解码霍夫曼编码 4.霍夫曼树编码解码实践 四.总结 一.引言 上篇 Word2vec 的文章中指出每次计算词库 N 个单词的 Softmax 计算量很大&#xff0c;…
最新文章