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

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

Linux 文件类型,目录与路径,文件与目录管理

文件类型 后面的字符表示文件类型标志 普通文件&#xff1a;-&#xff08;纯文本文件&#xff0c;二进制文件&#xff0c;数据格式文件&#xff09; 如文本文件、图片、程序文件等。 目录文件&#xff1a;d&#xff08;directory&#xff09; 用来存放其他文件或子目录。 设备…...

TDengine 快速体验(Docker 镜像方式)

简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能&#xff0c;本节首先介绍如何通过 Docker 快速体验 TDengine&#xff0c;然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker&#xff0c;请使用 安装包的方式快…...

CentOS下的分布式内存计算Spark环境部署

一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架&#xff0c;相比 MapReduce 具有以下核心优势&#xff1a; 内存计算&#xff1a;数据可常驻内存&#xff0c;迭代计算性能提升 10-100 倍&#xff08;文档段落&#xff1a;3-79…...

Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!

一、引言 在数据驱动的背景下&#xff0c;知识图谱凭借其高效的信息组织能力&#xff0c;正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合&#xff0c;探讨知识图谱开发的实现细节&#xff0c;帮助读者掌握该技术栈在实际项目中的落地方法。 …...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比

在机器学习的回归分析中&#xff0c;损失函数的选择对模型性能具有决定性影响。均方误差&#xff08;MSE&#xff09;作为经典的损失函数&#xff0c;在处理干净数据时表现优异&#xff0c;但在面对包含异常值的噪声数据时&#xff0c;其对大误差的二次惩罚机制往往导致模型参数…...

基于PHP的连锁酒店管理系统

有需要请加文章底部Q哦 可远程调试 基于PHP的连锁酒店管理系统 一 介绍 连锁酒店管理系统基于原生PHP开发&#xff0c;数据库mysql&#xff0c;前端bootstrap。系统角色分为用户和管理员。 技术栈 phpmysqlbootstrapphpstudyvscode 二 功能 用户 1 注册/登录/注销 2 个人中…...

WebRTC从入门到实践 - 零基础教程

WebRTC从入门到实践 - 零基础教程 目录 WebRTC简介 基础概念 工作原理 开发环境搭建 基础实践 三个实战案例 常见问题解答 1. WebRTC简介 1.1 什么是WebRTC&#xff1f; WebRTC&#xff08;Web Real-Time Communication&#xff09;是一个支持网页浏览器进行实时语音…...

macOS 终端智能代理检测

&#x1f9e0; 终端智能代理检测&#xff1a;自动判断是否需要设置代理访问 GitHub 在开发中&#xff0c;使用 GitHub 是非常常见的需求。但有时候我们会发现某些命令失败、插件无法更新&#xff0c;例如&#xff1a; fatal: unable to access https://github.com/ohmyzsh/oh…...

轻量级Docker管理工具Docker Switchboard

简介 什么是 Docker Switchboard &#xff1f; Docker Switchboard 是一个轻量级的 Web 应用程序&#xff0c;用于管理 Docker 容器。它提供了一个干净、用户友好的界面来启动、停止和监控主机上运行的容器&#xff0c;使其成为本地开发、家庭实验室或小型服务器设置的理想选择…...