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);
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/396241.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【算法题】整数反转,一文彻底搞清!

目录 一、题目描述 二、解题思路 1、整数转为字符串 2、数学运算 三、参考答案 一、题目描述 整数反转 给你一个32位的有符号整数x&#xff0c;返回将x中的数字部分反转后的结果。 如果反转后整数超过32位的有符号整数的范围 [−231, 231 − 1] &#xff0c;就返回 0。 …

58 mysql 存储引擎之 MEMORY

前言 我们这里来看一下 MEMORY 存储引擎, 我们常见的那些 临时表什么的, 都是基于 MEMORY 在之前 我们也曾经调试过 相关内存临时表的信息 它主要是 使用 hp_scan, hp_find_record 等等 api 来操作内存中的信息 我们这里基于 information_schema.TABLES 这张基于 MEMORY 的…

加速 Spring Boot 3.3 迁移

1. 关键要点 为什么你应该升级你的服务迁移到 Spring Boot 3.3 时需要更新的内容OpenRewrite 如何帮助使升级更轻松、更快捷 2. 前言 现在Spring Boot 已经到了3.3&#xff0c;但是你在哪里&#xff1f;在过去的 3.x 版本更新中&#xff0c;我们看到了许多新功能&#xff0c;…

从EN标准到REACH法规:全面掌握CE认证洗涤剂的安全要求

一、什么是CE认证&#xff1f; CE认证&#xff08;Conformit Europenne&#xff09;是产品符合欧洲经济区&#xff08;EEA&#xff09;安全、健康、环保和消费者保护要求的标志。对于洗涤剂而言&#xff0c;CE认证证明该产品符合欧洲相关法规和标准&#xff0c;确保其在使用过…

牛客JS题(三十四)监听对象

注释很详细&#xff0c;直接上代码 涉及知识点&#xff1a; defineProperty实现深度监视递归终止条件引用传值闭包与作用域 题干&#xff1a; 我的答案 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8" /></head&…

ue5正确导入资源 content(内容),content只能有一个

把资源content下的东西&#xff0c;全部拷贝&#xff0c;放在项目的content下 content只能有一个

【HarmonyOS NEXT星河版开发学习】小型测试案例02-华为登录

个人主页→VON 收录专栏→鸿蒙开发小型案例总结​​​​​ 基础语法部分会发布于github 和 gitee上面&#xff08;还未发布&#xff09; 前言 通过此案例&#xff0c;不得不感叹鸿蒙的强大了&#xff0c;仅仅使用了26行代码就构建出来了这个界面&#xff0c;确实特别方便&#…

【git】简易的命令行入门教程

文章目录 1.Git 全局设置2.创建 git 仓库3.已有仓库 1.Git 全局设置 git config --global user.name "******" git config --global user.email "******qq.com"2.创建 git 仓库 mkdir ****** cd ****** git init touch README.md git add README.md git…

如何在notebook中运行nodejs

在 Python 生态系统的推动下&#xff0c;机器学习和人工智能日益流行&#xff0c;这带来了计算笔记本的概念。这些交互式计算平台主要是为以 Python 为中心的数据科学应用而开发的&#xff0c;它们将代码、计算输出、解释性文本和多媒体合并成一个有内聚力的文档。 作为 JavaS…

Liunx---批量安装服务器

目录 一、环境准备 一、环境准备 1.准备一台rhel7的主机并且打开主机图形。 2.配置好可用ip 3.做kickstart自动安装脚本后面需要用到DHCP&#xff0c;关闭VMware DHCP功能 二、安装图形化kickstart自动安装脚本的工具 yum install system-config-kickstart ----安装图形化生…

python模式设计代码之观察者模式

1、观察者模式 话题订阅模式。观察者模式有两个角色&#xff0c;分别是话题发布者和话题订阅者&#xff08;即观察者&#xff09;。发布者就是把消息发送给话题&#xff0c;观察者就是订阅这个话题从而得到最新的资讯。这个模式的作用就拿手机的消息推送来说&#xff0c;app身…

elasticsearch的学习(四):elasticsearch的一些基本概念

简介 elasticsearch的一些基本概念。 核心概念 索引&#xff1a;一个拥有相似特征的文档的集合。 类型&#xff1a;在索引中定义&#xff0c;是索引的一个逻辑上的分类&#xff0c;版本7以上已经弃用了。 文档&#xff1a;可被索引的基础信息单元&#xff0c;即一条数据&a…

Linux 错误码

目录 一、概述二、含义三、错误处理函数1、IS_ERR2、strerr、perror 一、概述 在 Linux 系统中&#xff0c;错误码是用来表示操作系统运行过程中发生的错误的数字代码。错误码通常由负数表示&#xff0c;0 表示成功&#xff0c;正数表示警告或其他非致命错误。 为了开发者更好…

【Linux基础】Linux基本指令(二)

目录 &#x1f680;前言一&#xff0c;mv指令二&#xff0c;more & less指令2.1 more 指令2.1 less指令 三&#xff0c;重定向技术(重要)3.1 echo指令3.2 输出重定向 >3.3 追加重定向 >>3.4 输入重定向 < 四&#xff0c;head & tail指令4.1 head 指令4.2 t…

【经验分享】ShardingSphere+Springboot-04:自定义分片算法(COMPLEX/STANDARD)

文章目录 3.4 CLASS_BASED 自定义类分片算法3.4.1 复杂分片自定义算法&#xff08;strategyCOMPLEX &#xff09;3.4.2 STANDARD 标准分片自定义算法## 进阶:star: 自定义算法范围查询优化 3.4 CLASS_BASED 自定义类分片算法 3.4.1 复杂分片自定义算法&#xff08;strategyCOM…

VUE结合elementui实现分页器列表

<template><div>外贸知识<div class"art-box"><div class"art-item-box"><div class"art-item" v-for"(art, index) in paginatedArtList" :key"index"><a :href"art.artsrc"&g…

离开SD的大佬们另组战队,开源新品牌冲击MJ王座

FLUX.1强势登场&#xff0c;秒杀Midjourney&#xff1f; Midjourney 6.1 才发表几天&#xff0c;FLUX.1立刻就来踢馆了 离职四个月&#xff0c;Stability AI 核心成员 Robin Rombach 前几日官宣成立了 Black Forest Labs&#xff0c;公司推出的第一个产品 FLUX.1&#xff0c;…

GStreamer 简明教程(一):环境搭建,运行 Basic Tutorial 1 Hello world!

文章目录 前言一、源码环境搭建二、Basic Tutorial 1 Hello world三、开启更多日志参考 前言 本系列文章将纪录学习 [GStreamer] 的过程。 为什么想学习 [GStreamer]&#xff0c;有这么几个原因&#xff1a; 多媒体处理是一个复杂的任务&#xff0c;[GStreamer] 的管道架构可…

Docker最佳实践(七):安装MinIO文件服务器

大家好&#xff0c;欢迎各位工友。 Minio是一个开源免费的高性能对象存储服务器&#xff0c;专为大规模数据集和高并发访问而设计。它具有出色的读写性能和低延迟&#xff0c;可以满足对数据速度和效率要求较高的应用场景。本篇呢我们就来演示一下如何在Docker中搭建Minio容器&…

Java的线程实现

我们知道&#xff0c;线程是比进程更轻量级的调度执行单位&#xff0c;线程的引入&#xff0c;可以把一个进程的资源分配和执行调度分开&#xff0c;各个线程既可以共享进程资源&#xff08;内存地址、文件I/O等&#xff09;&#xff0c;又可以独立调度。目前线程是Java里面进行…