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

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

题目链接&#xff1a;Friendly Spiders 首先我们可以考虑暴力做法&#xff0c;那就是每两个蜘蛛判断一下gcd&#xff0c;如果不等于1&#xff0c;那就连条边&#xff0c;这样的话时间复杂度是O&#xff08;n^2&#xff09;&#xff0c;显然超时&#xff0c;因此我们可以采用类似…...

【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语言的常量、枚举、作用域

本专栏将从基础开始&#xff0c;循序渐进&#xff0c;由浅入深讲解Go语言&#xff0c;希望大家都能够从中有所收获&#xff0c;也请大家多多支持。 查看相关资料与知识库 专栏地址:Go专栏 如果文章知识点有错误的地方&#xff0c;请指正&#xff01;大家一起学习&#xff0c;…...

第十一章 数据结构

第十一章 数据结构 11.1 数组 数组是元素的顺序集合&#xff0c;通常这些元素具有相同的数据类型 索引表示元素在数组中的顺序号&#xff0c;顺序号从数组开始处计数 数组元素通过索引被独立给出了地址&#xff0c;数组整体上有一个名称&#xff0c;但每个元素利用数组的的…...

LeetCode704 二分查找

前言 题目&#xff1a; 704.二分查找 文档&#xff1a; 代码随想录——二分查找 编程语言&#xff1a; C 解题状态&#xff1a; 解答错误&#xff0c;变量定义位置错误。 思路 有序数组的查找&#xff0c;最直接的思路应该就是二分查找。但是在查找的过程中要考虑到区间的边界…...

[言简意赅] Matlab生成FPGA端rom初始化文件.coe

&#x1f38e;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要在其他机器上单独运行扫描&#xff0c;必须先连接RLMLicense管理器&#xff0c;如何连接&#xff1f; 3、软硬件环境 1、软件版本&#xff1a;HelixQAC23.04 2、机器环境…...

从等保测评看行业安全趋势:洞察与预测

在当今数字化时代&#xff0c;网络安全已成为各行各业的头等大事。等保测评&#xff08;等级保护测评&#xff09;&#xff0c;作为国家对信息系统安全的重要管理手段&#xff0c;不仅关乎企业的合规性&#xff0c;更是行业安全水平的重要衡量标准。本文将从等保测评的视角出发…...

HTTP模块(二)

HTTP 设置 HTTP 响应报文 HTTP报文常见属性&#xff1a; const http require(http);const server http.createServer((request, response) > {// 设置请求状态码 2xx 4xx 5xxresponse.statusCode 200;// 设置请求描述 了解即可response.statusMessage hello// 指定响…...

引入缓存带来的问题以及解决方案

目录 前言 问题与解决方案 缓存击穿 缓存穿透 缓存雪崩 缓存一致性 前言 在提升接口性能的方案中&#xff0c;毫无疑问&#xff0c;使用缓存是最有效果的&#xff0c;但同时也会带来新的问题。 缓存击穿缓存穿透缓存雪崩缓存一致性 以上问题都是引入缓存需要考虑的&am…...

力扣39题:组合总和的 Java 实现

引言 力扣&#xff08;LeetCode&#xff09;是一个在线编程平台&#xff0c;提供了大量的编程题目供开发者练习。第39题“组合总和”是一个经典的回溯算法问题&#xff0c;要求找出所有可能的组合&#xff0c;使得组合中的数字之和等于给定的目标值。本文将介绍如何使用 Java …...

使用el-table实现自动滚动

文章目录 概要技术实现完整代码 概要 在前端开发大屏的时候&#xff0c;我们会用到表格数据展示&#xff0c;有时候为了使用户体验更加好&#xff0c;会增加表格自动滚动。下边我将以示例代码&#xff0c;用element UI的el-table来讲一下。 技术实现 1 .增加dom监听&#xf…...

Angular由一个bug说起之八:实践中遇到的一个数据颗粒度的问题

互联网产品离不开数据处理&#xff0c;数据处理有一些基本的原则包括&#xff1a;准确性、‌完整性、‌一致性、‌保密性、‌及时性。‌ 准确性&#xff1a;是数据处理的首要目标&#xff0c;‌确保数据的真实性和可靠性。‌准确的数据是进行分析和决策的基础&#xff0c;‌因此…...

day13(DNS域名解析)

今天内容&#xff1a; 1、逆向解析 2、多域名 3、时间服务器 4、主从配置 1.设置逆向解析 &#xff08;1&#xff09;永久配置我们自己的DNS服务器 &#xff08;2&#xff09;关闭NetworkManager服务 NetworkManager 的自动管理功能可能会干扰定制化的网络配置。 在需要切换…...

uboot的mmc partconf命令

文章目录 命令格式参数解释具体命令解释总结 mmc partconf 是一个用于配置 MMC (MultiMediaCard) 分区的 U-Boot 命令。具体来说&#xff0c;这个命令允许你设置或读取 MMC 卡的分区配置参数。让我们详细解释一下 mmc partconf 0 0 1 0 命令的含义。 命令格式 mmc partconf &…...

数据结构经典测题3

1. 设有定义&#xff1a; char *p; &#xff0c;以下选项中不能正确将字符串赋值给字符型指针 p 的语句是【多选】&#xff08; &#xff09; A: pgetchar(); B: scanf("%s",p); C: char s[]"china"; ps; D: *p"china"; 答案为ABD A选项&…...

tensorboard add_text() 停止自动为尖括号标记添加配对的结束括号</>

问题 调用tensorboard的add_text()记录文本信息时&#xff0c;如果文本中含有含尖括号的标记&#xff0c;就会被自动识别为html标记&#xff0c;因此tensorboard会自动生成对应的带斜杠的结束标记。 例如要记录的文本是 abc<abc>&#xff0c;在tensorboard中就会显示为a…...

sql-libs通关详解

1-4关 1.第一关 我们输入?id1 看回显&#xff0c;通过回显来判断是否存在注入&#xff0c;以及用什么方式进行注入&#xff0c;直接上图 可以根据结果指定是字符型且存在sql注入漏洞。因为该页面存在回显&#xff0c;所以我们可以使用联合查询。联合查询原理简单说一下&…...

【STM32】当按键具有上拉电阻时GPIO应该配置什么模式?怎么用按键去控制LED翻转?

当按键具有上拉电阻时&#xff0c;可以通过正确配置STM32的GPIO端口和编写相应的控制代码来实现按键控制LED灯的功能。具体来说&#xff0c;需要配置按键所连接的GPIO端口为输入模式&#xff0c;并启用内部上拉电阻&#xff0c;这样在按键未操作时该端口保持高电平状态&#xf…...

EXO-chatgpt_api 解释

目录 chatgpt_api 解释 resolve_tinygrad_tokenizer 函数 resolve_tokenizer 函数 调试和日志记录​​​​​​​ 参数 返回值 初始化方法 __init__ 异步方法 注意事项 chatgpt_api 解释 展示了如何在一个项目中组织和导入各种库、模块和类,以及如何进行一些基本的We…...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

简易版抽奖活动的设计技术方案

1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

多模态图像修复系统:基于深度学习的图片修复实现

多模态图像修复系统:基于深度学习的图片修复实现 1. 系统概述 本系统使用多模态大模型(Stable Diffusion Inpainting)实现图像修复功能,结合文本描述和图片输入,对指定区域进行内容修复。系统包含完整的数据处理、模型训练、推理部署流程。 import torch import numpy …...

C# 表达式和运算符(求值顺序)

求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如&#xff0c;已知表达式3*52&#xff0c;依照子表达式的求值顺序&#xff0c;有两种可能的结果&#xff0c;如图9-3所示。 如果乘法先执行&#xff0c;结果是17。如果5…...

NPOI操作EXCEL文件 ——CAD C# 二次开发

缺点:dll.版本容易加载错误。CAD加载插件时&#xff0c;没有加载所有类库。插件运行过程中用到某个类库&#xff0c;会从CAD的安装目录找&#xff0c;找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库&#xff0c;就用插件程序加载进…...

从面试角度回答Android中ContentProvider启动原理

Android中ContentProvider原理的面试角度解析&#xff0c;分为​​已启动​​和​​未启动​​两种场景&#xff1a; 一、ContentProvider已启动的情况 1. ​​核心流程​​ ​​触发条件​​&#xff1a;当其他组件&#xff08;如Activity、Service&#xff09;通过ContentR…...