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

交换瓶子(图论 贪心）

news 来源：原创 2025/7/6 2:58:56

1224. 交换瓶子 - AcWing题库

 把每一个瓶子看成一个点，从每个瓶子向他应该在的那个位置的瓶子连一条边

通过这个方式，我们就可以连出n条边 

观察可以发现这些图有特点：

n个点 连成n条边 

因为每个点会指向它应该在的位置的那个点，他所在位置的对应的点会指向他，所以每个点的出度和入度都为1

不会有以下情况

都会是一个一个环

 

最终希望完成的样子是一个升序的 ，把整个图都变成自环

对点进行操作，分两种情况：

1️⃣交换同一个环内的点

 

 如图，交换1 和 3的位置，意味着改变点1和点2的出边，让点1的出边指向点2先前出边方向，点2指向点1 先前出边的方向

可以发现将一个环裂开成了两个环

2️⃣交换不同环中的点

 可以发现合并了两个环

初始的时候我们假设有k个环，n个点，我们的目标是将所有的环拆解成自环，每次操作最多增加一个环，因此次数 >= n-k次，只要有一个环里面存在两个或以上的点，我们就必然可以把它分裂一下，变成两个环，所以必然存在一种方案，可以使我们恰好操作n-k次就可以把k个环分解成n个环

所以答案>=n-k 且可以取到n-k

#include <iostream>using namespace std;const int N = 1e4 + 10;int n;
int b[N];
bool st[N];int main() {cin >> n;for (int i = 1;i <= n;i++) {cin >> b[i];}int cnt = 0;for (int i = 1;i <= n;i++) {if (!st[i]) {cnt++;for (int j = i;!st[j];j=b[j]) {st[j] = true;}}}int res = n - cnt;cout << res << endl;return 0;
}

相关文章：

交换瓶子(图论 贪心）

1224. 交换瓶子 - AcWing题库 把每一个瓶子看成一个点&#xff0c;从每个瓶子向他应该在的那个位置的瓶子连一条边 通过这个方式&#xff0c;我们就可以连出n条边 观察可以发现这些图有特点&#xff1a; n个点 连成n条边 因为每个点会指向它应该在的位置的那个点&#xff…...

编程日记 2025/7/6 2:58:56

汽车升级到底应不应该设置“可取消“功能

最近&#xff0c;汽车OTA&#xff08;Over-the-Air&#xff09;升级频频成为车主讨论的热点。有些车主反映&#xff0c;一些升级增加了实用功能&#xff0c;而另一些却让体验变得复杂甚至带来不便。于是&#xff0c;大家不禁发问&#xff1a;汽车升级功能究竟应不应该允许“可取…...

编程日记 2025/7/3 20:49:42

Mac电脑钓鱼到拿下核心权限

目录 一. 前言 二. PKG后门制作阶段 2.1 环境准备 2.2 制作过程 2.3 成功上线 三 . 浏览器密码抓取 四. 权限维持 1. 手动权限维持 2. MSF自动化维持 五. 参考文章 一. 前言 攻防对抗强度和难度日益演进，传统的渗透测试思路成本逐渐提高，钓鱼已经成为当下攻击者最常…...

编程日记 2025/7/3 1:07:20

Docker多架构镜像构建踩坑记

背景 公司为了做信创项目的亮点&#xff0c;需要将现有的一套在X86上运行的应用系统迁移到ARM服务器上运行&#xff0c;整个项目通过后端Java&#xff0c;前端VUEJS开发通过CICD做成Docker镜像在K8S里面运行。但是当前的CICD产品不支持ARM的镜像构建&#xff0c;于是只能手工构…...

编程日记 2025/6/30 20:13:30

docker 架构详解

Docker架构是基于客户端-服务器&#xff08;C/S&#xff09;模式的&#xff0c;包含多个关键组件&#xff0c;以确保容器化应用的高效构建、管理和运行。以下是对Docker架构的详细解析&#xff1a; Docker 架构概述 Docker 架构采用客户端-服务器&#xff08;C/S&#xff09;…...

编程日记 2025/7/1 21:34:12

05-标准库开发-STM32-IIC协议

七、STM32中IIC协议 概述 Inter-Integrated Circuit (IIC)&#xff0c;也常称为I2C&#xff08;I squared C&#xff09;&#xff0c;是一种同步、串行、半双工通信总线协议。它主要用于连接低速外围设备到处理器或微控制器上&#xff0c;如MPU6050姿态传感器、OLED显示屏、存…...

编程日记 2025/6/29 18:55:46

vue 封装全局过滤器

1.找到utils下创建fifilter.js 一些常用的过滤方法 export const filters {//url解码urlCode: value > {if (!value) return let v decodeURIComponent(value)let bigIndex v.lastIndexOf(/)let endIndex v.lastIndexOf(.)let url v.substring(bigIndex 1, endIndex)…...

编程日记 2025/7/4 2:40:01

【PlantUML系列】流程图（四）

目录 目录 一、基础用法 1.1 开始和结束 1.2 操作步骤 1.3 条件判断 1.4 并行处理 1.5 循环 1.6 分区 1.7 泳道 一、基础用法 1.1 开始和结束 开始一般使用start关键字&#xff1b;结束一般使用stop/end关键字。基础用法包括&#xff1a; start ... stopstart ...…...

编程日记 2025/7/4 14:12:29

MATLAB中的合并分类数组

目录 创建分类数组 串联分类数组 创建具有不同类别的分类数组 串联具有不同类别的数组 分类数组的并集 此示例演示了如何合并两个分类数组。 创建分类数组 创建分类数组 A&#xff0c;其中包含教室 A 中的 25 个学生的首选午餐饮料。 rng(default) A randi(3,[25,1]); …...

编程日记 2025/6/30 20:48:38

流编辑器sed（stream editor）

一.sed简介 sed是一种流编辑器&#xff0c;处理时&#xff0c;把当前处理的行存储在临时缓冲区中&#xff0c;称为模式空间&#xff0c;接着用sed命令处 理缓冲区中的内容&#xff0c;处理完成后&#xff0c;把缓冲区的内容送往屏幕。接着处理下一行&#xff0c;这样不断重复&…...

编程日记 2025/7/2 23:42:20

R语言的数据结构--矩阵

【图书推荐】《R语言医学数据分析实践》-CSDN博客 《R语言医学数据分析实践 李丹 宋立桓 蔡伟祺 清华大学出版社9787302673484》【摘要 书评 试读】- 京东图书 (jd.com) R语言医学数据分析实践-R语言的数据结构-CSDN博客 矩阵是一个二维数组&#xff0c;矩阵中的元素都具有相…...

编程日记 2025/7/4 23:45:26

使用 Python 爬取某网站简历模板（bs4/lxml+协程）

使用 Python 爬取站长素材简历模板 简介 在本教程中&#xff0c;我们将学习如何使用 Python 来爬取站长素材网站上的简历模板。我们将使用requests和BeautifulSoup库来发送 HTTP 请求和解析 HTML 页面。本教程将分为两个部分&#xff1a;第一部分是使用BeautifulSoup的方法&am…...

编程日记 2025/7/5 5:35:31

19 go语言（golang） - 通过反射手动实现json序列化

一、json 在 Go 语言中&#xff0c;JSON 序列化和反序列化通常通过标准库 encoding/json 来实现。这个包提供了简单易用的接口来将 Go 数据结构转换为 JSON 格式字符串&#xff08;序列化&#xff09;&#xff0c;以及从 JSON 字符串解析出 Go 数据结构&#xff08;反序列化&a…...

编程日记 2025/7/6 2:13:45

Scala:隐式转换

隐式转换的定义 //隐式转换&#xff1a;编译器自动滴&#xff0c;偷偷滴&#xff0c;把数据A->B object test04 {def main(args: Array[String]): Unit {val i:Int1//把Int类型&#xff0c;转化成Double类型//Int -> Double//隐式转换失败val b:Double1//隐式转换失败v…...

编程日记 2025/7/1 19:48:19

UVM之寄存器模型生成

1.采用python脚本生成寄存器模型 首先用excel表格做好寄存器描述 然后编写脚本生成.ralf文件 &#xff08;1&#xff09;首先通过openpyxl读取EXCEL表格&#xff0c; workbook openpyxl.load_workbook(reg.xlsx) # 返回一个workbook数据类型的值 &#xff08;2&#xff…...

编程日记 2025/7/2 21:13:48

PL/SQL批量生成数据

在PL/SQL中生成大量模拟数据&#xff0c;特别是当你需要生成大量记录&#xff08;如1亿条&#xff09;时&#xff0c;有几种常见的方式可以提高生成数据的效率和性能。以下是一些常用的方法和最佳实践&#xff1a; 1. 使用PL/SQL块批量生成数据 PL/SQL块可以通过循环生成大量…...

编程日记 2025/7/1 16:27:07

Xcode模拟器运行报错：The request was denied by service delegate

Xcode模拟器运行报错&#xff1a;The request was denied by service delegate 造成的原因: &#xff08;1&#xff09;新的苹果M系列芯片的Mac电脑 &#xff08;2&#xff09;此电脑首次安装启动Xcode的应用程序 &#xff08;3&#xff09;此电脑未安装Rosetta 2 解决方法: …...

编程日记 2025/7/3 11:14:53

2024小迪安全基础入门第十课

目录 一、传输格式&数据-类型&编码&算法 1. 传输格式&#xff1a; 2. 传输数据&#xff1a; 3. 影响与渗透测试&#xff1a; #传输格式 #传输数据 二、密码存储&混淆-不可逆&非对称性 1. 密码存储&#xff1a; 2. 密码存储的影响&#xff1a; 3.…...

编程日记 2025/7/2 19:56:25

Redisson分布式限流器

Redisson分布式限流器 一、使用1.1、方法1.2、示例 二、原理2.1、设置限流器2.2、获取令牌 三、总结 最近有需求在做分布式限流&#xff0c;调研的限流框架大概有&#xff1a; 1、spring cloud gateway集成redis限流,但属于网关层限流 2、阿里Sentinel,功能强大、带监控平台 …...

编程日记 2025/7/2 4:20:53

xvisor调试记录

Xvisor是一种开源hypervisor，旨在提供完整、轻量、移植且灵活的虚拟化解决方案，属于type-1类型的虚拟机，可以直接在裸机上启动。 启动xvisor步骤： 1、搭建riscv编译环境 首先从github上下载riscv-gnu-toolchain很费劲，建议直接从国内的源下载 git clone https://gitee…...

编程日记 2025/7/3 1:04:50

Android问题记录 - Inconsistent JVM-target compatibility detected for tasks

文章目录 前言开发环境问题描述问题分析解决方案补充内容最后 前言 前段时间升级Android Studio后修复了一堆问题&#xff0c;详情请看&#xff1a;Android问题记录 - 适配Android Studio Ladybug/Java 21/AGP 8.0&#xff08;持续更新&#xff09;。我以为问题已经全部解决了…...

编程日记 2025/7/2 4:21:37

【Python系列】使用 `psycopg2` 连接 PostgreSQL 数据库

???欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学习,不断总结,共同进步,活到老学到老…...

编程日记 2025/7/1 8:36:33

家庭路由器跑PCND的优点

在当今数字化的时代&#xff0c;PCDN&#xff08;Peer-to-Peer Content Delivery Network&#xff09;技术逐渐走入人们的视野&#xff0c;有人考虑在家庭路由器上跑PCDN&#xff0c;下面是优点&#xff1a; 1.资源利用最大化 家庭网络在很多时候存在闲置的带宽和计算资源。通…...

编程日记 2025/7/2 16:32:51

ASP.NET Core API + MySql

环境 数据库&#xff1a; mysql8.0 后端&#xff1a; vs2022 ASP.NET Core API .net 8 前端&#xff1a; Hbuilderx bootstrap 5.3.0 jquery v3.7.1 bootstrap-table 1.23.5 创建项目 添加资源包 AutoMapper Microsoft.EntityFrameworkCore.Tools 8.0.0 Pomelo.EntityFramew…...

编程日记 2025/7/1 22:55:30

torch.optim.lr_scheduler.ReduceLROnPlateau

torch.optim.lr_scheduler.ReduceLROnPlateau 是 PyTorch 中的一种学习率调度器&#xff0c;主要用于在模型训练过程中根据某些指标&#xff08;如验证损失&#xff09;动态调整学习率。它是一种基于性能指标动态调整学习率的策略&#xff0c;而不是预定义的固定时间调整。 主要…...

编程日记 2025/7/5 14:02:12

Dubbo

官方文档&#xff1a; Java SDK 手册 | Apache Dubbo 一 RPC及Dubbo 1 什么是RPC dubbo是⼀款⾼性能的rpc框架。什么是rpc呢&#xff1f; rpc是⼀种协议&#xff1a;是⼀种远程过程调⽤&#xff08;remote procudure call&#xff09;协议 rpc协议是在应⽤层之上的协议&…...

编程日记 2025/7/3 7:59:53

算法1（蓝桥杯18）-删除链表的倒数第 N 个节点

问题&#xff1a; 给你一个链表&#xff0c;删除链表的倒数第 n 个节点&#xff0c;并且返回链表的头节点。 输入&#xff1a;head 1 -> 2 -> 3 -> 4 -> 5 -> null, n 2 输出&#xff1a;1 -> 2 -> 3 -> 5 -> null输入&#xff1a;head 1 ->…...

编程日记 2025/7/5 9:53:46

SEC_ASA 第一天作业

拓扑&#xff1a; 实验需求&#xff1a; 注意&#xff1a;在开始作业之前必须先读“前言”&#xff0c;以免踩坑&#xff01;&#xff01;&#xff01;&#xff08;☞敢点我试试&#xff09; 按照拓扑图配置VLAN连接。 注意&#xff1a;ASA防火墙的 Gi0/1口需要起子接口&#x…...

编程日记 2025/7/4 0:02:38

《C语言程序设计现代方法》note-8 指针和数组的关系

文章目录 助记提要12章 指针和数组12.1 指针的算术运算12.2 指针用于数组处理结合使用*和运算符 12.3 数组名作为指针数组名可以用作指针指针也可以当做数组名数组型实参 12.4 指针和多维数组处理每个元素处理行处理列多维数组名做指针 12.5 指针和变长数组 助记提要 指针支持…...

编程日记 2025/6/28 18:16:52

安科瑞电能质量治理产品在分布式光伏电站的应用-安科瑞黄安南

1.概述 随着全球对可再生能源需求的增加&#xff0c;分布式光伏电站的建设和发展迅速。然而&#xff0c;分布式光伏电站的运行过程中面临着一系列问题&#xff0c;比如导致企业关口计量点功率因数过低、谐波污染等。这些问题不仅影响光伏电站自身的运行效率&#xff0c;还会对…...

编程日记 2025/7/1 20:22:05

JavaScript 的原生数组方法和 Vue 的响应式系统之间的差异

发现宝藏 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。【宝藏入口】。 JavaScript 的原生数组方法和 Vue 的响应式系统之间的差异主要体现在 Vue 如何追踪数组的变化&#xff0c;以及 Vue 如何处理数组…...

编程日记 2025/6/28 19:59:33

项目组件框架介绍[bRPC]

文章目录 前言bRPC安装bRPC的简单使用protobuf简单使用Echo服务远程调用Echo服务 与etcd关联 前言 bRPC是百度开源的一款工业级RPC框架&#xff0c;功能强大, 常用于搜索、存储、机器学习、广告、推荐等高性能系统。 bRPC安装 使用源码安装即可, 在安装前要确认依赖 sudo apt…...

编程日记 2025/7/1 14:57:17

基于MobileNetV3架构动物声音分类识别与应用系统实现

1.摘要 本文主要实现了一个基于MobileNetV3架构的深度学习模型用于动物声音分类识别任务。该MobileNetV3是一种轻量级的卷积神经网络&#xff0c;旨在实现高效分类性能&#xff0c;本章在猫、狗、海豚等三个动物声音(.wav数据集&#xff09;上进行了训练和测试&#xff0c;即在…...

编程日记 2025/7/3 5:37:44

ragflow连ollama时出现的Bug

ragflow和ollama连接后&#xff0c;已经添加了两个模型但是ragflow仍然一直warn&#xff1a;Please add both embedding model and LLM in Settings &#xff1e; Model providers firstly.这里可能是我一开始拉取的镜像容器太小&#xff0c;容不下当前添加的模型&#xff0c;导…...

编程日记 2025/7/3 6:36:12

[大数据]Hudi编译集成

1. 编译环境准备 相关组件版本如下&#xff1a; Hadoop3.3.1Hive3.1.3Flink1.13.6&#xff0c;scala-2.12Spark3.3.1&#xff0c;scala-2.12 1&#xff09;安装Maven &#xff08;1&#xff09;上传apache-maven-3.6.1-bin.tar.gz到/opt/software目录&#xff0c;并解压更名…...

编程日记 2025/7/5 20:46:03

rk3588-ubuntu22.04系统网关实现路由器功能：

rk3588-ubuntu22.04系统网关实现路由器功能&#xff1a; 场景需求描述&#xff1a; 需求背景&#xff1a; 场景一&#xff1a;通过网线eth0/(路由器wlan0)访问外网&#xff1a; 如果网关 和 设备所处的环境可以通过网线联网或者路由器联网&#xff0c;那么不需要将网关配置成…...

编程日记 2025/7/6 2:29:29

Python部署教程-Python项目怎样在Pycharm中运行

大家好&#xff0c;我是程序员徐师兄&#xff0c;今天为大家带来的是Python部署教程-Python项目怎样在Pycharm中运行。Python安装部署教程&#xff0c;包括软件的下载&#xff0c;软件的安装。该系统采用 Python语言开发&#xff0c;flask、Django 框架&#xff0c;MySql 作为数…...

编程日记 2025/7/5 10:42:58

代码随想录算法训练营第51期第14天 | 226. 翻转二叉树、101. 对称二叉树、104.二叉树的最大深度、111.二叉树的最小深度

226. 翻转二叉树 226. 翻转二叉树https://leetcode.cn/problems/invert-binary-tree/1.昨天忘了声明&#xff0c;如果都用C的话&#xff0c;我大概率写不完&#xff0c;所以思路方面&#xff0c;我可能考虑用pyhon先写&#xff0c;后续会用文心一言转换成C 2.这里可以直接用层…...

编程日记 2025/7/5 9:24:04

C/C++常见符号与运算符

C/C常见符号与运算符对照表 符号用法与意义与Java类比:在条件运算符中 (cond ? x : y) 表示条件为假的分支&#xff1b;在 switch-case 中如 case 1:表示标签结束点&#xff1b;在自定义标签如 label: 中用于 goto 跳转Java中? :三元运算相同&#xff1b;switch-case中也有:…...

编程日记 2025/7/4 8:40:10

maven报错“找不到符号“

问题 springboot项目 maven编译打包过程&#xff0c;报错"找不到符号" 解决 很多网上方法都试过&#xff0c;都没用 换jdk&#xff0c;把17->21...

编程日记 2025/7/3 10:42:02

开源数据同步中间件（Dbsyncer）简单玩一下 mysql to mysql 的增量，全量配置

一、什么是Dbsyncer 1、介绍 Dbsyncer是一款开源的数据同步中间件&#xff0c;提供MySQL、Oracle、SqlServer、PostgreSQL、Elasticsearch(ES)、Kafka、File、SQL等同步场景&#xff0c;支持上传插件自定义同步转换业务&#xff0c;提供监控全量和增量数据统计图、应用性能预警…...

编程日记 2025/7/4 16:09:23

【Kubernetes理论篇】容器集群管理系统Kubernetes（K8S）

Kubernetes集群部署基本管理实战 这么好的机会&#xff0c;还在等什么&#xff01; 01、Kubernetes 概述 K8S是什么 K8S 的全称为 Kubernetes (K12345678S)&#xff0c;PS&#xff1a;“嘛&#xff0c;写全称也太累了吧&#xff0c;写”。不如整个缩写 K8s 作为缩写的结果…...

编程日记 2025/7/5 12:14:43

鸿蒙ArkTS语言基础语法详解

文章目录 鸿蒙ArkTS语言基础语法详解一、引言二、ArkTS语言概述1. ArkTS语言特点2. TypeScript基础语法2.1 类型注解2.2 接口2.3 泛型2.4 类的继承2.5 类的访问修饰符 三、ArkTS的基本组成3.1 装饰器3.2 UI描述3.3 自定义组件3.4 系统组件3.5 属性方法和事件方法 四、自定义组件…...

编程日记 2025/7/2 22:11:10

两条链表相同位数相加

优质博文IT-BLOG-CN 一、题目 给你两个非空的链表&#xff0c;表示两个非负的整数。它们每位数字都是按照逆序的方式存储的&#xff0c;并且每个节点只能存储一位数字。请你将两个数相加&#xff0c;并以相同形式返回一个表示和的链表。你可以假设除了数字0之外&#xff0c;这…...

编程日记 2025/7/2 17:51:46

C语言单元总结

黑色加粗表示刷题刷到这样的题 红色加粗表示可能重要 单元一 程序设计宏观认识 C语言程序框架 C语言程序最基本的程序框架由两部分构成&#xff0c;分别是 1) 编译预处理 2) 函数组 C语言程序构成 C程序最大的特点就是所有的程序都是用函数来装配的&#xff0c;函数是构成…...

编程日记 2025/7/5 11:25:36

【Golang】Go语言编程思想（六）：Channel，第二节，使用Channel等待Goroutine结束

使用 Channel 等待任务结束 首先回顾上一节 channel 这一概念介绍时所写的代码&#xff1a; package mainimport ("fmt""time" )func worker(id int, c chan int) {for n : range c {fmt.Printf("Worker %d received %c\n",id, n)} }func crea…...

编程日记 2025/7/4 17:25:34

Oracle RAC开启和关闭日志归档Log Archive

一、开启日志归档模式 # srvctl stop database -d <DB_NAME> # srvctl start instance -d <DB_NAME> -i <INSTANCE_NAME> -o mount # 停止 RAC 数据库的所有实例&#xff1a; [oracleora19crac1:/home/oracle]$srvctl stop database -d orcl # 启动第一个实…...

编程日记 2025/7/4 16:39:36

今天调了个转速的小BUG

同事说转速表有个bug&#xff0c;转速停止后&#xff0c;继电器没有恢复到初始状态。若停止之前是报警&#xff0c;继电器吸合&#xff0c;则停止后继电器还是吸合。我心想不会啊&#xff0c;这软件都弄了好几年了&#xff0c;一直也没出现过状况。 经过与调试同事的沟通&#…...

编程日记 2025/7/4 16:59:16

RabbitMQ七种工作模式之 RPC通信模式, 发布确认模式

文章目录 六. RPC(RPC通信模式)客户端服务端 七. Publisher Confirms(发布确认模式)1. Publishing Messages Individually(单独确认)2. Publishing Messages in Batches(批量确认)3. Handling Publisher Confirms Asynchronously(异步确认) 六. RPC(RPC通信模式) 客⼾端发送消息…...

编程日记 2025/7/1 16:11:24

【Python教程】Python3基础篇之基础语法

博主介绍：✌全网粉丝21W+，CSDN博客专家、Java领域优质创作者，掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围：SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物联网、机器学习等设计与开发。 感兴趣的可…...

编程日记 2025/7/5 8:51:15