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

【前后缀技巧】2022牛客多校3 A

登录—专业IT笔试面试备考平台_牛客网

题意:

思路:

这种是典中典中典,对于gcd,背包问题都是一样的处理方式

预处理出前缀lca和后缀lca,枚举哪个消失即可,可以统计方案数

Code:

#include <bits/stdc++.h>constexpr int N = 2e5 + 10;
constexpr int mod = 1e9 + 7;
constexpr int Inf = 0x3f3f3f3f;
constexpr double eps = 1e-10;std::vector<int> adja[N], adjb[N];int n, k;
int x[N];
int a[N], b[N];
int pa[N], pb[N];
int depa[N], depb[N];
int Fa[N][33], Fb[N][33];
int prea[N], sufa[N], preb[N], sufb[N];void dfs1(int u, int fa) {depa[u] = depa[fa] + 1;Fa[u][0] = fa;for (int j = 1; j <= 30; j ++) Fa[u][j] = Fa[Fa[u][j - 1]][j - 1];for (auto v : adja[u]) {if (v == fa) continue;dfs1(v, u);}
}
void dfs2(int u, int fa) {depb[u] = depb[fa] + 1;Fb[u][0] = fa;for (int j = 1; j <= 30; j ++) Fb[u][j] = Fb[Fb[u][j - 1]][j - 1];for (auto v : adjb[u]) {if (v == fa) continue;dfs2(v, u);}
}
int lca_a(int u, int v) {if (depa[u] < depa[v]) std::swap(u, v);for (int j = 30; j >= 0; j --) {if (depa[Fa[u][j]] >= depa[v]) {u = Fa[u][j];}}if (u == v) return u;for (int j = 30; j >= 0; j --) {if (Fa[u][j] != Fa[v][j]) {u = Fa[u][j];v = Fa[v][j];}}return Fa[u][0];
}
int lca_b(int u, int v) {if (depb[u] < depb[v]) std::swap(u, v);for (int j = 30; j >= 0; j --) {if (depb[Fb[u][j]] >= depb[v]) {u = Fb[u][j];}}if (u == v) return u;for (int j = 30; j >= 0; j --) {if (Fb[u][j] != Fb[v][j]) {u = Fb[u][j];v = Fb[v][j];}}return Fb[u][0];
}
void solve() {std::cin >> n >> k;for (int i = 1; i <= k; i ++) std::cin >> x[i];for (int i = 1; i <= n; i ++) {std::cin >> a[i];}for (int i = 2; i <= n; i ++) {std::cin >> pa[i];adja[pa[i]].push_back(i);adja[i].push_back(pa[i]);}for (int i = 1; i <= n; i ++) {std::cin >> b[i];}for (int i = 2; i <= n; i ++) {std::cin >> pb[i];adjb[pb[i]].push_back(i);adjb[i].push_back(pb[i]);}dfs1(1, 0);dfs2(1, 0);prea[1] = x[1];for (int i = 2; i <= k; i ++) {prea[i] = lca_a(prea[i - 1], x[i]);}preb[1] = x[1];for (int i = 2; i <= k; i ++) {preb[i] = lca_b(preb[i - 1], x[i]);}sufa[k] = x[k];for (int i = k - 1; i >= 1; i --) {sufa[i] = lca_a(sufa[i + 1], x[i]);}sufb[k] = x[k];for (int i = k - 1; i >= 1; i --) {sufb[i] = lca_b(sufb[i + 1], x[i]);}int ans = 0;int cur1 = sufa[2];int cur2 = sufb[2];if (a[cur1] > b[cur2]) ans ++;for (int i = 2; i <= k - 1; i ++) {int cur1 = lca_a(prea[i - 1], sufa[i + 1]);int cur2 = lca_b(preb[i - 1], sufb[i + 1]);if (a[cur1] > b[cur2]) ans ++;};cur1 = prea[k - 1];cur2 = preb[k - 1];if (a[cur1] > b[cur2]) ans ++;std::cout << ans << "\n";
}
signed main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t = 1;while(t --) {solve();}return 0;
}

 

相关文章:

【前后缀技巧】2022牛客多校3 A

登录—专业IT笔试面试备考平台_牛客网 题意&#xff1a; 思路&#xff1a; 这种是典中典中典&#xff0c;对于gcd&#xff0c;背包问题都是一样的处理方式 预处理出前缀lca和后缀lca&#xff0c;枚举哪个消失即可&#xff0c;可以统计方案数 Code&#xff1a; #include &l…...

Ae 效果:CC Page Turn

扭曲/CC Page Turn Distort/CC Page Turn CC Page Turn &#xff08;CC 翻页&#xff09;主要用于模拟书页翻动的效果。通过使用该效果&#xff0c;用户可以创建出像书页或杂志页面翻动的视觉效果&#xff0c;增强影片的交互性和视觉吸引力。 ◆ ◆ ◆ 效果属性说明 Contro…...

【数据仓库设计基础(四)】数据仓库实施步骤

文章目录 1&#xff0e;定义范围2&#xff0e;确定需求3&#xff0e;逻辑设计1&#xff09;建立需要的数据列表2&#xff09;识别数据源3&#xff09;制作实体关系图 4&#xff0e;物理设计1&#xff09;性能优化2&#xff09;数仓的拓展性 5&#xff0e;装载数据6&#xff0e;…...

GridSearchCV 工具介绍

目录 1、定义 2、工作流程 3、示例代码 4、总结 1、定义 GridSearchCV 是一个用于超参数调优的工具&#xff0c;它在给定的参数网格中执行交叉验证&#xff0c;以确定最佳的参数组合。通过穷举搜索&#xff08;exhaustive search&#xff09;来寻找最佳参数&#xff0c;即…...

基于 SSM 框架的旅游文化管理平台

本系统采用基于JAVA语言实现、架构模式选择B/S架构&#xff0c;Tomcat7.0及以上作为运行服务器支持&#xff0c;基于JAVA等主要技术和框架设计&#xff0c;idea作为开发环境&#xff0c;数据库采用MYSQL5.7以上。 开发环境&#xff1a; JDK版本&#xff1a;JDK1.8 服务器&…...

chatgpt技术总结(包括transformer,注意力机制,迁移学习,Ray,TensorFlow,Pytorch)

最近研读了一些技术大咖对chatgpt的技术研讨&#xff0c;结合自己的一些浅见&#xff0c;进行些许探讨。 我们惊讶的发现&#xff0c;chatgpt所使用的技术并没有惊天地泣鬼神的创新&#xff0c;它只是将过去的技术潜能结合现在的硬件最大化的发挥出来&#xff0c;也正因如此&am…...

vertx的学习总结4

一、异步数据和事件流 1.为什么流是事件之上的一个有用的抽象&#xff1f; 2.什么是背压&#xff0c;为什么它是异步生产者和消费者的基础&#xff1f; 3.如何从流解析协议数据&#xff1f; 1. 答&#xff1a;因为它能够将连续的事件序列化并按照顺序进行处理。通过将事件…...

SpringBoot心旅售票管理系统

本心旅售票管理系统采用基于JAVA语言实现、架构模式选择B/S架构&#xff0c;Tomcat7.0及以上作为运行服务器支持&#xff0c;基于JAVA、springboot、vue等主要技术和框架设计&#xff0c;idea作为开发环境&#xff0c;数据库采用MYSQL5.7以上。 采用技术: SpringBootVueMySQL...

CUDA C编程权威指南:1-基于CUDA的异构并行计算

什么是CUDA&#xff1f;CUDA&#xff08;Compute Unified Device Architecture,统一计算设备架构&#xff09;是NVIDIA&#xff08;英伟达&#xff09;提出的并行计算架构&#xff0c;结合了CPU和GPU的优点&#xff0c;主要用来处理密集型及并行计算。什么是异构计算&#xff1…...

R语言易错点(持续更新中~~)

1.R向量元素的索引(下标)是从1开始的&#xff0c;而非0 >x [1] 1 2 4>x[3] [1] 4 2.[]和[ [ ] ] mylist<-list(stud.id1234,stud.name"Tom",stud.marksc(10,3,14,25,19)) > mylist $stud.id [1] 1234$stud.name [1] "Tom"$stud.marks [1] 10…...

Multisim14.0仿真(二十七)基于UC3842的反激式开关电源的设计及仿真

一、UC3842简介&#xff1a; UC3842为固定频率电流模式PWM控制器。它们是专门为OFF−线和直流到直流转换器应用与最小的外部组件。内部实现的电路包括用于精确占空比控制的修剪振荡器、温度补偿参考、高增益误差放大器、电流传感比较器和理想适合于驱动功率MOSFET的高电流温度极…...

SpringMVC(二)@RequestMapping注解

我们先新建一个Module。 我们的依赖如下所示&#xff1a; <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0"xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaL…...

NXP公司K60N512+PWM控制BLDC电机

本篇文章介绍了使用NXP公司提供的塔式快速原型系统来驱动控制带霍尔传感器的无刷直流电机。文章涉及的塔式快速原型系统主要包括以下四个独立板卡&#xff1a;1.塔式系统支撑模块&#xff08;TWR-Elevator&#xff09;&#xff0c;用以连接微控制器以及周边模块&#xff1b;2.低…...

CAA的VS Studio安装

文章目录 一、官网下载VS Studio二、勾选如下安装信息三、更改软件安装位置四、17专业版密钥 一、官网下载VS Studio 官网下载地址&#xff1a; https://visualstudio.microsoft.com/zh-hans/downloads/ 下载对应版本后&#xff0c;以VS Studio2017为例&#xff1a; 二、勾…...

条件查询和数据查询

一、后端 1.controller层 package com.like.controller;import com.like.common.CommonDto; import com.like.entity.User; import com.like.service.UserService; import jakarta.annotation.Resource; import org.springframework.web.bind.annotation.GetMapping; import …...

JSP旅游平台管理

本系统采用基于JAVA语言实现、架构模式选择B/S架构&#xff0c;Tomcat7.0及以上作为运行服务器支持&#xff0c;基于JAVA、JSP等主要技术和框架设计&#xff0c;idea作为开发环境&#xff0c;数据库采用MYSQL5.7以上。 开发环境&#xff1a; JDK版本&#xff1a;JDK1.8 服务器&…...

简单走近ChatGPT

目录 一、ChatGPT整体背景认知 &#xff08;一&#xff09;ChatGPT引起关注的原因 &#xff08;二&#xff09;与其他公司的竞争情况 二、NLP学习范式的发展 &#xff08;一&#xff09;规则和机器学习时期 &#xff08;二&#xff09;基于神经网络的监督学习时期 &…...

10.3作业

#include <myhead.h> int main(int argc, const char *argv[]) { mkfifo(“./f1”,0777); mkfifo(“./f2”,0777); pid_t cpid fork(); if(0 < cpid) { int fdw open(“./f1”,O_WRONLY); int fdr open(“./f2”,O_RDONLY); char buf[128] “”; while(1) { bzero…...

Springboot中的@Import注解~

Import注解是Spring框架中的注解之一&#xff0c;用于导入其他配置类或者组件 Import注解的作用有以下几点&#xff1a; 导入其他配置类&#xff1a;可以使用Import注解导入其他的配置类&#xff0c;将其加入到当前配置类中&#xff0c;从而可以共享配置信息 导入其他组件&am…...

Linux 安全 - SUID机制

文章目录 一、文件权限位二、SUID简介 一、文件权限位 &#xff08;1&#xff09; $ ls -l text.txt -rw-rw-r-- 1 yl yl 0 Sep 28 16:25 text.txt其中第一个字段-rw-rw-r–&#xff0c;我们可以把它分为四部分看&#xff1a; -rw-rw-r--&#xff08;1&#xff09;- &a…...

OpenClaw轻量化部署:在树莓派上运行Qwen3.5-9B微型服务

OpenClaw轻量化部署&#xff1a;在树莓派上运行Qwen3.5-9B微型服务 1. 为什么选择树莓派部署OpenClaw 去年夏天&#xff0c;我在整理个人文档时被重复的文件分类工作折磨得苦不堪言。当时我就在想&#xff1a;如果能有个AI助手帮我自动处理这些琐事该多好。但市面上的云端方案…...

Path of Building终极指南:5分钟掌握流放之路最强Build规划工具

Path of Building终极指南&#xff1a;5分钟掌握流放之路最强Build规划工具 【免费下载链接】PathOfBuilding Offline build planner for Path of Exile. 项目地址: https://gitcode.com/GitHub_Trending/pa/PathOfBuilding Path of Building&#xff08;简称PoB&#x…...

MAX30102传感器总是不准?Arduino避坑指南:从焊接绝缘到手指摆放的5个关键细节

MAX30102传感器精度优化全攻略&#xff1a;从硬件调试到算法校准的完整解决方案 MAX30102作为一款高集成度生物传感器&#xff0c;在心率、血氧监测领域应用广泛&#xff0c;但许多开发者在Arduino平台上使用时常遇到数据不稳定、测量偏差大的问题。本文将系统性地剖析影响测量…...

3大场景解析:开源工具如何重构MobaXterm的专业版体验

3大场景解析&#xff1a;开源工具如何重构MobaXterm的专业版体验 【免费下载链接】MobaXterm-Keygen MobaXterm Keygen Originally by DoubleLabyrinth 项目地址: https://gitcode.com/gh_mirrors/mob/MobaXterm-Keygen 在开发者的日常工作中&#xff0c;终端工具的选择…...

Qt官网抽风连不上?亲测有效的Qt6在线安装网络问题终极解决手册

Qt6在线安装网络问题终极解决手册&#xff1a;从反复失败到一次成功 看着Qt安装器上那个刺眼的"无法连接服务器"提示&#xff0c;我第27次点击了重试按钮。作为一名有十年经验的开发者&#xff0c;我从未想过会在安装环境这一步耗费整整一个下午。这不是个例——根据…...

1Panel v2.0.5及以下版本紧急加固指南:除了升级,这3个临时措施也能防住RCE

1Panel高危漏洞应急防护实战&#xff1a;3种临时方案守护服务器安全 当安全警报拉响时&#xff0c;运维团队往往面临两难选择&#xff1a;立即升级可能影响业务连续性&#xff0c;不升级则暴露在严重威胁之下。针对近期曝光的1Panel远程代码执行漏洞&#xff08;CVE-2025-54424…...

3步构建智能无人机防御系统:从威胁识别到实时追踪的实践指南

3步构建智能无人机防御系统&#xff1a;从威胁识别到实时追踪的实践指南 【免费下载链接】Anti-UAV &#x1f525;&#x1f525;Official Repository for Anti-UAV&#x1f525;&#x1f525; 项目地址: https://gitcode.com/gh_mirrors/an/Anti-UAV 一、安全威胁&#…...

5分钟极速部署!Billion Mail容器化方案助力邮件营销升级 [特殊字符]

5分钟极速部署&#xff01;Billion Mail容器化方案助力邮件营销升级 &#x1f680; 【免费下载链接】BillionMail Billion Mail is a future open-source email marketing platform designed to help businesses and individuals manage their email campaigns with ease 项目…...

绿色低碳+高效交付:中集模块化数据中心用实力印证中国方案全球竞争力

随着人工智能与绿色转型成为全球经济增长核心引擎&#xff0c;高算力需求正推动数据中心建设向预制化、高效能方向加速演进。中集集团&#xff08;000039.SZ/2039.HK&#xff09;凭借工业化制造与全球交付优势&#xff0c;2025年在模块化数据中心&#xff08;AIDC&#xff09;领…...

Scala入门必修课:val与var的深度对比与选择指南

Scala入门必修课&#xff1a;val与var的深度对比与选择指南1. 引言&#xff1a;变量定义的灵魂拷问2. 基础概念&#xff1a;val与var的定义2.1 直观区别2.2 类型推导3. 深入理解&#xff1a;从编译到执行3.1 编译后的字节码差异3.2 内存与性能考量4. 实际应用&#xff1a;选择指…...