当前位置: 首页 > 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;
}

http://www.lryc.cn/news/171659.html

相关文章:

  • 【HarmonyOS】解决API6 WebView跳转外部浏览器问题、本地模拟器启动黑屏
  • 给出三个整数,判断大小
  • 优化软件系统,解决死锁问题,提升稳定性与性能 redis排队下单
  • MyBatisPlus 底层用 json 存储,Java 仍然使用 对象操作
  • 发送验证码倒计时 防刷新重置!!!
  • OpenCV项目开发实战--forEach的并行像素访问与其它方法的性能比较
  • cv::Mat 的常见操作方法
  • JVM——11.JVM小结
  • 月木学途开发 2.前台用户模块
  • buuctf-ciscn_s_3
  • 3D模型格式转换工具HOOPS Exchange协助Epic Games实现CAD数据轻松导入虚幻引擎
  • Linux- inode vnode
  • 不来看看?通过Python实现贪吃蛇小游戏
  • C# linq初探 使用linq查询数组中元素
  • 使用线程池进行任务处理
  • ES6之Map和Set有什么不同?
  • Java中的集合
  • 9.4.2servlet基础2
  • 嵌入式学习 - 用电控制电
  • QCA组态如何科学命名?
  • 外贸行业中常用的邮箱推荐
  • 高性能实践
  • 说说hashCode() 和 equals() 之间的关系?
  • 算法通关村-----图的基本算法
  • 基于随机森林+小型智能健康推荐助手(心脏病+慢性肾病健康预测+药物推荐)——机器学习算法应用(含Python工程源码)+数据集(二)
  • stm32学习-芯片系列/选型
  • LeetCode //C - 200. Number of Islands
  • 使用Python构建强大的网络爬虫
  • 图像处理之《基于语义对象轮廓自动生成的生成隐写术》论文精读
  • Java 字节流