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

AtCoder Beginner Contest 401 E题题解

news 来源：原创 2025/9/7 19:18:59

E - Reachable Sethttp://E - Reachable Set

题意概述：

给定一个无向图，

对于每个 $k=1\sim n$ ，解决以下问题：

-选择最少的一些顶点，使得删除这些顶点及其关联的所有边后点1只能到达 $1 \sim k$ 以内的所有点

牵制芝士：头文件，建图，带权并查集

题解：

首先，我们可以将题目拆成两部分

1 ：判断一个点能不能实现目标

2 ：对于能实现的点，计算答案

第一部分：

可以用并查集来处理

只与比 $k$ 小的节点连边，并统计与 $1$ 所在集合的节点数

由于只与比 $k$ 小的节点连边，所以集合中只会有小于等于 $k$ 的节点

所以当且仅当点 $1$ 所在集合的节点数等于 $k$ 时，点 $1$ 才会与 $1\sim k$ 都联通

第二部分：

使用 $vis$ 数组标记目前是否能从 $1\sim k$ 直接扩展到点 $x$

$ans$ 表示 $vis$ 值为 $1$ 的节点的个数

所有大于 $k$ 能扩展点，都需要被删除

因为只处理能实现目标的节点，所以答案就是 $ans-k$

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,fa[210000],sum[210000];
vector<int>a[210000];
bool vis[210000];
int find(int x)
{if(x==fa[x]) return x;return fa[x]=find(fa[x]);
}
void add(int x,int y)
{int fax=find(x);int fay=find(y);if(fax>fay) swap(fax,fay);if(fax!=fay){sum[fax]+=sum[fay];fa[fay]=fax;}
}
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){fa[i]=i;sum[i]=1;}for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);a[x].push_back(y);a[y].push_back(x);}vis[1]=1;int ans=0;for(int i=1;i<=n;i++){for(int j=0;j<a[i].size();j++){if(a[i][j]<i) add(a[i][j],i);//第一部分if(!vis[a[i][j]]) ans++;//第二部分vis[a[i][j]]=1;}printf("%d\n",sum[1]!=i?-1:(ans-i));}return 0;
}

AtCoder Beginner Contest 401 E题题解

E - Reachable Sethttp://E - Reachable Set 题意概述 ： 给定一个无向图， 对于每个 ，解决以下问题： -选择最少的一些顶点，使得删除这些顶点及其关联的所有边后点1只能到达以内的所有点牵制芝士 ：头文…...

编程日记 2025/9/7 19:18:59

Kubernetes控制平面组件：API Server Webhook 授权机制详解

云原生学习路线导航页（持续更新中） kubernetes学习系列快捷链接 Kubernetes架构原则和对象设计（一）Kubernetes架构原则和对象设计（二）Kubernetes架构原则和对象设计（三）Kubernetes控…...

编程日记 2025/9/7 19:09:08

【CodeMirror】系列（二）官网示例（六）自动补全、边栏

一、自动补全 codemirror/autocomplete 包提供了在编辑器中显示输入建议的功能。这个示例展示了如何启用该功能以及如何编写自己的补全来源。自动补全是通过在编辑器的配置项中加入 autocompletion 扩展实现的。有些语言包支持内置的自动补全功能，比如HTML包。默…...

编程日记 2025/9/3 1:25:22

CSS 表格样式学习笔记

CSS 提供了强大的工具来美化和定制 HTML 表格的外观。通过合理使用 CSS 属性，可以使表格更加美观、易读且功能强大。以下是对 CSS 表格样式的详细学习笔记。一、表格边框 1. 单独边框默认情况下，表格的 <table>、<th> 和 <td> 元…...

编程日记 2025/8/29 12:51:51

简单记录一下Android四大组件

1、Android Layout 1.1、LinearLayout 线性布局，子控件按照水平或垂直的方向依次排列，排列方向通过属性android:orientation控制，horizontal为水平排列，vertical为垂直排列。对于同一水平线上的控件，可以调整它的lay…...

编程日记 2025/9/3 0:27:01

在线地图支持天地图和腾讯地图，仪表板和数据大屏支持发布功能，DataEase开源BI工具v2.10.7 LTS版本发布

2025年4月11日，人人可用的开源BI工具DataEase正式发布v2.10.7 LTS版本。这一版本的功能变动包括：数据源方面，Oracle数据源支持获取和查询物化视图；图表方面，在线地图支持天地图、腾讯地图；新增子弹图&…...

编程日记 2025/9/4 18:19:28

【图像处理基石】什么是通透感？

一、画面的通透感定义画面的通透感指图像在色彩鲜明度、空间层次感、物体轮廓清晰度三方面的综合表现，具体表现为： 色彩鲜明：颜色纯净且饱和度适中，无灰暗或浑浊感；层次分明：明暗过渡自然，光…...

编程日记 2025/9/4 16:55:53

猫咪如厕检测与分类识别系统系列【六】分类模型训练+混合检测分类+未知目标自动更新

前情提要家里养了三只猫咪，其中一只布偶猫经常出入厕所。但因为平时忙于学业，没法时刻关注牠的行为。我知道猫咪的如厕频率和时长与健康状况密切相关，频繁如厕可能是泌尿问题，停留过久也可能是便秘或不适。为了更科学地了解牠的如…...

编程日记 2025/9/3 16:23:24

NoSQL入门指南：Redis与MongoDB的Java实战

一、为什么需要NoSQL？ 在传统SQL数据库中，数据必须严格遵循预定义的表结构，就像把所有物品整齐摆放在固定尺寸的货架上。而NoSQL（Not Only SQL）数据库则像一个灵活的储物间，允许存储各种类型的数据&#x…...

编程日记 2025/9/2 17:31:42

游戏引擎学习第223天

回顾今天我们正在进行过场动画序列的制作，因此我想深入探讨这个部分。昨天，我们暂时停止了过场动画的制作，距离最终结局还有一些内容没有完成。今天的目标是继续完成这些内容。我们已经制作了一个过场动画的系列，并把它们集中…...

编程日记 2025/9/6 0:27:49

【redis进阶二】分布式系统之主从复制结构(1)

目录一为什么要有分布式系统？ 二分布式系统涉及到的非常关键的问题：单点问题三学习部署主从结构的redis (1)创建一个目录 (2)进入目录拷贝两份原有redis (3)使用vim修改几个选项 (4)启动两个从节点服务器 (5)建立复制，要想配…...

编程日记 2025/9/7 5:54:16

第一步： 在数据库创建树表和单表： SQL命令： 商品表 CREATE TABLE products (product_id INT AUTO_INCREMENT PRIMARY KEY,product_name VARCHAR(255) , price DECIMAL(10, 2) , stock INT NOT NULL, category_id INT NOT NULL); 商品分类…...

编程日记 2025/9/3 7:33:49

VectorBT量化入门系列：第六章 VectorBT实战案例：机器学习预测策略

VectorBT量化入门系列：第六章 VectorBT实战案例：机器学习预测策略本教程专为中高级开发者设计，系统讲解VectorBT技术在量化交易中的应用。通过结合Tushare数据源和TA-Lib技术指标，深度探索策略开发、回测优化与风险评估的核心方法…...

编程日记 2025/9/2 15:06:05

5G网络下客户端数据业务掉线频繁

MCPTT（Mission Critical Push-to-Talk）客户端的日志，和界面在待机状态下（即没有做通话等业务操作），会频繁提示“离线”。主要先看有没有丢网，UL BLER有没有问题。确认没有问题。看到业务信道释…...

编程日记 2025/9/5 4:23:09

CPU（中央处理器）

一、CPU的定义与核心作用 CPU 是计算机的核心部件，负责解释并执行指令、协调各硬件资源以及完成数据处理，其性能直接影响计算机的整体效率。核心功能： 从内存中读取指令并译码。执行算术逻辑运算。控制数据在寄存器、内存和I/O设备间的…...

编程日记 2025/9/4 17:16:25

Java从入门到“放弃”（精通）之旅——程序逻辑控制④

Java从入门到“放弃”（精通）之旅🚀：程序逻辑的完美理解一、开篇：程序员的"人生选择" 曾经的我，生活就像一段顺序执行的代码： System.out.println("早上8:00起床"); Syste…...

编程日记 2025/9/7 9:44:02

[Dify] 基于明道云实现金融业务中的Confirmation生成功能

在金融业务的日常流程中，交易记录的处理不仅涉及数据录入、流程审批，更重要的是其最终输出形式——交易确认函（Confirmation）。本文将介绍如何通过明道云的打印模板功能，快速、准确地生成符合业务需求的交易Confirmation，提升工作效率与合规性。为什么需要Confirmation？…...

编程日记 2025/9/4 7:19:10

Qt安卓设备上怎么安装两个不同的Qt应用？

在安卓设备上安装两个不同的Qt应用时，需要确保这两个应用在安卓系统中被视为独立的应用程序。以下是详细的步骤和注意事项，帮助你实现这一目标： 一、修改应用的包名安卓系统通过应用的包名（package属性）来区分不同的…...

编程日记 2025/9/5 10:45:35

Prompt工程提示词(1-6章)

White graces：个人主页 🐹今日诗词:怅望千秋一洒泪，萧条异代不同时🐹 ⛳️点赞 ☀️收藏⭐️关注💬卑微小博主🙏 ⛳️点赞 ☀️收藏⭐️关注💬卑微小博主🙏 目录 🚀 第…...

编程日记 2025/9/2 16:17:38

0基础 | 硬件滤波 C、RC、LC、π型

一、滤波概念 （一）滤波定义滤波是将信号中特定波段频率滤除的操作，是抑制和防止干扰的重要措施。通过滤波器实现对特定频率成分的筛选，确保目标信号的纯净度，提升系统稳定性。 （二）滤波器分…...

编程日记 2025/9/6 19:41:16

C++ 编程指南34 - C++ 中 ABI 不兼容的典型情形

一：概述 ABI（Application Binary Interface）是二进制层面的接口规范。如果一个库的 ABI 发生了变化，那么基于旧 ABI 编译的代码可能在运行时与新库不兼容（即使接口名字都一样也不行）。那么在C++中编程中，哪些情形会导致ABI不兼容呢？下面逐一列举一下。二：C++ 中 ABI…...

编程日记 2025/8/31 8:09:23

【动态规划】深入动态规划：背包问题

文章目录前言01背包例题一、01背包二、分割等和子集三、目标和四、最后一块石头的重量|| 完全背包例题一、完全背包二、零钱兑换三、零钱兑换||四、完全平方数前言什么是背包问题，怎么解决算法中的背包问题呢？ 背包问题 (Knapsack problem) 是⼀种组…...

编程日记 2025/9/6 4:41:29

NVIDIA AI Aerial

NVIDIA AI Aerial 适用于无线研发的 NVIDIA AI Aerial 基础模组Aerial CUDA 加速 RANAerial Omniverse 数字孪生Aerial AI 无线电框架用例构建商业 5G 网络加速 5G生成式 AI 和 5G 数据中心加速 6G 研究基于云的工具优势100% 软件定义通过部署在数字孪生中进行测试6G 标准化…...

编程日记 2025/9/5 21:14:53

计算机视觉6——相机基础

一、数字相机基本工作原理 （一）像素概念数字相机生成二维图像，图像最小单元是像素。每个像素对应三维世界中某个特定方向，像素值衡量某一时刻来自该方向的光照强度/颜色 ，即相机度量每个像素的光照情况并保存到对…...

编程日记 2025/9/2 18:55:48

入门到精通，C语言十大经典程序

以下是十个经典的C语言程序示例，这些程序涵盖了从基础到稍复杂的应用场景，适合初学者和有一定基础的开发者学习和参考。 1. Hello, World! 这是每个初学者学习编程时的第一个程序，用于验证开发环境是否正确配置。 #include <stdio.h>…...

编程日记 2025/9/6 1:22:43

【毕设】Python构建基于TMDB电影推荐系统

个性化电影推荐系统这是一个基于FastAPI开发的现代化电影推荐系统，结合了协同过滤和深度学习技术，为用户提供个性化的电影推荐服务。主要功能 🎯 个性化电影推荐🔍 电影搜索与浏览⭐ 电影评分系统💝 收藏夹功能&a…...

编程日记 2025/9/6 8:33:15

嵌入式常见概念的介绍

目录一、MCU、MPU、ARM （一）MCU（微控制器） （二）MPU（微处理器） （三）ARM（架构） 二、DSP （一）数字信号处理…...

编程日记 2025/9/6 11:27:53

富兴号：拨云见日，打造普洱品质典范

在高端普洱茶市场的混沌格局中，价格与品质的天平严重失衡，消费者往往深陷 “高价却难觅好茶” 的困境。而新兴品牌富兴号强势崛起，奋力冲破这一迷局，致力于重塑 “号级茶” 的卓越品质，为茶叶赋予珍贵的品鉴与收藏价值…...

编程日记 2025/8/29 18:41:52

【WORD】批量将doc转为docx

具体步骤进行： 打开Word文档，按下AltF11快捷键，打开VBA编辑器。在VBA编辑器中，左侧的“项目资源管理器”窗口会显示当前打开的Word文档相关项目。找到您要添加代码的文档项目（通常以文档名称命名）&#xf…...

编程日记 2025/9/7 17:32:13

Linux内存管理架构(1)

0.内存空间架构 1.用户空间在 Linux 系统中，应用程序通过 malloc() 申请内存，并通过 free() 释放内存时，底层的内存管理是由 glibc（GNU C Library）中的内存分配器实现的。glibc 的内存分配器负责与操作系统的内核交互…...

编程日记 2025/9/2 13:54:45

Ubuntu 各个常见长期支持历史版本与代号

文章目录 1. Ubuntu 历史版本与代号2. 查看当前系统版本在 Ubuntu 操作系统里，每个版本都有一个别具特色的名字。该名字由一个形容词与一个动物名称构成，且形容词和动物名称的首字母是一样的。例如 “Warty Warthog（长疣的疣猪）”…...

编程日记 2025/8/30 10:47:34

信息安全管理与评估2021年国赛正式卷答案截图以及十套国赛卷

2021年全国职业院校技能大赛高职组 “信息安全管理与评估”赛项任务书1 赛项时间共计X小时。赛项信息赛项内容竞赛阶段任务阶段竞赛任务竞赛时间分值第一阶段平台搭建与安全设备配置防护任务1 网络平台搭建任务2 网络安全设备配置与防护第二…...

编程日记 2025/9/6 9:40:44

在线上定位1G日志文件中的异常信息时，我这样做合适吗

1G级线上日志文件的异常定位系统性方案一、快速定位流程 import datetime import randomdef generate_springboot_log(file_name, file_size_gb):# 模拟Spring Boot日志内容log_levels ["INFO", "DEBUG", "WARNING", "ERROR"]cla…...

编程日记 2025/9/2 15:53:40

Transformer模型中的两种掩码

模型训练通常使用批处理batch来提升训练效率。而实际中Transformer的输入序列（如句子、文本片段）长度往往不一致。为了让这些样本可以组成一个统一的形状 [B, T] 的张量给GPU进行并行计算提高效率，需要将较短的序列填充（pad&…...

编程日记 2025/9/7 0:26:48

FastAPI-MPC正式发布，新的AI敏捷开发利器

FastAPI-MCP发布：零配置构建微服务控制平台的革命性实践引言在微服务架构日益复杂的今天，如何快速实现API接口的标准化管理与可视化控制成为开发者面临的核心挑战。近日，FastAPI-MCP工具的发布引发了技术社区广泛关注，其宣称能…...

编程日记 2025/9/2 17:26:06

Spring Boot 项目基于责任链模式实现复杂接口的解耦和动态编排！

全文目录： 开篇语前言一、责任链模式概述责任链模式的组成部分： 二、责任链模式的核心优势三、使用责任链模式解耦复杂接口1. 定义 Handler 接口2. 实现具体的 Handler3. 创建订单对象4. 在 Spring Boot 中使用责任链模式5. 配置责任链6. 客户端调用四、…...

编程日记 2025/8/30 14:15:12

学习笔记八——内存管理相关

📘 目录内存结构基础：栈、堆、数据段Rust 的内存管理机制（对比 C/C、Java）Drop：Rust 的自动清理机制Deref：为什么 *x 能访问结构体内部值Rc：多个变量“共享一个资源”怎么办？Weak&…...

编程日记 2025/9/7 15:20:32

Deepseek Bart模型相比Bert的优势

BART（Bidirectional and Auto-Regressive Transformers）与BERT（Bidirectional Encoder Representations from Transformers）虽然均基于Transformer架构，但在模型设计、任务适配性和应用场景上存在显著差异。以下是BART…...

编程日记 2025/9/6 9:49:30

Python在糖尿病分类问题上寻找具有最佳 ROC AUC 分数和 PR AUC 分数（决策树、逻辑回归、KNN、SVM）

Python在糖尿病分类问题上寻找具有最佳 ROC AUC 分数和 PR AUC 分数（决策树、逻辑回归、KNN、SVM） 问题模板解题思路1. 导入必要的库2. 加载数据3. 划分训练集和测试集4. 数据预处理5. 定义算法及其参数6. 存储算法和对应指标7. 训练模型并计算指标8. 找…...

编程日记 2025/8/31 13:27:17

达梦数据库-学习-20-慢SQL优化之CTE等价改写

目录一、环境信息二、介绍三、优化过程 1、原始SQL 2、源SQL执行时间 3、原始SQL执行计划 4、拆分问题 5、过滤性 6、统计信息收集 7、改写思路一 8、改写SQL一 9、改写SQL一的执行计划 10、改写思路二 11、改写SQL二 12、改写SQL二的执行计划一、环境信息…...

编程日记 2025/9/3 15:30:00

软件生命周期模型：瀑布模型、螺旋模型、迭代模型、敏捷开发、增量模型、快速原型模型

目录 1.软件生命周期 2.软件生命周期模型 2.1瀑布模型缺点【存在的问题】： 优点： 2.2 螺旋模型特点： 2.3 迭代模型优点： 2.4 敏捷开发 2.5 增量模型增量模型一般和迭代模型一起使用： 2.6 快速原型模型…...

编程日记 2025/9/3 8:27:19

AI agents系列之全面介绍

随着大型语言模型（LLMs）的出现，人工智能（AI）取得了巨大的飞跃。这些强大的系统彻底改变了自然语言处理，但当它们与代理能力结合时，才真正释放出潜力——能够自主地推理、规划和行动。这就是LLM代理大显身手的地方，它们代表了我们与AI交互以及利用AI的方式的范式转变。 …...

编程日记 2025/9/5 12:46:31

Ubuntu 下通过 Docker 部署 WordPress 服务器

最近想恢复写私人博客的习惯，准备搭建一个wordpress。在这篇博客中，我将记录如何在 Ubuntu 环境下通过 Docker 部署一个 WordPress 服务器。WordPress 是一个流行的内容管理系统（CMS），它让用户能够轻松地创建和管理网…...

编程日记 2025/9/3 15:22:47

Elasticsearch生态

目录 Elasticsearch核心概念 Elasticsearch实现全文检索的原理 Elasticsearch打分规则常用的查询语法 ES数据同步方案 Elasticsearch生态非常丰富，包含了一系列工具和功能，帮助用户处理、分析和可视化数据，Elastic Stack是其核心部分&a…...

编程日记 2025/9/6 18:06:38

idea配置spring MVC项目启动（maven配置完后）

springmvc项目在idea中配置启动总结，下面的内容是在maven配置好后进行的。配置 Tomcat 服务器添加 Tomcat 到 IDEA： File → Settings → Build, Execution, Deployment → Application Servers → 点击 → 选择 Tomcat Server。指定 Tomcat 安装目…...

编程日记 2025/8/23 10:19:42

大模型微调数据集怎么搞？基于easydataset实现文档转换问答对json数据集！

微调的难点之一在与数据集。本文介绍一种将文档转换为问答数据集的方法，超级快！ 上图左侧是我的原文档，右侧是我基于文档生成的数据集。原理是通过将文档片段发送给ollama本地模型，然后本地模型生成有关问题，并基于文…...

编程日记 2025/8/29 2:56:06

【排序算法】快速排序

目录一、递归版本 1.1 hoare版本问题1：为什么left 和 right指定的数据和key值相等时不能交换？ 问题2：为什么跳出循环后right位置的值⼀定不⼤于key？ 1.2 挖坑法 1.3 lomuto前后指针版本二、快排优化 2.1 时间复杂度的计算 2.1.…...

编程日记 2025/9/3 11:39:40

爬虫：IP代理

什么是代理代理服务器代理服务器的作用就是用来转发请求和响应在爬虫中为何需要使用代理？ 有些时候，需要对网站服务器发起高频的请求，网站的服务器会检测到这样的异常现象，则会讲请求对应机器的ip地址加入黑名单&#xff…...

编程日记 2025/9/1 16:43:14

JUC.atomic原子操作类原理分析

摘要多线程场景下共享变量原子性操作除了可以使用Java自带的synchronized关键字以及AQS锁实现线程同步外，java.util.concurrent.atomic 包下提供了对基本类型封装类(AtomicBoolean|AtomicLong|AtomicReference|AtomicBoolean) 以及对应的数组封装。对于已有的包含…...

编程日记 2025/9/2 7:47:30

【XCP实战】AUTOSAR架构下XCP从0到1开发配置实践

目录前言正文 1.CAN功能开发 1.1 DBC的制作及导入 1.2 CanTrcv模块配置 1.3 Can Controller模块配置 1.4 CanIf模块配置 2.XCP模块集成配置配置 2.1.XCP模块配置 2.2.XCP模块的Task Mapping 2.3.XCP模块的初始化 3.在链接文件中定义标定段 4.编写标定相关的测试…...

编程日记 2025/9/4 3:26:05

题意概述 ：

牵制芝士 ：头文件，建图，带权并查集

题解 ：

第一部分 ：

第二部分 ：

代码 ：

相关文章：

题意概述：

牵制芝士：头文件，建图，带权并查集

题解：

第一部分：

第二部分：

代码：