当前位置: 首页 > 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…...

【网络】每天掌握一个Linux命令 - iftop

在Linux系统中&#xff0c;iftop是网络管理的得力助手&#xff0c;能实时监控网络流量、连接情况等&#xff0c;帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...

Unity3D中Gfx.WaitForPresent优化方案

前言 在Unity中&#xff0c;Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染&#xff08;即CPU被阻塞&#xff09;&#xff0c;这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案&#xff1a; 对惹&#xff0c;这里有一个游戏开发交流小组&…...

JavaScript 中的 ES|QL:利用 Apache Arrow 工具

作者&#xff1a;来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗&#xff1f;了解下一期 Elasticsearch Engineer 培训的时间吧&#xff01; Elasticsearch 拥有众多新功能&#xff0c;助你为自己…...

Opencv中的addweighted函数

一.addweighted函数作用 addweighted&#xff08;&#xff09;是OpenCV库中用于图像处理的函数&#xff0c;主要功能是将两个输入图像&#xff08;尺寸和类型相同&#xff09;按照指定的权重进行加权叠加&#xff08;图像融合&#xff09;&#xff0c;并添加一个标量值&#x…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

c++ 面试题(1)-----深度优先搜索(DFS)实现

操作系统&#xff1a;ubuntu22.04 IDE:Visual Studio Code 编程语言&#xff1a;C11 题目描述 地上有一个 m 行 n 列的方格&#xff0c;从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子&#xff0c;但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...

Sklearn 机器学习 缺失值处理 获取填充失值的统计值

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 使用 Scikit-learn 处理缺失值并提取填充统计信息的完整指南 在机器学习项目中,数据清…...

高防服务器价格高原因分析

高防服务器的价格较高&#xff0c;主要是由于其特殊的防御机制、硬件配置、运营维护等多方面的综合成本。以下从技术、资源和服务三个维度详细解析高防服务器昂贵的原因&#xff1a; 一、硬件与技术投入 大带宽需求 DDoS攻击通过占用大量带宽资源瘫痪目标服务器&#xff0c;因此…...

[特殊字符] 手撸 Redis 互斥锁那些坑

&#x1f4d6; 手撸 Redis 互斥锁那些坑 最近搞业务遇到高并发下同一个 key 的互斥操作&#xff0c;想实现分布式环境下的互斥锁。于是私下顺手手撸了个基于 Redis 的简单互斥锁&#xff0c;也顺便跟 Redisson 的 RLock 机制对比了下&#xff0c;记录一波&#xff0c;别踩我踩过…...