当前位置: 首页 > news >正文

蓝桥杯每日一题(BFS)

1562 微博转发

开始思路错误点:在用拉链法保存关注信息的时候,因为要看一个用户发的有多少转发的,所以要以用户为坑位,所有关注这个坑位的用户为链表。(开始弄反了)

e数组存某个用户的idx,ne是某个节点在链表上的下一个,h是坑位。

st状态数组的参数是用户,而不是idx

#include<bits/stdc++.h>
using namespace std;
//1562 微博转发
const int N=1e3+10;
int n,l;
//拉链法存储
int e[N],idx,ne[N],h[N];
bool st[N];
//e某个idx对应的用户是谁
//ne 这个用户和其他人是否被i同时关注
//h代表某个用户的关注列表的链表尾部
void add(int u,int x)
{// 把某个被关注的用户加入到某个用户的链表中e[idx]=x,ne[idx]=h[u],h[u]=idx++;
}int bfs(int s)//找某个节点的第l层关注的用户个数
{//之前都是只要有后继就加入到队列中//如何实现到规定的层的位置就终止呢//就是L层循环:每次循环都控制向外延伸一层memset(st,0,sizeof(st));queue<int>q;q.push(s);st[s]=1;int res=0;//前l层有多少个点for(int i=1;i<=l;i++)//向前走l层{int num=q.size();//num就是上一次循环扩展出来的点while(num--){int t=q.front();q.pop();for(int j=h[t];j!=-1;j=ne[j]){if(!st[e[j]]){q.push(e[j]);res++;st[e[j]]=1;}}}}return res;}
int main()
{cin>>n>>l;memset(h,-1,sizeof(h));for(int i=1;i<=n;i++){int x;cin>>x;while(x--){int u;cin>>u;add(u,i);//i关注了u}}int qu;cin>>qu;while(qu--){int user;cin>>user;cout<<bfs(user)<<endl;}}

//844走迷宫

自己是用pair并且second放走的步数,内存超限了。

下面是自己的做法

#include<bits/stdc++.h>
using namespace std;
//844走迷宫
typedef pair<int,int>PII;
typedef pair<PII,int> PIII;
const int N=100;
int p[N][N];
int n,m;
int s[4]={0,1,0,-1};
int z[4]={1,0,-1,0};
int dfs()
{queue<PIII>q;q.push({{1,1},0});while(!q.empty()){PIII t=q.front();q.pop();PII zuo=t.first;int x=zuo.first;int y=zuo.second;for(int i=0;i<4;i++){if(x+z[i]>=1&&x+z[i]<=n&&y+s[i]>=1&&y+s[i]<=m&&!p[x+z[i]][y+s[i]]){q.push({{x+z[i],y+s[i]},t.second+1});if(x+z[i]==n&&y+s[i]==m){//cout<<t.second+1<<endl;return t.second+1;}}}}}
int main()
{cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){int num;cin>>num;if(num)p[i][j]=1;}}cout<< dfs();
}

y做法:直接使用一个二维数组存某个坐标到达的时候走的步数。

845 八数码 

在bfs求最短路的问题中,重点是怎么保存状态,y的做法:把矩阵转化为字符串,从初始位置到这个状态走的距离就是变化的次数

太巧妙了;

//看完y思路之后,最后怎么都是输出不对,最后找到是swap(还原的那个swap)应该也在if条件中,就是在4层的for循环中不一定都符合不越界的要求。

#include<bits/stdc++.h>
using namespace std;
//845 八数码
//既可以存状态,又可以存步数
unordered_map<string ,int>d;//记录到这个状态转换了多少次
queue<string>q;//所有的状态
string start="12345678x";
int ss[4]={-1, 0, 1, 0},z[4]={0, 1, 0, -1};
int bfs(string s)
{q.push(s);d[s]=0;while(q.size()){string t=q.front();q.pop();int p=t.find('x');int y=p/3;int x=p%3;int dis=d[t];if(t==start)return d[t];for(int i=0;i<4;i++){//  cout<<" ********"<<endl;int xx=x+z[i];int yy=y+ss[i];//cout<<xx<<" "<<yy<<" "<<"si::"<<ss[i]<<endl;if(xx>=0&&xx<3&&yy>=0&&yy<3){swap(t[p],t[yy*3+xx]);//cout<<"yun"<<endl;if(!d.count(t)){d[t]=dis+1;q.push(t);}swap(t[p],t[yy*3+xx]);}//if(t==start)return d[t];}}return -1;
}int main()
{string s;for(int i=0;i<9;i++){string c;cin>>c;s+=c;}//cout<<s<<endl;cout<<bfs(s)<<endl;}

//1233全球变暖

自己做的WA,先用 bfs看有几个岛屿,淹没操作后,再用bfs看。

#include<bits/stdc++.h>
using namespace std;
//1233 全球变暖
typedef pair<int,int>PII;
const int N=1010;
int n;
int p[N][N],f[N][N];
int st[N][N];
int s[4]={1,0,0,-1},z[4]={0,1,-1,0};
int bfs()
{int cnt=0;memset(st,0,sizeof(st));queue<PII>q;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(!st[i][j]&&p[i][j])//没有被访问过的一片陆地{//  cout<<"find that match if"<<endl;st[i][j]=1;cnt++;//cout<<"cnt "<<cnt<<endl;q.push({i,j});while(q.size()){PII t=q.front();//cout<<q.front().first<<" "<<q.front().second<<endl;q.pop();for(int k=0;k<4;k++){int x=t.first+s[k];int y=t.second+z[k];if(x>=1&&x<=n&&y>=1&&y<=n&&p[x][y]&&!st[x][y]){q.push({x,y});st[x][y]=1;}}}}}}return cnt;
}int main()
{cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){char c;cin>>c;if(c=='#')p[i][j]=1,f[i][j]=1;}}//查看有几个岛屿int precnt=bfs();//淹没for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(!f[i][j])//如果本来是一个海域{for(int k=0;k<4;k++){//cout<<"dawn"<<endl;int x=i+s[k];int y=j+z[k];if(x>=1&&x<=n&&y>=1&&y<=n&&p[x][y]){p[x][y]=0;//被淹没}}}}}//还有几个岛屿int poscnt=bfs();int num=precnt-poscnt;cout<<num<<endl;}

y是在bfs的时候就在4的for循环中判断,这个连通块是否被淹没,是就加加。最后根据这个连通块的节点个数和被淹没的节点个数判断这个岛屿是否被淹没

相关文章:

蓝桥杯每日一题(BFS)

1562 微博转发 开始思路错误点&#xff1a;在用拉链法保存关注信息的时候&#xff0c;因为要看一个用户发的有多少转发的&#xff0c;所以要以用户为坑位&#xff0c;所有关注这个坑位的用户为链表。&#xff08;开始弄反了&#xff09; e数组存某个用户的idx&#xff0c;ne是…...

【C语言】linux内核pci_save_state

一、中文注释 //include\linux\pci.h /* 电源管理相关的例程 */ int pci_save_state(struct pci_dev *dev);//drivers\pci\pci.c /*** pci_save_state - 在挂起前保存PCI设备的配置空间* dev: - 我们正在处理的PCI设备*/ int pci_save_state(struct pci_dev *dev) {int i;/* X…...

轻松打造完美原型:9款在线工具推荐

早年&#xff0c;UI设计师选择的工具有限&#xff0c;功能相对单一&#xff0c;大多数在线原型设计工具都是国外的&#xff0c;语言和网络都增加了设计工作的负担。如今&#xff0c;国内外有许多在线原型设计工具&#xff0c;不仅可以在浏览器上使用&#xff0c;而且还具有团队…...

Vue3中Pinia状态管理库学习笔记

pinia的基本使用 <template><div><h2>Home View</h2> <h2>count:{{ counterStore.count }}</h2><h2>count:{{ count }}</h2><button click"increment">count1</button></div> </template>…...

共谋企业出海新篇章纷享销客荣获数字中国企业峰会“卓越成果奖”

3月9日&#xff0c;2024数字中国企业峰会在杭州西湖中维香溢大酒店成功举办&#xff0c;众多数字化领域专家、知名企业 CIO 代表到场。峰会旨在推动数字化转型与创新发展&#xff0c;为企业出海和国际合作搭建交流与合作的平台。本次峰会的颁奖环节&#xff0c;纷享销客凭借其卓…...

【MySQL】group_concat 函数和 locate 函数运用之找到每篇文章的主题

力扣题 1、题目地址 2199. 找到每篇文章的主题 2、模拟表 表&#xff1a;Keywords Column NameTypetopic_idintwordvarchar (topic_id, word) 是该表的主键&#xff08;具有唯一值的列的组合&#xff09;。该表的每一行都包含一个主题的 id 和一个用于表达该主题的词。可…...

RedisCluster集群中的插槽为什么是16384个?

RedisCluster集群中的插槽为什么是16384个&#xff1f; CRC16的算法原理。 1.根据CRC16的标准选择初值CRCIn的值2.将数据的第一个字节与CRCIn高8位异或3.判断最高位&#xff0c;若该位为0左移一位&#xff0c;若为1左移一位再与多项式Hex码异或4.重复3至9位全部移位计算结束5…...

一直出现问题,发现服务器磁盘空间已满导致,腾出服务器磁盘空间命令

要解决服务器磁盘空间已满的问题&#xff0c;你可以按照以下步骤操作&#xff1a; 查看磁盘使用情况&#xff1a;使用df -h&#xff0c; du -s -h ./*命令来查看服务器的磁盘空间使用情况。查找大文件&#xff1a;使用du -a | sort -rn | head -5命令来找出占用空间最大的前5个…...

吴恩达机器学习笔记 二十三 倾斜数据集的误差指标 精确率 召回率 精确率与召回率的平衡 F1分数

如果数据集的正例和反例的比例非常倾斜&#xff0c;常用的错误指标如 准确率(accuracy) 并不好用。此时可以用精确率和召回率。 精确率&#xff08;precision&#xff09;&#xff1a;真阳的样本数/预测为阳的样本数真阳数/&#xff08;真阳假阳&#xff09; 召回率(recall):…...

无人游艇的研发和开发对于多个领域具有重要

无人游艇的研发和开发对于多个领域具有重要性。 首先&#xff0c;无人游艇可以在海上进行各种任务&#xff0c;如海洋科学研究、资源勘探和监测、海洋环境保护等。相比传统的人工操作船只&#xff0c;无人游艇可以长时间在海上工作&#xff0c;可以自动化执行任务&#xff0c;…...

在AI创业热潮下,如何抓住AI赚钱机会,实现人生逆袭

随着人工智能技术的迅猛发展,AI创业热潮正席卷全球。这不仅为科技领域的专业人士提供了无限的商机,也为普通人开辟了全新的赚钱途径。本文将为您揭示在AI创业热潮下,普通人如何抓住AI赚钱机会,实现人生逆袭,同时探讨哪些行业适合应用AI技术。 一、普通人如何抓住AI赚钱机…...

JETSON 配置并跑通 NanoDet

JETSON 配置 NanoDet 文章目录 JETSON 配置 NanoDetNanoDet 介绍源码环境搭建及测试配置 NanoDet 的环境环境配置过程中遇到的问题&#xff1a;环境配置完毕验证 NanoDet NanoDet 介绍 可以参考这个博客&#xff1a;NanoDet&#xff1a;这是个小于4M超轻量目标检测模型 源码 …...

突破编程_C++_C++11新特性(unordered_multimap)

1 概述 std::unordered_multimap 是一个哈希表实现的无序容器&#xff0c;它存储的元素是键值对&#xff0c;并且允许键的重复。这意味着同一个键可以关联多个值。在 std::unordered_multimap 中&#xff0c;元素的插入顺序是不确定的&#xff0c;并且不会因为元素的插入、删除…...

15.WEB渗透测试--Kali Linux(三)

免责声明&#xff1a;内容仅供学习参考&#xff0c;请合法利用知识&#xff0c;禁止进行违法犯罪活动&#xff01; 内容参考于&#xff1a; 易锦网校会员专享课 上一个内容&#xff1a;14.WEB渗透测试--Kali Linux&#xff08;二&#xff09;-CSDN博客 Kali工具使用 3389远…...

Android-Framework pm list packages和pm install返回指定应用信息

一、环境 高通 Android 13 注&#xff1a;Android10 和Android13有些差异&#xff0c;代码位置不变&#xff0c;参照修改即可 二、pm简单介绍 pm工具为包管理&#xff08;package manager&#xff09;的简称 可以使用pm工具来执行应用的安装和查询应用宝的信息、系统权限、…...

CSS

什么是CSS&#xff1f; CSS是一门语言&#xff0c;用于控制网页表现 CSS&#xff08;Cascading Style Sheet&#xff09;&#xff1a;层叠样式表 W3C标准&#xff1a;网页主要由三部分组成 结构&#xff1a;HTML表现&#xff1a;CSS行为&#xff1a;JavaScript CSS导入方式…...

算法详解——选择排序和冒泡排序

一、选择排序 选择排序算法的执行过程是这样的&#xff1a;首先&#xff0c;算法遍历整个列表以确定最小的元素&#xff0c;接着&#xff0c;这个最小的元素被置换到列表的开头&#xff0c;确保它被放置在其应有的有序位置上。接下来&#xff0c;从列表的第二个元素开始&#x…...

图论(蓝桥杯 C++ 题目 代码 注解)

目录 迪杰斯特拉模板&#xff08;用来求一个点出发到其它点的最短距离&#xff09;&#xff1a; 克鲁斯卡尔模板&#xff08;用来求最小生成树&#xff09;&#xff1a; 题目一&#xff08;蓝桥王国&#xff09;&#xff1a; 题目二&#xff08;随机数据下的最短路径&#…...

矩阵起源新一年喜报连连!

新春伊始 矩阵起源向大家分享 一连串好消息 首先&#xff0c;公司创始人兼CEO王龙先生获评“2023深圳创新突出贡献人物“。这一荣誉是对其在推动数据库行业技术创新和产品开发方面所做出的卓越贡献的认可。他的领导力和创新精神不仅引领我司取得了显著的成就&#xff0c;也为…...

牛客——紫魔法师(并查集)

链接&#xff1a;登录—专业IT笔试面试备考平台_牛客网 来源&#xff1a;牛客网 题目描述 “サーヴァント、キャスター、Medea。”--紫魔法师 给出一棵仙人掌(每条边最多被包含于一个环&#xff0c;无自环&#xff0c;无重边&#xff0c;保证连通)&#xff0c;要求用最少的…...

最新WooCommerce教程指南-如何搭建B2C外贸独立站

WooCommerce是全球最受欢迎的开源电子商务平台之一。它基于WordPress建站&#xff0c;只需一键安装即可使用。该平台提供了丰富的功能&#xff0c;包括产品发布、库存管理、支付网关和运输发货等&#xff0c;可以帮助搭建各种类型的电子商务网站。相比其他竞争对手&#xff0c;…...

一文教会你SpringBoot是如何启动的

SpringBoot启动流程分析 流程图 源码剖析 运行Application.run()方法 我们在创建好一个 SpringBoot 程序之后&#xff0c;肯定会包含一个类&#xff1a;xxxApplication&#xff0c;我们也是通过这个类来启动我们的程序的&#xff08;梦开始的地方&#xff09;&#xff0c;而…...

车载测试面试:各大车企面试题汇总

本博主可协助大家成功进军车载测试行业 TBOX 深圳 涉及过T-BOX测试吗Ota升级涉及的台架环境是什么样的&#xff1f;上车实测之前有没有一个仿真环境台架环境都什么零部件T-BOX了解多少Linux和shell有接触吗 单片机uds诊断是在实车上座的吗 uds在实车上插的那口 诊断仪器是哪…...

Qt散文一

Qt的事件分为普通事件和系统事件&#xff0c;普通事件比如用户按下键盘&#xff0c;系统事件比如定时器事件。事件循环的开始是从main函数的QApplication&#xff0c;然后调用exec()开始的&#xff0c;在执行exec()函数之后&#xff0c;程序将进入事件循环来监听应用程序的事件…...

MySQL学习Day32——数据库备份与恢复

在任何数据库环境中&#xff0c;总会有不确定的意外情况发生&#xff0c;比如例外的停电、计算机系统中的各种软硬件故障、人为破坏、管理员误操作等是不可避免的&#xff0c;这些情况可能会导致数据的丢失、 服务器瘫痪等严重的后果。存在多个服务器时&#xff0c;会出现主从服…...

阅读基础知识

一 网络 1. 三次握手四次挥手 三次握手&#xff1a;为了建立长链接进行交互即建立一个会话&#xff0c;使用 http/https 协议 ① 客户端产生初始化序列号 Seqx &#xff0c;向服务端发送建立连接的请求报文&#xff0c;将 SYN1 同步序列号&#xff1b; ② 服务端接收建立连接…...

【NestJS 编程艺术】1. NestJS设计模式深度解析:构建高效、可维护的服务端应用

在当今快速发展的软件开发领域&#xff0c;Node.js凭借其轻量级和高性能的特点&#xff0c;已经成为了构建服务端应用的首选技术之一。然而&#xff0c;随着应用规模的扩大&#xff0c;传统的Node.js框架如Express和Koa可能在架构设计和代码组织上显得力不从心。这时&#xff0…...

QT中connect()的参数5:Qt::DirectConnection、Qt::QueuedConnection区别

原文链接&#xff1a;https://blog.csdn.net/Dasis/article/details/120916993 connect用于连接QT的信号和槽&#xff0c;在qt编程过程中不可或缺。它其实有第5个参数&#xff0c;只是一般使用默认值&#xff0c;在满足某些特殊需求的时候可能需要手动设置。 Qt::AutoConnect…...

VXLAN学习笔记

声明&#xff1a;该博客内容大部分参考参考链接整理 什么是VXLAN&#xff1f; VXLAN(Virtual Extensible LAN)即虚拟扩展局域网&#xff0c;是大二层网络中广泛使用的网络虚拟化技术。在源网络设备与目的网络设备之间建立一条逻辑VXLAN隧道&#xff0c;采用MAC in UDP的封装方…...

全排列的不同写法(茴字的不同写法)及对应的时间开销

资源课件&#xff1a; CS106B-recursion-pptstanford library-timer.hstanford library-set.h 不同的方法 1------ Set<string> permutations1Rec(string remaining) {Set<string> res;if(remaining.size() 0) {res "";}else {for(int i 0; i <…...

阿里云ecs 做网站/河南关键词排名顾问

测试驱动开发与PHPUnitPhalApi推荐使用测试驱动开发最佳实践&#xff0c;并主要使用的是PHPUnit进行单元测试。 PHPUnit官网&#xff1a;https://phpunit.de&#xff0c;如需进行单元测试&#xff0c;请先安装PHPUnit。 以下是在PhalApi下简化后TDD步骤。定义接口服务的函数签名…...

网站建设费支付请示/中国十大经典广告

&&#xff0c;双目运算符&#xff1a;将两个表达式的值按二进制位展开&#xff0c;对应的位(bit)按值进行“与”运算&#xff0c;结果保留在该位上…比如170&204对应二进制就是10101010B& 11001100B 10001000B…170&204136…该位只要有一个值为0结果为0&a…...

嘉定网站建设公司/杭州百度快照优化排名推广

Description 对于序列A&#xff0c;它的逆序对数定义为满足i<j&#xff0c;且Ai>Aj的数对(i,j)的个数。给1到n的一个排列&#xff0c;按照某种顺序依次删除m个元素&#xff0c;你的任务是在每次删除一个元素之前统计整个序列的逆序对数。 Solution 比较明显的CDQ分治维护…...

建个网站找/竞价sem托管公司

题意:每次插入一个数字,查询本质不同的子串有多少个 题解:sam,数字很大,ch数组用map来存,每次ins之后查询一下新建点表示多少个本质不同的子串(l[np]-l[fa[np]]) /**************************************************************Problem: 4516User: walfyLanguage: CResult: …...

php做网站很快嘛/网站制作推广电话

新浪微博需要登录才能爬取&#xff0c;这里使用m.weibo.cn这个移动端网站即可实现简化操作&#xff0c;用这个访问可以直接得到的微博id。分析新浪微博的评论获取方式得知&#xff0c;其采用动态加载。所以使用json模块解析json代码单独编写了字符优化函数&#xff0c;解决微博…...

做网站的资料/青岛网站建设运营推广

目录 文章目录目录概述准备测试文件方法实例演练方法1: 通过重定向到null来清空文件内容方法2: 使用冒号":" 或 "true"命令重定向来清空文件方法3: 使用"echo -n "命令清空文件内容方法4: 使用truncate命令来清空文件内容方法5: 使用cat命令和/d…...