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

8.9套题

A. 猴猴吃苹果

题意:给定根节点k,求访问点的顺序,使得每次从上一个点到当前点的权值最大。访问过的点权值为0。权值一样时,输出最小编号

思路:由于是双向边,先求根节点到每一个节点的距离值。在第一轮中,最深的叶节点一定为答案,那么这一条路径就被访问过了,权值变为0,这个叶节点相同路径上的其他点到根节点(最后一个未被标记的点)的权值就改变了。所以从最优的叶节点出发,dfs往上跳,直到访问到已经被访问过的点为止即可。最后排序更新后的权值

#include<bits/stdc++.h>using namespace std;const int N = 1e6 + 10;int n,k,d[N],tot;
bool vis[N];
struct node{int id,val;
}a[N];
vector<int> v[N];
inline bool cmp(node p,node q){if(p.val!=q.val)  return p.val>q.val;else return p.id<q.id;
}
void dfs1(int p,int fa){for(int t:v[p]){if(t==fa)  continue;d[t]=d[p]+1;dfs1(t,p);}
}
void dfs2(int p,int fa){if(vis[p])  return;tot++;vis[p]=true;for(int t:v[p]){if(t==fa||d[t]>=d[p])  continue;dfs2(t,p);}
}
int main(){cin>>n>>k;for(int i=1,x;i<n;i++){cin>>x;v[i].push_back(x);v[x].push_back(i);}dfs1(k,-1);vis[k]=true;for(int i=0;i<n;i++){a[i].id=i;a[i].val=d[i];}sort(a,a+n,cmp);
//	for(int i=0;i<n;i++)  cout<<a[i].id<<" ";for(int i=0;i<n;i++){tot=0;dfs2(a[i].id,-1);a[i].val=tot;
//    	cout<<tot<<" "<<a[i].id<<endl;}sort(a,a+n,cmp);cout<<k<<endl;for(int i=0;i<n;i++){if(a[i].val)cout<<a[i].id<<endl;}return 0;
}

B. 猴猴吃香蕉

题意:选取n个数中的若干个数,使得它们的乘积为k

思路:计数dp,容易得出f[j]+=f[j/a[i]]的转移方程式。使得a[i]为组成k的一个因子。由于k的范围不可接受,于是筛出k的所有因子,如果a[i]/x能整除,说明这个数能被分解。f[j]+=f[a[i]/t[j]],由于因子较大,且个数趋近根号n,需要离散化

最终dp方程:f[j]+=f[pos[a[i]/t[j]]],答案为f[pos[k]]

C. 猴猴的比赛

题意:给定两棵树,求一个节点x在两棵树中有相同祖先的对数

思路:考虑求出每一个点的子树中的范围[L,R](连续的),对于另一颗树而言,每次处理一个点答案计数完成后,就将这个点在第一棵树中的位置标记为1。答案计数为所有父节点[L,R]中1的数量。注意在遍历子节点时,需要减去子树所有点的[L,R]中1的数量,防止重复运算

核心代码:

void dfs2(int p,int fa){//L[p]为点p的dfn序for(int t:g[p]){if(t==fa)  continue;ans-=BIT.query(R[t])-BIT.query(L[t]);dfs2(t,p);} ans+=BIT.query(R[p])-BIT.query(L[p]);//整个子树 BIT.add(L[p],1);
}

相关文章:

8.9套题

A. 猴猴吃苹果 题意&#xff1a;给定根节点k&#xff0c;求访问点的顺序&#xff0c;使得每次从上一个点到当前点的权值最大。访问过的点权值为0。权值一样时&#xff0c;输出最小编号 思路&#xff1a;由于是双向边&#xff0c;先求根节点到每一个节点的距离值。在第一轮中&…...

Python 爬取网页水务数据并实现智慧水务前端可视化

提示&#xff1a;本文爬取深圳市环境水务集团有限公司的公开数据作为数据样例进行数据分析与可视化。 文章目录 一、爬虫二、对爬取的数据进行数据库、excel的存储与数据处理1.代码实现 三、应用Flask框架将后端获取数据后渲染到前端四、前端Echarts的使用1.下载echarts.min.js…...

百度智能云发布3款轻量级+2款场景大模型

文心大模型ERNIE 3.5是目前百度智能云千帆大模型平台上最受欢迎的基础大模型之一。针对用户的常见通用的对话场景&#xff0c;ERNIE 3.5 在指令遵循、上下文学习和逻辑推理能力三方面分别进行了能力增强。 ERNIE Speed作为三款轻量级大模型中的“大个子”&#xff0c;推理场景…...

UE基础 —— 编辑器界面

菜单栏 UE中每个编辑器都有一个菜单栏&#xff0c;部分菜单会出现在所有编辑器窗口中&#xff0c;如File、Window、Help&#xff0c;其他则是其编辑器特有的&#xff1b; 主工具栏 UE中部分最常用的工具和命令的快捷方式&#xff1b; 1&#xff0c;保存按钮&#xff08;ctrls&a…...

2024年Vue组件库大比拼:谁将成为下一个Element?

2024 年&#xff0c;Vue生态蓬勃发展&#xff0c;越来越多的开发者开始探索更适合自己项目的组件库。 今天我们来看一下2024年最受欢迎的几款Vue开源组件库&#xff0c;除了Element&#xff0c;开发者们还有哪些选择呢&#xff1f; 1.Vuetify Vuetify是由社区支持的Vue组件库&…...

SS9283403 sqlite3交叉编译并部署到SS928(六)

1.Sqlite3下载 连接&#xff1a;SQLite Download Page 2.解压 tar zxvf sqlite-autoconf-3460000.tar.gz 3.配置并编译 进入解压目录&#xff0c;打开命令行&#xff0c;输入如下命令 ./configure CCaarch64-mix210-linux-gcc --hostarm-linux --prefix/home/mc/work/sqlite…...

java3d-1_4_0_01-windows-i586.exe

下载 Java 3D API 安装 C:\Program Files\Java\Java3D\1.4.0_01\bin C:\Java\jre6 C:\Java\jdk1.6.0_45 C:\Windows 记录下这 4 个目录&#xff0c;去检查下 4 哥目录下文件多了什么 检查目录① C:\Program Files\Java\Java3D\1.4.0_01\bin 检查目录② C:\Java\jre6 C:…...

Vue3中的history模式路由:打造无缝导航体验!

Hey小伙伴们&#xff0c;今天给大家带来Vue3中使用history模式路由的实战案例&#xff01;&#x1f31f; &#x1f50d; 项目背景 Vue3的路由功能非常强大&#xff0c;可以帮助我们轻松实现单页面应用中的页面切换。但是你知道吗&#xff1f;默认情况下Vue Router使用的是has…...

python(6)

一、datetime函数 方法一&#xff1a; 前一个datetime是模块。后一个datetime是类型 方法二&#xff1a; 方法三&#xff1a; 二、逆序字符串 三 、旋转字符串...

以Zed项目为例学习大型Rust项目的组织与管理

说明 Zed项目代码&#xff1a;https://github.com/zed-industries/zed.git本文项目代码&#xff1a;https://github.com/VinciYan/zed_workspace.git Zed是一款由Atom创始人开发的高性能、协作友好的现代开源代码编辑器&#xff0c;使用Rust编写&#xff0c;集成AI辅助功能&a…...

正点原子imx6ull-mini-Linux驱动之Linux RS232/485/GPS 驱动实验(23)

错误1&#xff1a;我一直找不到为什么我的minicom用不了&#xff0c;编译啥的都通过了&#xff0c;原来是我的密码文件命名错了&#xff0c;我就习以为常的命名为password&#xff0c;谁知道应该是passwd&#xff0c;所以以后该复制的还是复制&#xff0c;不然就容易找不到源头…...

用户上下文打通+本地缓存Guava

文章目录 &#x1f31e; Sun Frame&#xff1a;SpringBoot 的轻量级开发框架&#xff08;个人开源项目推荐&#xff09;&#x1f31f; 亮点功能&#x1f4e6; spring cloud模块概览常用工具 &#x1f517; 更多信息1.设计1.链路流程2.详细设计 2.网关过滤器获取唯一标识放到Hea…...

Windows图形界面(GUI)-MFC-C/C++ - 树形视图(Tree Control) - CTreeCtrl

公开视频 -> 链接点击跳转公开课程博客首页 -> ​​​链接点击跳转博客主页 目录 树形视图(Tree Control) - CTreeCtrl 创建和初始化 添加和删除项 获取和设置项属性 操作项 项选择变化 项双击 项展开 示例代码 树形视图(Tree Control) - CTreeCtrl 创建和初始…...

C语言 --- 枚举、位运算

&#xff08;一&#xff09;枚举 1.概念&#xff1a;枚举是指将变量的值一一列举出来&#xff0c;变量的值只限于列举出来的值的范围 2.作用&#xff1a;a.提高代码可读性&#xff1b;b.提高代码的安全性 3.枚举类型&#xff1a; enum 枚举名 { 列举各种值 //枚举元素或枚…...

12322222222

当您和老王不在同一个网段时&#xff0c;您们之间的通信需要通过路由器来实现。这是因为不同的网段被视为不同的网络&#xff0c;而路由器的作用之一就是连接不同的网络并负责数据包的转发。下面是详细的通信流程&#xff1a; 本地网络通信尝试&#xff1a;您的设备&#xff0…...

知识改变命运:Java 语言 【可变参数】

可变参数 概念&#xff1a;Java允许一个类中多个同名同功能但是参数不同的方法&#xff0c;封装为一个方法。 基本语法&#xff1a; 访问修饰符 返回值 方法名 (数据类型...参数名) { ...... }案例&#xff1a;写一个类名DyMethod 方法名sum 计算两个整数和&#xff0c;三个整…...

Spring及相关框架的重要的问题

Java框架 问题一&#xff1a;Spring框架中的单例bean是线程安全的吗&#xff1f; 看下图&#xff0c;不能被修改的成员变量就是无状态的类&#xff0c;无状态的类没有线程安全问题&#xff0c;所以在开发中尽量避免可修改的成员变量。 回答&#xff1a;不是线程安全的&#xf…...

Linux Vim教程

Linux Vim 教程 Vim&#xff08;Vi IMproved&#xff09;是一个强大的文本编辑器&#xff0c;广泛用于编程和系统管理。本文将带你全面了解 Vim 的基础使用、常用命令、高级功能等。 1. 安装 Vim 在大多数 Linux 发行版中&#xff0c;Vim 已经预装。如果没有&#xff0c;可以…...

【学习笔记】多进程信号量控制

目录 1、CreateSemaphore 2、ReleaseSemaphore 3、CreateEvent 4、SetEvent 5、WaitForSingleObject 程序案例1&#xff1a; 程序案例2&#xff1a; 1、CreateSemaphore 创建一个计数信号量对象&#xff0c;成功时返回信号量对象的句柄&#xff1b;失败时返回NULL&…...

Redis与Memorycache的区别

Redis与Memorycache主要是持久线程和持久化的区别 1、从性能方面来说&#xff1a; Redis是单线程的&#xff0c;优点是CPU开销小&#xff0c;省去多线程线程之间切换的开销&#xff0c;但是相对于Memorycache来说海量数据的相对较低 Memorycache使用了多线程技术&#xff0c;数…...

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八

现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet&#xff0c;点击确认后如下提示 最终上报fail 解决方法 内核升级导致&#xff0c;需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...

spring:实例工厂方法获取bean

spring处理使用静态工厂方法获取bean实例&#xff0c;也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下&#xff1a; 定义实例工厂类&#xff08;Java代码&#xff09;&#xff0c;定义实例工厂&#xff08;xml&#xff09;&#xff0c;定义调用实例工厂&#xff…...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中&#xff0c;新增了一个本地验证码接口 /code&#xff0c;使用函数式路由&#xff08;RouterFunction&#xff09;和 Hutool 的 Circle…...

如何在网页里填写 PDF 表格?

有时候&#xff0c;你可能希望用户能在你的网站上填写 PDF 表单。然而&#xff0c;这件事并不简单&#xff0c;因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件&#xff0c;但原生并不支持编辑或填写它们。更糟的是&#xff0c;如果你想收集表单数据&#xff…...

Docker 本地安装 mysql 数据库

Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker &#xff1b;并安装。 基础操作不再赘述。 打开 macOS 终端&#xff0c;开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...

C++.OpenGL (20/64)混合(Blending)

混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...

uniapp手机号一键登录保姆级教程(包含前端和后端)

目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号&#xff08;第三种&#xff09;后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...

解析奥地利 XARION激光超声检测系统:无膜光学麦克风 + 无耦合剂的技术协同优势及多元应用

在工业制造领域&#xff0c;无损检测&#xff08;NDT)的精度与效率直接影响产品质量与生产安全。奥地利 XARION开发的激光超声精密检测系统&#xff0c;以非接触式光学麦克风技术为核心&#xff0c;打破传统检测瓶颈&#xff0c;为半导体、航空航天、汽车制造等行业提供了高灵敏…...

DeepSeek源码深度解析 × 华为仓颉语言编程精粹——从MoE架构到全场景开发生态

前言 在人工智能技术飞速发展的今天&#xff0c;深度学习与大模型技术已成为推动行业变革的核心驱动力&#xff0c;而高效、灵活的开发工具与编程语言则为技术创新提供了重要支撑。本书以两大前沿技术领域为核心&#xff0c;系统性地呈现了两部深度技术著作的精华&#xff1a;…...