1775D - Friendly Spiders
题目链接:Friendly Spiders
首先我们可以考虑暴力做法,那就是每两个蜘蛛判断一下gcd,如果不等于1,那就连条边,这样的话时间复杂度是O(n^2),显然超时,因此我们可以采用类似二分图的方法去建,首先把一个数的所有质因数分解,然后连一条边,将质因数+n,因为这代表虚点,因为我们要求的是蜘蛛之间的关系,可以通过它们有相同的质因数去建立关系,因此边就建完了,然后跑一遍bfs,最后倒着跑一遍dfs求方案数即可。
代码附上:
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 6e5+5;
int n,st,ed;
int a[N];
int d[N];
vector<int>g[N];
vector<int>ans;void bfs(int sx){queue<int>q;q.push(sx);d[sx]=1;while(!q.empty()){int x=q.front();q.pop();for(const auto &y:g[x]){if(!d[y]){d[y]=d[x]+1;q.push(y);}}}return;
}void dfs(int x){if(x==st)return;for(const auto &y:g[x]){if(d[y]==d[x]-1){ans.push_back(y);dfs(y);return;}}
}void solve(){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];cin>>st>>ed;for(int i=1;i<=n;i++){int x=a[i];for(int j=2;j*j<=x;j++){if(x%j==0){g[i].push_back(n+j);g[n+j].push_back(i);while(x%j==0)x/=j;}}if(x>1){g[i].push_back(n+x);g[n+x].push_back(i);}}bfs(st);if(!d[ed]){cout<<-1<<"\n";return;}ans.push_back(ed);dfs(ed);reverse(ans.begin(),ans.end());cout<<(ans.size()+1)/2<<"\n";//除去虚点for(int i=0;i<ans.size();i++){if(ans[i]<=n)cout<<ans[i]<<" ";}cout<<"\n";return;}signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int t=1;while(t--){solve();}return 0;
}
相关文章:
1775D - Friendly Spiders
题目链接:Friendly Spiders 首先我们可以考虑暴力做法,那就是每两个蜘蛛判断一下gcd,如果不等于1,那就连条边,这样的话时间复杂度是O(n^2),显然超时,因此我们可以采用类似…...
【python】OpenCV—Point Polygon Test
文章目录 1、完整代码2、涉及到的库cv2.pointPolygonTestcv2.minMaxLoc 1、完整代码 from __future__ import print_function from __future__ import division import cv2 as cv import numpy as np # Create an image r 100 src np.zeros((4*r, 4*r), dtypenp.uint8) # 创…...
6 Go语言的常量、枚举、作用域
本专栏将从基础开始,循序渐进,由浅入深讲解Go语言,希望大家都能够从中有所收获,也请大家多多支持。 查看相关资料与知识库 专栏地址:Go专栏 如果文章知识点有错误的地方,请指正!大家一起学习,…...
第十一章 数据结构
第十一章 数据结构 11.1 数组 数组是元素的顺序集合,通常这些元素具有相同的数据类型 索引表示元素在数组中的顺序号,顺序号从数组开始处计数 数组元素通过索引被独立给出了地址,数组整体上有一个名称,但每个元素利用数组的的…...
LeetCode704 二分查找
前言 题目: 704.二分查找 文档: 代码随想录——二分查找 编程语言: C 解题状态: 解答错误,变量定义位置错误。 思路 有序数组的查找,最直接的思路应该就是二分查找。但是在查找的过程中要考虑到区间的边界…...
[言简意赅] Matlab生成FPGA端rom初始化文件.coe
🎎Matlab生成FPGA端rom初始化文件.coe 本文主打言简意赅。 函数源码 function gencoeInitialROM(width, depth, signal, filepath)% gencoeInitialROM - 生成 Xilinx ROM 初始化格式的 COE 文件%% 输入参数:% width - ROM 数据位宽% depth - ROM 数据深度% s…...
【QAC】分布式部署下其他机器如何连接RLM
1、 文档目标 解决分布式部署下其他机器如何连接RLMLicense管理器。 2、 问题场景 分布式部署下QAC要在其他机器上单独运行扫描,必须先连接RLMLicense管理器,如何连接? 3、软硬件环境 1、软件版本:HelixQAC23.04 2、机器环境…...
从等保测评看行业安全趋势:洞察与预测
在当今数字化时代,网络安全已成为各行各业的头等大事。等保测评(等级保护测评),作为国家对信息系统安全的重要管理手段,不仅关乎企业的合规性,更是行业安全水平的重要衡量标准。本文将从等保测评的视角出发…...
HTTP模块(二)
HTTP 设置 HTTP 响应报文 HTTP报文常见属性: const http require(http);const server http.createServer((request, response) > {// 设置请求状态码 2xx 4xx 5xxresponse.statusCode 200;// 设置请求描述 了解即可response.statusMessage hello// 指定响…...
引入缓存带来的问题以及解决方案
目录 前言 问题与解决方案 缓存击穿 缓存穿透 缓存雪崩 缓存一致性 前言 在提升接口性能的方案中,毫无疑问,使用缓存是最有效果的,但同时也会带来新的问题。 缓存击穿缓存穿透缓存雪崩缓存一致性 以上问题都是引入缓存需要考虑的&am…...
力扣39题:组合总和的 Java 实现
引言 力扣(LeetCode)是一个在线编程平台,提供了大量的编程题目供开发者练习。第39题“组合总和”是一个经典的回溯算法问题,要求找出所有可能的组合,使得组合中的数字之和等于给定的目标值。本文将介绍如何使用 Java …...
使用el-table实现自动滚动
文章目录 概要技术实现完整代码 概要 在前端开发大屏的时候,我们会用到表格数据展示,有时候为了使用户体验更加好,会增加表格自动滚动。下边我将以示例代码,用element UI的el-table来讲一下。 技术实现 1 .增加dom监听…...
Angular由一个bug说起之八:实践中遇到的一个数据颗粒度的问题
互联网产品离不开数据处理,数据处理有一些基本的原则包括:准确性、完整性、一致性、保密性、及时性。 准确性:是数据处理的首要目标,确保数据的真实性和可靠性。准确的数据是进行分析和决策的基础,因此…...
day13(DNS域名解析)
今天内容: 1、逆向解析 2、多域名 3、时间服务器 4、主从配置 1.设置逆向解析 (1)永久配置我们自己的DNS服务器 (2)关闭NetworkManager服务 NetworkManager 的自动管理功能可能会干扰定制化的网络配置。 在需要切换…...
uboot的mmc partconf命令
文章目录 命令格式参数解释具体命令解释总结 mmc partconf 是一个用于配置 MMC (MultiMediaCard) 分区的 U-Boot 命令。具体来说,这个命令允许你设置或读取 MMC 卡的分区配置参数。让我们详细解释一下 mmc partconf 0 0 1 0 命令的含义。 命令格式 mmc partconf &…...
数据结构经典测题3
1. 设有定义: char *p; ,以下选项中不能正确将字符串赋值给字符型指针 p 的语句是【多选】( ) A: pgetchar(); B: scanf("%s",p); C: char s[]"china"; ps; D: *p"china"; 答案为ABD A选项&…...
tensorboard add_text() 停止自动为尖括号标记添加配对的结束括号</>
问题 调用tensorboard的add_text()记录文本信息时,如果文本中含有含尖括号的标记,就会被自动识别为html标记,因此tensorboard会自动生成对应的带斜杠的结束标记。 例如要记录的文本是 abc<abc>,在tensorboard中就会显示为a…...
sql-libs通关详解
1-4关 1.第一关 我们输入?id1 看回显,通过回显来判断是否存在注入,以及用什么方式进行注入,直接上图 可以根据结果指定是字符型且存在sql注入漏洞。因为该页面存在回显,所以我们可以使用联合查询。联合查询原理简单说一下&…...
【STM32】当按键具有上拉电阻时GPIO应该配置什么模式?怎么用按键去控制LED翻转?
当按键具有上拉电阻时,可以通过正确配置STM32的GPIO端口和编写相应的控制代码来实现按键控制LED灯的功能。具体来说,需要配置按键所连接的GPIO端口为输入模式,并启用内部上拉电阻,这样在按键未操作时该端口保持高电平状态…...
EXO-chatgpt_api 解释
目录 chatgpt_api 解释 resolve_tinygrad_tokenizer 函数 resolve_tokenizer 函数 调试和日志记录 参数 返回值 初始化方法 __init__ 异步方法 注意事项 chatgpt_api 解释 展示了如何在一个项目中组织和导入各种库、模块和类,以及如何进行一些基本的We…...
接口测试中缓存处理策略
在接口测试中,缓存处理策略是一个关键环节,直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性,避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明: 一、缓存处理的核…...
零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?
一、核心优势:专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发,是一款收费低廉但功能全面的Windows NAS工具,主打“无学习成本部署” 。与其他NAS软件相比,其优势在于: 无需硬件改造:将任意W…...
java 实现excel文件转pdf | 无水印 | 无限制
文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...
STM32F4基本定时器使用和原理详解
STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...
家政维修平台实战20:权限设计
目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系,主要是分成几个表,用户表我们是记录用户的基础信息,包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题,不同的角色…...
在四层代理中还原真实客户端ngx_stream_realip_module
一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡(如 HAProxy、AWS NLB、阿里 SLB)发起上游连接时,将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后,ngx_stream_realip_module 从中提取原始信息…...
微信小程序 - 手机震动
一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注:文档 https://developers.weixin.qq…...
页面渲染流程与性能优化
页面渲染流程与性能优化详解(完整版) 一、现代浏览器渲染流程(详细说明) 1. 构建DOM树 浏览器接收到HTML文档后,会逐步解析并构建DOM(Document Object Model)树。具体过程如下: (…...
现代密码学 | 椭圆曲线密码学—附py代码
Elliptic Curve Cryptography 椭圆曲线密码学(ECC)是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础,例如椭圆曲线数字签…...
EtherNet/IP转DeviceNet协议网关详解
一,设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络,本网关连接到EtherNet/IP总线中做为从站使用,连接到DeviceNet总线中做为从站使用。 在自动…...
