算法训练营第六十七天 | 卡码网110 字符串接龙、卡码网105 有向图的完全可达性、卡码网106 岛屿的周长
卡码网110 字符串接龙
这题一开始用的邻接表+dfs,不幸超时
#include <iostream>
#include <list>
#include <string>
#include <vector>
using namespace std;int minLen = 501;bool count(string a, string b) {int num = 0;for (int i = 0; i < a.length() && i < b. length(); i++) {if (a[i] != b[i]) {num++;if (num > 1) return false;}}return true;
}int dfs(string* s, vector<list<int>>& l, int* visited, int len, int index, int n) {if (index == n + 1) {if (minLen > len) minLen = len;return len;}int result = 501;for (auto it = l[index].begin(); it != l[index].end(); it++) {if (!visited[*it]) {visited[*it] = 1;result = dfs(s, l, visited, len+1, *it, n);visited[*it] = 0;}}return min(minLen, result);
}int main() {int n;cin >> n;string s[n+2];cin >> s[0] >> s[n+1];for (int i = 1; i <= n; i++) {cin >> s[i];}vector<list<int>> l(n+1);for (int i = 0; i <= n; i++) {for (int j = 1; j <= n+1; j++) {if (j != i) {if (count(s[i], s[j])) l[i].push_back(j);}}}int visited[n+2];for (int i = 0; i < n+2; i++) visited[i] = 0;visited[0] = 1;minLen = dfs(s, l, visited, 1, 0, n);if (minLen == 501) cout << 0 << endl;else cout << minLen << endl;
}
题解中用的广搜,可以去看下,说是最短路径用深搜比较麻烦,要确定哪条最短,我确定出来了,但还是超时了。广搜只要搜到就一定是最短路径了,先放这。
卡码网105 有向图的完全可达性
这题就比较轻松了,深搜也不需要完全回溯,只需要遍历记录即可
代码如下:
#include <iostream>
#include <list>
#include <vector>
#include <queue>
using namespace std;void bfs(vector<list<int>>& l, vector<int>& visited, int index) {queue<int> myque;myque.push(index);while (!myque.empty()) {for (int i : l[index]) {if (!visited[i]) {visited[i] = 1;myque.push(i);}}myque.pop();}
}int main() {int n, k;cin >> n >> k;int s, t;vector<list<int>> l(n);for (int i = 0; i < k; i++) {cin >> s >> t;l[s-1].push_back(t-1);}vector<int> visited(n, 0);visited[0] = 1;bfs(l, visited, 0);for (int i = 0; i < n; i++) {if (!visited[i]) {cout << -1 << endl;return 0;}}cout << 1 << endl;return 0;
}
卡码网106 岛屿的周长
这题很简单,没用到dfs和bfs,简单填充边界后判断周围是否触碰边界后计数即可。
代码如下:
#include <iostream>using namespace std;int main() {int n, m;cin >> n >> m;int g[n][m];int sum = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> g[n][m];}}for (int i = 1; i < n - 1; i++) {for (int j = 1; j < m - 1; j++) {if (g[i][j] == 1) {if (g[i-1][j] == 0) sum++;if (g[i][j-1] == 0) sum++;if (g[i+1][j] == 0) sum++;if (g[i][j+1] == 0) sum++;}}}cout << sum << endl;
}
相关文章:
算法训练营第六十七天 | 卡码网110 字符串接龙、卡码网105 有向图的完全可达性、卡码网106 岛屿的周长
卡码网110 字符串接龙 这题一开始用的邻接表dfs,不幸超时 #include <iostream> #include <list> #include <string> #include <vector> using namespace std;int minLen 501;bool count(string a, string b) {int num 0;for (int i 0; …...
搭建 MySQL MHA
搭建 MySQL MHA 搭建 MySQL MHA实验拓扑图实验环境实验思路MHA架构故障模拟 实验部署数据库安装主从复制部署时间同步主服务器配置从服务器配置创建链接 MHA搭建安装依赖的环境安装 node 组件安装 manager 组件配置无密码认证在 manager 节点上配置 MHA管理 mysql 节点服务器创…...
python中的线程与进程
一、线程与进程 在计算机科学中,理解线程和进程的区别是重要的基础知识。这些概念对于多任务操作和并发编程尤为关键。下面将详细介绍线程与进程的区别、特点和各自的使用场景。 1.1 进程(Process) 进程是操作系统分配资源的基本单位。每个进…...
网络安全筑基篇——反序列化漏洞
目录 序列化是什么? 反序列化又是什么? 反序列化漏洞的危害 代码样例 常见的魔术方法 修复方式有哪些? 常见的反序列化漏洞 Shiro反序列化漏洞 Fastjson反序列化漏洞 序列化是什么? 将实例化对象转换成字节流的过程 反序…...
帝国cms定时审核并更新的方法
比如你网站采集了成千上万篇文章,不可能一下子全部放出来的,所以为了模拟人工发布,那么就需要定时审核发布文章内容,本文内容核心解决了更加个性化的逼真模拟人工更新网站内容。 第一:首先要满足你的表中有未审核的数据…...
一个简单好用安全的开源交互审计系统,支持SSH,Telnet,Kubernetes协议
前言 在当今的企业网络环境中,远程访问和交互审计成为了保障网络安-全的重要组成部分。然而,现有的解-决方案往往存在一些痛点,如复杂的配置、有限的协议支持、以及审计功能的不足。这些问题不仅增加了IT管理员的负担,也为企业的…...
使用Spring Boot和WebSocket实现实时通信
使用Spring Boot和WebSocket实现实时通信 大家好,我是免费搭建查券返利机器人省钱赚佣金就用微赚淘客系统3.0的小编,也是冬天不穿秋裤,天冷也要风度的程序猿!今天我们将探讨如何在Spring Boot应用中使用WebSocket实现实时通信&am…...
【Vue】集成富文本编辑器
这文章使用的是wangeditor插件,官网地址:wangEditor,这个比较简单 安装 npm i wangeditor --save 使用 <div id"editor"></div>import E from "wangeditor"const editor new E("#editor") e…...
【论文阅读】--Popup-Plots: Warping Temporal Data Visualization
弹出图:扭曲时态数据可视化 摘要1 引言2 相关工作3 弹出图3.1 椭球模型3.1.1 水平轨迹3.1.2 垂直轨迹3.1.3 组合轨迹 3.2 视觉映射与交互 4 实施5 结果6 评估7 讨论8 结论和未来工作致谢参考文献 期刊: IEEE Trans. Vis. Comput. Graph.(发表日期: 2019&…...
重建大师引擎数0,本地引擎设置改不了,空三在跑,这样是正常的吗?
答:任务目录和引擎监控目录并没有按照网络集群设置,需要调整为网络路径。 重建大师是一款专为超大规模实景三维数据生产而设计的集群并行处理软件,输入倾斜照片,激光点云,POS信息及像控点,输出高精度彩色网…...
APM教程-SkyWalking安装和配置
SkyWalking简介 APM (Application Performance Management) 即应用性能管理,属于IT运维管理(ITOM)范畴。主要是针对企业 关键业务的IT应用性能和用户体验的监测、优化,提高企业IT应用的可靠性和质量,保证用户得到良好的服务&#…...
斯坦福大学 AI 研究部门推出的“7 周人工智能学习计划”
①AI Python 基础,包括计算机原理、语法、判断语句等; ②AI Python 进阶,涉及 Linux 命令、多任务编程等; ③机器学习,涵盖算法、数据结构等; ④计算机视觉与图像处理,包含图像分类、目标检测…...
World of Warcraft [CLASSIC] plugin lua
World of Warcraft [CLASSIC] plugin lua 魔兽世界lua脚本插件 World of Warcraft API - Wowpedia - Your wiki guide to the World of Warcraft D:\World of Warcraft\_classic_\Interface\AddOns zwf.lua function CountdownFunc()CountdownFrame CreateFrame("Fram…...
背靠广汽、小马智行,如祺出行打得过滴滴和百度吗?
©自象限原创 作者丨艾AA 编辑丨薛黎 北京时间6月14日凌晨,在特斯拉股东大会上,马斯克阐述了对Robotaxi(自动驾驶出租车)商业模式的构想——特斯拉不仅会运营自己的无人驾驶出租车车队,还可以让特斯拉车主们的爱…...
CCSP自考攻略+经验总结
备考攻略 备考攻略准备阶段通读阶段精度阶段总复习阶段刷题阶段命运审判 写到最后 备考攻略 趁着对ssp知识点的理解还在,开始ccsp的考证之路,文章结构还是按照cissp备考篇的结构梳理。本次备考和cissp的离职在家备考不同,ccsp是在职利用非工…...
面试突击:ArrayList源码详解
本文已收录于:https://github.com/danmuking/all-in-one(持续更新) 前言 哈喽,大家好,我是 DanMu。ArrayList 是我们日常开发中不可避免要使用到的一个类,并且在面试过程中也是一个非常高频的知识点&#…...
力扣每日一题:2734. 执行子串操作后的字典序最小字符串
题目链接 脑子比较笨,分三种情况考虑: 以a开头。xxa,a在中间。 对于情况2还有两种可能: 1. 全是a,最后一个元素需要替换成z,因为必须执行一次操作。 2. aaaxxa,中间有一段非a,将这…...
C++11中std::thread的使用
C11 引入了 std::thread,它是用于创建和管理线程的标准库类。以下是详细的讲解,包括如何使用 std::thread 进行线程创建、管理和参数传递等操作。 1. 包含必要的头文件 在使用 std::thread 前,需要包含 <thread> 头文件: …...
酷瓜云课堂(内网版)v1.1.5 发布,局域网在线学习+考试系统
更新内容 更新layui-v2.9.10更新docker国内镜像地址增加导入镜像构建容器的方式教师不批阅非首次考试试卷轮播图增加专栏类型目标链接增加课程能否发布检查去除初始化kindeditor语言文件去除选择题EF选项优化富文本内容显示样式优化内容图片点击放大监听优化试题题干答案等图片…...
大数据之Hadoop部署
文章目录 服务器规划服务器环境准备1. 网络测试2. 安装额外软件包3. 安装基础工具4. 关闭防火墙5. 创建用户并配置权限6. 创建目录并设置权限7. 卸载JDK8. 修改主机名9. 配置hosts文件10. 重启服务器 配置免密登录安装Java安装Hadoop1. Hadoop部署2. 配置Hadoop3. 格式化Hadoop…...
DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径
目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...
FFmpeg 低延迟同屏方案
引言 在实时互动需求激增的当下,无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作,还是游戏直播的画面实时传输,低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架,凭借其灵活的编解码、数据…...
如何将联系人从 iPhone 转移到 Android
从 iPhone 换到 Android 手机时,你可能需要保留重要的数据,例如通讯录。好在,将通讯录从 iPhone 转移到 Android 手机非常简单,你可以从本文中学习 6 种可靠的方法,确保随时保持连接,不错过任何信息。 第 1…...
Java面试专项一-准备篇
一、企业简历筛选规则 一般企业的简历筛选流程:首先由HR先筛选一部分简历后,在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如:Boss直聘(招聘方平台) 直接按照条件进行筛选 例如:…...
【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统
目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索(基于物理空间 广播范围)2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...
OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()
操作系统:ubuntu22.04 OpenCV版本:OpenCV4.9 IDE:Visual Studio Code 编程语言:C11 算法描述 在 GPU 上对图像执行 均值漂移滤波(Mean Shift Filtering),用于图像分割或平滑处理。 该函数将输入图像中的…...
无人机侦测与反制技术的进展与应用
国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机(无人驾驶飞行器,UAV)技术的快速发展,其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统,无人机的“黑飞”&…...
省略号和可变参数模板
本文主要介绍如何展开可变参数的参数包 1.C语言的va_list展开可变参数 #include <iostream> #include <cstdarg>void printNumbers(int count, ...) {// 声明va_list类型的变量va_list args;// 使用va_start将可变参数写入变量argsva_start(args, count);for (in…...
毫米波雷达基础理论(3D+4D)
3D、4D毫米波雷达基础知识及厂商选型 PreView : https://mp.weixin.qq.com/s/bQkju4r6med7I3TBGJI_bQ 1. FMCW毫米波雷达基础知识 主要参考博文: 一文入门汽车毫米波雷达基本原理 :https://mp.weixin.qq.com/s/_EN7A5lKcz2Eh8dLnjE19w 毫米波雷达基础…...
MySQL 主从同步异常处理
阅读原文:https://www.xiaozaoshu.top/articles/mysql-m-s-update-pk MySQL 做双主,遇到的这个错误: Could not execute Update_rows event on table ... Error_code: 1032是 MySQL 主从复制时的经典错误之一,通常表示ÿ…...
