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

[补题记录] Atcoder Beginner Contest 309(E)

URL:https://atcoder.jp/contests/abc309

目录

E

Problem/题意

Thought/思路

解法一:

解法二:

 Code/代码


E

Problem/题意

一个家庭有 N 个人,根节点为 1,给出 2 ~ N 的父节点。一共购买 M 次保险,每次给出 Xi Yi,使得 Xi 和它之后的 Yi 代人都有保险。问一共有多少人获得保险?

Thought/思路

解法一:

用 next[i] 表示从 i 出发,还能覆盖多少代保险。假设 x 是 i 的下一个节点,那么 next[x] = Max(next[x], next[i] - 1)。通解只需要将 i 改为 fa[x] 即可。

只要当前节点的 next >= 0,就能让 ans ++。

解法二:

来自:~Lanly~

该解法的核心思想就是,当前处理的点,有且仅有一条回到根节点的路线,也因此可以将其当作一维前缀和来处理。

Code/代码

解法一:

#include "bits/stdc++.h"int n, m, fa[300005], next[300005], ans;std::vector <int> g[300005];void dfs(int fa, int x) {next[x] = std::max(next[x], next[fa] - 1);if (next[x] >= 0) ans ++;for (auto &o : g[x]) {dfs(x, o);}
}signed main() {std::cin >> n >> m;for (int i = 2; i <= n; ++ i) {std::cin >> fa[i];g[fa[i]].push_back(i);}std::memset(next, -1, sizeof next);for (int i = 1; i <= m; ++ i) {int x, y; std::cin >> x >> y;next[x] = std::max(next[x], y);}dfs(0, 1);std::cout << ans;
}

解法二:

#include "bits/stdc++.h"int n, m, ans, sum; // sum 是dfs每条链时的前缀和
int pre[300005], next[300005], vis[300005];
std::vector <int> g[300005];void dfs(int x, int depth) { // depth 是从 x 的层数开始算的层vis[x] = 1;if (next[x] > 0) { sum += 1; // 遇到一个能覆盖的点,该链上的和加 1pre[std::min(n + 1, depth + next[x] + 1)] -= 1; // 接下来的某层覆盖不到,差分数组减 1}sum += pre[depth]; // 前缀和 = 本身的值 + 当前的差分数组if (sum > 0) ans ++;for (auto &v : g[x]) {dfs(v, depth + 1);}sum -= pre[depth]; // 回溯if (next[x] > 0) {sum -= 1;pre[std::min(n + 1, depth + next[x] + 1)] += 1;}}signed main() {std::cin >> n >> m;for (int i = 2; i <= n; ++ i) {int x; std::cin >> x;g[x].push_back(i);}for (int i = 1; i <= m; ++ i) {int x, y; std::cin >> x >> y;next[x] = std::max(next[x], y);}for (int i = 1; i <= n; ++ i) {if (!vis[i]) dfs(i, 0);}std::cout << ans;
}

相关文章:

[补题记录] Atcoder Beginner Contest 309(E)

URL&#xff1a;https://atcoder.jp/contests/abc309 目录 E Problem/题意 Thought/思路 解法一&#xff1a; 解法二&#xff1a; Code/代码 E Problem/题意 一个家庭有 N 个人&#xff0c;根节点为 1&#xff0c;给出 2 ~ N 的父节点。一共购买 M 次保险&#xff0c;每…...

【HarmonyOS】解决API6 WebView跳转外部浏览器问题、本地模拟器启动黑屏

【问题描述1】 HarmonyOS API6 Java开发中使用WebView组件&#xff0c;如果网页中有跳转链接&#xff0c;点击会跳转到手机系统浏览器。 【解决方案】 解决这个问题的方法就是给WebView这种自定义的WebAgent对象。具体代码如下&#xff1a; WebConfig webConfigthis.webView…...

给出三个整数,判断大小

7-2 比较大小 给出三个整数&#xff0c;判断大小。 输入格式: 给出三个整数a,b,c 输出格式: 在一行中依次从小到大的顺序输出&#xff0c;两数之间有一个空格&#xff0c;无多余空格。 输入样例: 在这里给出一组输入。例如&#xff1a; 2 1 5 输出样例: 在这里给出相应的输…...

优化软件系统,解决死锁问题,提升稳定性与性能 redis排队下单

项目背景&#xff1a; 随着用户数量的不断增加&#xff0c;我们的速卖通小管家软件系统面临了一个日益严重的问题&#xff1a;在从存储区提供程序的数据读取器中进行读取时&#xff0c;频繁出现错误。系统报告了一个内部异常: 异常信息如下&#xff1a; 从存储区提供程序的数…...

MyBatisPlus 底层用 json 存储,Java 仍然使用 对象操作

PO 类的字段定义为一个对象&#xff0c;然后使用以下注解修饰 TableField(typeHandler JacksonTypeHandler.class) 当然 jsonTypeHandler 有多种可以选择...

发送验证码倒计时 防刷新重置!!!

需求&#xff1a;发送验证码&#xff0c;每60s可点击发送一次&#xff0c;倒计时中按钮不可点击&#xff0c;且刷新页面倒计时不会重置 可用以下方式避免刷新页面时&#xff0c;倒计时重置 localStorage本地缓存方式 思路&#xff1a; 1.记录倒计时的时间 2.页面加载时&…...

OpenCV项目开发实战--forEach的并行像素访问与其它方法的性能比较

在本教程中,我们将比较Mat 类的forEach方法与 OpenCV 中访问和转换像素值的其他方法的性能。我们将展示forEach如何比简单地使用at方法甚至有效地使用指针算术快得多。 OpenCV 内部有一些隐藏的宝石,有时并不为人所知。这些隐藏的宝石之一是Mat 类的forEach方法,它利用计算…...

cv::Mat 的常见操作方法

cv::Mat是OpenCV库中用于处理图像和矩阵的主要数据结构。以下是一些常见的cv::Mat操作方法&#xff1a; 创建和初始化 cv::Mat::Mat(): 创建一个空的cv::Mat对象。cv::Mat::Mat(int rows, int cols, int type): 创建一个指定行数、列数和数据类型的cv::Mat对象。cv::Mat::Mat(i…...

JVM——11.JVM小结

这篇文章我们来小结一下JVM JVM&#xff0c;即java虚拟机&#xff0c;是java代码运行时的环境。我们从底层往上层来说&#xff0c;分别是硬件部分&#xff0c;操作系统&#xff0c;JVM&#xff0c;jre&#xff0c;JDK&#xff0c;java代码。JVM是直接与操作系统打交道的。JVM也…...

月木学途开发 2.前台用户模块

概述 效果展 数据库设计 会员表 DROP TABLE IF EXISTS user_type; CREATE TABLE user_type (userTypeId int(11) NOT NULL AUTO_INCREMENT,userTypeName varchar(255) DEFAULT NULL,userTypeDesc varchar(255) DEFAULT NULL,PRIMARY KEY (userTypeId) ) ENGINEInnoDB AUTO_I…...

buuctf-ciscn_s_3

一、srop 参考文章-博客园-wudiiv11&#xff08;作者&#xff09;-BUUCTF-ciscn_2019_s_3 参考文章-博客园-z2yh&#xff08;作者&#xff09;-Srop 原理与利用方法 vlun函数中没有分配栈帧&#xff08;指rsp没有增长&#xff0c;也没有压入父函数的rbp&#xff0c;这也导致…...

3D模型格式转换工具HOOPS Exchange协助Epic Games实现CAD数据轻松导入虚幻引擎

一、面临的挑战 Epic Games最为人所知的身份可能是广受欢迎的在线视频游戏Fortnite的开发商&#xff0c;但它也是虚幻引擎背后的团队&#xff0c;虚幻引擎是一种实时3D创作工具&#xff0c;为世界领先的游戏提供动力&#xff0c;并且也被电影电视、建筑、汽车、制造、模拟等领…...

Linux- inode vnode

什么是inode inode 是 UNIX 和 UNIX-like 操作系统中的一个关键概念。它代表了文件系统中文件或目录的元数据。每个文件和目录在文件系统中都有一个与之关联的 inode。这个数据结构存储了关于文件的所有信息&#xff0c;除了其名称和实际数据之外。 以下是 inode 中通常包含的…...

不来看看?通过Python实现贪吃蛇小游戏

&#x1f3c5;我是默&#xff0c;一个在CSDN分享笔记的博主。&#x1f4da;&#x1f4da; &#x1f31f;在这里&#xff0c;我要推荐给大家我的专栏《Python》。&#x1f3af;&#x1f3af; &#x1f680;无论你是编程小白&#xff0c;还是有一定基础的程序员&#xff0c;这个专…...

C# linq初探 使用linq查询数组中元素

使用linq进行数组查询 输出数组中全部的偶数并升序输出结果 写法1&#xff1a; int[] numbers { 5, 10, 8, 3, 6, 12 }; //查询的数组var numqurey from num in numberswhere num % 2 0 //按照条件过滤orderby numselect num;foreach (var num in numqurey){Console.Writ…...

使用线程池进行任务处理

线程池 线程池&#xff1a;一种线程使用模式。线程过多会带来调度开销&#xff0c;进而影响缓存局部性和整体性能。而线程池维护着多个线程&#xff0c;等待着监督管理者分配可并发执行的任务。这避免了在处理短时间任务时创建与销毁线程的代价。线程池不仅能够保证内核的充分…...

ES6之Map和Set有什么不同?

一、Map 1.定义 Map是ES6提供的一种新的数据结构&#xff0c;它是键值对的集合&#xff0c;类似于对象&#xff0c;但是键的范围不限于字符串&#xff0c;各种类型的值都可以当做键。 Object结构是“字符串-值”的对应&#xff0c;Map结构则是“值-值”的对应 2.代码示例 M…...

Java中的集合

Java中的集合分为单列集合和双列集合&#xff0c;单列集合顶级接口为Collection&#xff0c;双列集合顶级接口为Map。 Collection 的子接口有两个&#xff1a;List和Set。 List 接口的特点&#xff1a;元素可重复&#xff0c;有序&#xff08;存取顺序&#xff09;。 List 接…...

9.4.2servlet基础2

一.SmartTomcat 1.第一次使用需要进行配置. 二.异常处理 1.404:浏览器访问的资源,在服务器上不存在. a.检查请求的路径和服务器配置的是否一致(大小写,空格,标点符号). b. 确认webapp是否被正确加载(检查web.xml没有/目录错误/内容错误/名字拼写错误)(多多关注日志信息). 2…...

嵌入式学习 - 用电控制电

目录 前言&#xff1a; 1、继电器 2、二极管 3、三极管 3.1 特殊的三极管-mos管 3.2 npn类型三极管 3.3 pnp类型三极管 3.4 三极管的放大特性 3.5 mos管和三极管的区别 前言&#xff1a; 计算机的工作的核心原理&#xff1a;用电去控制电。 所有的电子元件都有数据手册…...

QCA组态如何科学命名?

前言 &#xff08;一&#xff09;文献来源 文献来源&#xff1a;[1]Furnari S, Crilly D, Misangyi V F, et al. Capturing causal complexity: Heuristics for configurational theorizing[J]. Academy of Management Review, 2021, 46(4): 778-799. &#xff08;二&#xff…...

外贸行业中常用的邮箱推荐

随着全球贸易的不断发展&#xff0c;外贸行业越来越重要。在这个过程中&#xff0c;电子邮件作为一种重要的沟通工具&#xff0c;扮演着关键的角色。然而&#xff0c;对于许多外贸从业者来说&#xff0c;选择合适的邮箱服务并不容易。本文将探讨外贸邮箱和普通邮箱的区别&#…...

高性能实践

1、认识性能 从用户体验来看&#xff0c;性能就是响应时间短&#xff1b; 从开发角度来看&#xff0c;性能主要是执行效率高。 性能主要表现形式如下&#xff1a; &#xff08;1&#xff09;响应时间&#xff0c;AVG、MAX、MIN、TP95、TP99 &#xff08;2&#xff09;吞吐…...

说说hashCode() 和 equals() 之间的关系?

每天一道面试题&#xff0c;陪你突击金九银十&#xff01; 上一篇关于介绍Object类下的几种方法时面试题时&#xff0c;提到equals()和hashCode()方法可能引出关于“hashCode() 和 equals() 之间的关系&#xff1f;”的面试题&#xff0c;本篇来解析一下这道基础面试题。 先祭一…...

算法通关村-----图的基本算法

图的实现方式 邻接矩阵 定义 邻接矩阵是一个二维数组&#xff0c;其中的元素表示图中节点之间的关系。通常&#xff0c;如果节点 i 与节点 j 之间有边&#xff08;无向图&#xff09;或者从节点 i 到节点 j 有边&#xff08;有向图&#xff09;&#xff0c;则矩阵中的元素值…...

基于随机森林+小型智能健康推荐助手(心脏病+慢性肾病健康预测+药物推荐)——机器学习算法应用(含Python工程源码)+数据集(二)

目录 前言总体设计运行环境Python环境依赖库 模块实现1. 疾病预测2. 药物推荐1&#xff09;数据预处理2&#xff09;模型训练及应用3&#xff09;模型应用 其它相关博客工程源代码下载其它资料下载 前言 本项目基于Kaggle上公开的数据集&#xff0c;旨在对心脏病和慢性肾病进行…...

stm32学习-芯片系列/选型

【03】STM32HAL库开发-初识STM32 | STM概念、芯片分类、命名规则、选型 | STM32原理图设计、看数据手册、最小系统的组成 、STM32IO分配_小浪宝宝的博客-CSDN博客  STM32&#xff1a;ST是意法半导体&#xff0c;M是MCU/MPU&#xff0c;32是32位。  ST累计推出了&#xff1a…...

LeetCode //C - 200. Number of Islands

200. Number of Islands Given an m x n 2D binary grid grid which represents a map of *‘1’*s (land) and *‘0’*s (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically…...

使用Python构建强大的网络爬虫

介绍 网络爬虫是从网站收集数据的强大技术&#xff0c;而Python是这项任务中最流行的语言之一。然而&#xff0c;构建一个强大的网络爬虫不仅仅涉及到获取网页并解析其HTML。在本文中&#xff0c;我们将为您介绍创建一个网络爬虫的过程&#xff0c;这个爬虫不仅可以获取和保存网…...

图像处理之《基于语义对象轮廓自动生成的生成隐写术》论文精读

一、相关知识 首先我们需要了解传统隐写和生成式隐写的基本过程和区别。传统隐写需要选定一幅封面图像&#xff0c;然后使用某种隐写算法比如LSB、PVD、DCT等对像素进行修改将秘密嵌入到封面图像中得到含密图像&#xff0c;通过信道传输后再利用算法的逆过程提出秘密信息。而生…...

哪些网页游戏好玩/网址seo优化排名

Java I/O 扩展 标签&#xff1a; Java基础 NIO Java 的NIO(新IO)和传统的IO有着相同的目的: 输入 输出 .但是NIO使用了不同的方式来处理IO,NIO利用内存映射文件(此处文件的含义可以参考Unix的名言一切皆文件)来处理IO, NIO将文件或文件的一段区域映射到内存中(类似于操作系统的…...

wordpress 外部调用插件/个人接外包的网站

在生产环境下进行故障诊断时&#xff0c;为了不终止正在运行的服务或应用程序&#xff0c;有两种方式可以对正在运行的服务或应用程序的进程进行分析和调试。 首先一种比较直观简洁的方式就是用WinDbg等调试器直接attach到需要调试的进程&#xff0c;调试完毕之后再detach即可。…...

域名网站都有怎么进去建设/建站工具有哪些

2019独角兽企业重金招聘Python工程师标准>>> 花了一下午的时间&#xff0c;整理测试了一下Bean的生命周期行为. 首先排一个序。完整的测试代码后面贴出来。 加载当前Bean的构造器 加载Autowired注入的依赖关系的构造器。&#xff08;也就是加载依赖的Bean&#x…...

网站开发的职责/百度seo点击器

使用ip a命令查看虚拟机的网卡信息 发现有一个虚拟网卡virbr0 [rootlocalhost ~]# ip a 1: lo: <LOOPBACK,UP,LOWER_UP> mtu 65536 qdisc noqueue state UNKNOWN group default qlen 1000link/loopback 00:00:00:00:00:00 brd 00:00:00:00:00:00inet 127.0.0.1/8 scope…...

网络推广培训课程4万/专业放心关键词优化参考价格

状态 element和pad都可以处于不同的状态。pad的状态与element的状态相关联&#xff0c;因此状态的设计主要围绕element的状态进行。 一个element可以有 4 种状态。NULL、READY、PAUSED和PLAYING。当一个element最初被实例化时&#xff0c;它处于 NULL 状态。 状态定义 NULL&…...

王野摩托车质量可靠吗/短视频搜索seo

写了一个小爬虫跑在ubuntu的服务器上发现ssh断开后程序就会被终止。 这和linux的子进程与父进程的关系有关。感兴趣的可以看这里为什么ssh一关闭&#xff0c;程序就不再运行了&#xff1f; 解决办法&#xff1a; nohup ‘你的命令’ & 要如何查看后台运行的进程呢&#xff…...