安阳做网站多少钱/今天《新闻联播》回放
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:https://atcoder.jp/contests/abc309 目录 E Problem/题意 Thought/思路 解法一: 解法二: Code/代码 E Problem/题意 一个家庭有 N 个人,根节点为 1,给出 2 ~ N 的父节点。一共购买 M 次保险,每…...

【HarmonyOS】解决API6 WebView跳转外部浏览器问题、本地模拟器启动黑屏
【问题描述1】 HarmonyOS API6 Java开发中使用WebView组件,如果网页中有跳转链接,点击会跳转到手机系统浏览器。 【解决方案】 解决这个问题的方法就是给WebView这种自定义的WebAgent对象。具体代码如下: WebConfig webConfigthis.webView…...

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

优化软件系统,解决死锁问题,提升稳定性与性能 redis排队下单
项目背景: 随着用户数量的不断增加,我们的速卖通小管家软件系统面临了一个日益严重的问题:在从存储区提供程序的数据读取器中进行读取时,频繁出现错误。系统报告了一个内部异常: 异常信息如下: 从存储区提供程序的数…...

MyBatisPlus 底层用 json 存储,Java 仍然使用 对象操作
PO 类的字段定义为一个对象,然后使用以下注解修饰 TableField(typeHandler JacksonTypeHandler.class) 当然 jsonTypeHandler 有多种可以选择...

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

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

cv::Mat 的常见操作方法
cv::Mat是OpenCV库中用于处理图像和矩阵的主要数据结构。以下是一些常见的cv::Mat操作方法: 创建和初始化 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,即java虚拟机,是java代码运行时的环境。我们从底层往上层来说,分别是硬件部分,操作系统,JVM,jre,JDK,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(作者)-BUUCTF-ciscn_2019_s_3 参考文章-博客园-z2yh(作者)-Srop 原理与利用方法 vlun函数中没有分配栈帧(指rsp没有增长,也没有压入父函数的rbp,这也导致…...

3D模型格式转换工具HOOPS Exchange协助Epic Games实现CAD数据轻松导入虚幻引擎
一、面临的挑战 Epic Games最为人所知的身份可能是广受欢迎的在线视频游戏Fortnite的开发商,但它也是虚幻引擎背后的团队,虚幻引擎是一种实时3D创作工具,为世界领先的游戏提供动力,并且也被电影电视、建筑、汽车、制造、模拟等领…...

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

不来看看?通过Python实现贪吃蛇小游戏
🏅我是默,一个在CSDN分享笔记的博主。📚📚 🌟在这里,我要推荐给大家我的专栏《Python》。🎯🎯 🚀无论你是编程小白,还是有一定基础的程序员,这个专…...

C# linq初探 使用linq查询数组中元素
使用linq进行数组查询 输出数组中全部的偶数并升序输出结果 写法1: 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…...

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

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

Java中的集合
Java中的集合分为单列集合和双列集合,单列集合顶级接口为Collection,双列集合顶级接口为Map。 Collection 的子接口有两个:List和Set。 List 接口的特点:元素可重复,有序(存取顺序)。 List 接…...

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

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

QCA组态如何科学命名?
前言 (一)文献来源 文献来源:[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. (二ÿ…...

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

高性能实践
1、认识性能 从用户体验来看,性能就是响应时间短; 从开发角度来看,性能主要是执行效率高。 性能主要表现形式如下: (1)响应时间,AVG、MAX、MIN、TP95、TP99 (2)吞吐…...

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

算法通关村-----图的基本算法
图的实现方式 邻接矩阵 定义 邻接矩阵是一个二维数组,其中的元素表示图中节点之间的关系。通常,如果节点 i 与节点 j 之间有边(无向图)或者从节点 i 到节点 j 有边(有向图),则矩阵中的元素值…...

基于随机森林+小型智能健康推荐助手(心脏病+慢性肾病健康预测+药物推荐)——机器学习算法应用(含Python工程源码)+数据集(二)
目录 前言总体设计运行环境Python环境依赖库 模块实现1. 疾病预测2. 药物推荐1)数据预处理2)模型训练及应用3)模型应用 其它相关博客工程源代码下载其它资料下载 前言 本项目基于Kaggle上公开的数据集,旨在对心脏病和慢性肾病进行…...
stm32学习-芯片系列/选型
【03】STM32HAL库开发-初识STM32 | STM概念、芯片分类、命名规则、选型 | STM32原理图设计、看数据手册、最小系统的组成 、STM32IO分配_小浪宝宝的博客-CSDN博客 STM32:ST是意法半导体,M是MCU/MPU,32是32位。 ST累计推出了:…...

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

图像处理之《基于语义对象轮廓自动生成的生成隐写术》论文精读
一、相关知识 首先我们需要了解传统隐写和生成式隐写的基本过程和区别。传统隐写需要选定一幅封面图像,然后使用某种隐写算法比如LSB、PVD、DCT等对像素进行修改将秘密嵌入到封面图像中得到含密图像,通过信道传输后再利用算法的逆过程提出秘密信息。而生…...