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

F - LIS on Tree

F - LIS on Tree (atcoder.jp)

问题描述:树上LIS。

普通LIS。O(n * n)

void solve() {int n; cin>>n;vector<int> f(n + 1),a(n+1);for(int i = 1; i <= n; ++i) {cin>>a[i];f[i] = 1;for(int j = 1; j < i; ++j) {if(a[i] > a[j]) f[i] = max(f[i], f[j] + 1);}}cout<<*max_element(all(f));
}

二分优化。O(n * log(n))

/// 版本1
void solve() {vector<int> f;int n; cin>>n;for(int i = 0; i < n; ++i) {int t; cin>>t;auto pos = lower_bound(all(f), t);if(pos == f.end()) f.push_back(t);else *pos = t;}cout<<f.size();
}
/// 版本2
void solve() {int n; cin>>n;vector<int> f(n,INF);int ans = -1;for(int i = 0; i < n; ++i) {int t; cin>>t;int pos = lower_bound(all(f), t) - f.begin();f[pos] = t;ans = max(ans, pos);}cout<<ans + 1;
}

对于树上LIS来说,如果只考虑一条链的话,就是裸LIS。由于对于一个父节点,它的儿子节点都共用父节点往上的那一条链上的权值,而且遍历完1个儿子节点,对其余的儿子节点的操作中需要将这个儿子节点的操作撤销掉。这个撤销很像回溯。数据范围很大,需要LIS优化,如果用版本1的LIS,每次需要判断是改回还是删除,可能删除这个操作会超时;用版本2的LIS,只需要考虑改回就行,更简单些。

具体代码思路:无向树建树。遍历到节点u时,计算到这个节点u的LIS长度,之后将节点u的权值加入到LIS数组中,找儿子节点,最后再将 “之前节点u的权重加入到LIS数组中” 的这一步进行回溯/撤销。

具体代码:

// 版本2 AC代码
void solve() {int n; cin>>n; vector<vector<int>> g(n+1);vector<int> val(n + 1),f(n+1, INF), ans(n + 1);for(int i = 1; i <= n; ++i) cin>>val[i];for(int i = 1; i < n; ++i) {int u,v; cin>>u>>v;g[u].push_back(v);g[v].push_back(u);}auto dfs = [&](auto &&dfs, int u, int fu) -> void {// 找到第一个大于等于val[u]的位置int pos = lower_bound(f.begin()+1, f.end(), val[u]) - f.begin(); int tmp = f[pos]; // 记录这个位置的权重,因为要撤销/回溯f[pos] = val[u]; // 将pos位置更改为val[u]ans[u] = max(ans[fu], pos); // 求LIS长度for(auto y: g[u]) {if(y == fu) continue;dfs(dfs, y,u);}// 进行撤销操作f[pos] = tmp;};dfs(dfs, 1, 0);for(int i = 1; i <= n; ++i) cout<<ans[i]<<endl;
}
// 版本1 RE代码 可能还有错误没有找到》
void solve() {int n; cin>>n; vector<vector<int>> g(n+1);vector<int> val(n + 1),f, ans(n + 1);for(int i = 1; i <= n; ++i) cin>>val[i];for(int i = 1; i < n; ++i) {int u,v; cin>>u>>v;g[u].push_back(v);g[v].push_back(u);}auto dfs = [&](auto &&dfs, int u, int fu) -> void {int tag = 0;auto pos = lower_bound(all(f), val[u]);int len = pos - f.begin() + 1;if(pos == f.end()) {tag = -1;f.push_back(val[u]);} else {tag = *pos;*pos = val[u];}ans[u] = len;for(auto y: g[u]) {if(y == fu) continue;dfs(dfs, y,u);}if(tag == -1) {f.erase(f.end()-1);} else *pos = tag;};dfs(dfs, 1, 0);for(int i = 1; i <= n; ++i) cout<<ans[i]<<endl;
}

相关文章:

F - LIS on Tree

F - LIS on Tree (atcoder.jp) 问题描述&#xff1a;树上LIS。 普通LIS。O(n * n)。 void solve() {int n; cin>>n;vector<int> f(n 1),a(n1);for(int i 1; i < n; i) {cin>>a[i];f[i] 1;for(int j 1; j < i; j) {if(a[i] > a[j]) f[i] max…...

2023 年全国大学生数学建模B题目-多波束测线问题

B题目感觉属于平面几何和立体几何的问题&#xff0c;本质上需要推导几何变换情况&#xff0c;B题目属于有标准答案型&#xff0c;没太大的把握不建议选择&#xff0c;可发挥型不大。 第一问 比较简单&#xff0c;就一个2维平面的问题&#xff0c;但有点没理解&#xff0c;这个…...

qt creater11 翻译国际化教程教程:

先出效果图。 闲聊几句&#xff1a;qt这个翻译很方便&#xff0c;能直接导出项目里所有文字。 具体步骤如下&#xff1a; 在Qt中&#xff0c;我们可以使用QTranslator类来实现多语言切换。以下是一般步骤&#xff1a; 1. 在你的源代码中&#xff0c;所有需要翻译的字符串都…...

【AWS实验 】在 AWS Fargate 上使用 Amazon ECS 部署应用程序

文章目录 实验概览目标实验环境任务 1&#xff1a;连接到实验命令主机任务 2&#xff1a;将应用程序容器化任务 3&#xff1a;构建 Web2048 容器任务 4&#xff1a;创建 Amazon ECR 存储库并推送 Docker 映像任务 5&#xff1a;创建 ECS 集群任务 6&#xff1a;测试应用程序总结…...

matlab几种求解器的选择fsolve-sole-vpasolve

文章目录 fsolvesolvevpasovle总结vpasovle的结果fsovle的结果 fsolve 求数值解 result_xfsolve(my_fun,x0,options)参数: my_fun:待求解函数&#xff0c;作为一个.m文件 x0:初始值&#xff0c;向量&#xff0c;可以仅仅指定其中的几项solve 强大的求解器。在方程组中求解析…...

无限访问 GPT-4,OpenAI 强势推出 ChatGPT 企业版!

继 ChatGPT 收费大降价、推出 App 版等系列动作之后&#xff0c;OpenAI 于今日宣布正式发布面向企业的 AI 助手——ChatGPT Enterprise 版。 与 To C 端的 ChatGPT 版本有所不同的是&#xff0c;该版本可以以更快速度无限制地访问 GPT-4&#xff0c;还可以用来处理更长输入的上…...

MySQL的故事——Schema与数据类型优化

Schema与数据类型优化 一、选择优化的数据类型 更小的通常更好 应该尽量使用可以正确存储数据的最小类型&#xff0c;更小的数据类型通常更快&#xff0c;因为他们占用更少的磁盘&#xff0c;内存和CPU缓存&#xff0c;并且处理时需要的CPU周期更少 简单就好 更简单的数据类型…...

C++编译和链接

编译和链接 一、源代码的组织 头文件&#xff08;.h&#xff09;&#xff1a;#include头文件、函数的声明、结构体的声明、类的声明、模板的声明、内联函数、#define和const定义的常量等。 源文件&#xff08;.cpp&#xff09;&#xff1a;函数的定义、类的定义、模板具体化的…...

【CSDN技术】Markdown编辑器如何使用-csdn博客编写入门

Markdown编辑器如何使用-csdn博客编写入门 欢迎使用Markdown编辑器新的改变功能快捷键合理的创建标题&#xff0c;有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants 创建一个自…...

【docker】运行redis

拉取redis镜像 有多种选择&#xff1a; redis&#xff08;基础版&#xff09;redis/redis-stack&#xff08;包含redis stack server和RedisInsight&#xff09;redis/redis-stack-server&#xff08;仅包含redis stack server&#xff09; docker pull redis docker pull r…...

Paddle训练COCO-stuff数据集学习记录

COCO-stuff数据集 COCO-Stuff数据集对COCO数据集中全部164K图片做了像素级的标注。 80 thing classes, 91 stuff classes and 1 class ‘unlabeled’ 数据集下载 wget --directory-prefixdownloads http://images.cocodataset.org/zips/train2017.zip wget --directory-prefi…...

SpringBoot 框架学习

java 学习笔记指路 基础知识 Python转java补充知识 Java中常见的名词解释 前端 【黑马程序员pink老师前端】HTML 【黑马程序员pink老师前端】JavaScript基础大总结 【黑马程序员pink老师前端】JavaScript函数与作用域 【黑马程序员pink老师前端】JavaScript对象 数据库 【黑马程…...

java - lua - redis 完成商品库存的删减

java调用lua脚本完成对商品库存的管理 主页链接 微风轻吟挽歌的主页 如若有帮助请帮忙点赞 //lua脚本 获取到内存不够的商品StringBuilder sb new StringBuilder();//定义一个数组存储可能缺少库存的值sb.append(" local table {} ");//获取值sb.append(" …...

dbeaver离线安装clickhouse连接驱动

Clickhouse 数据库连接工具——DBeaver 主要介绍了Clickhouse 数据库连接工具——DBeaver相关的知识&#xff0c;希望对你有一定的参考价值。 Clickhouse 数据库连接工具——DBeaver 1.下载 DBeaver 和 连接驱动 https://dbeaver.io/files/dbeaver-ce-latest-x86_64-setup.…...

2024腾讯校招后端面试真题汇总及其解答(二)

11.如果同时有5个任务在10分钟之后提交,或者更多,那么如果是一个个从队列中拿数据,那么前一个任务会影响后续任务执行时间,说一下解决思路 你的问题是一个典型的并发处理问题。如果你的系统是单线程的,那么的确,前一个任务的执行时间会影响后续任务的执行时间。但是,你…...

datagrip 相关数据连接信息无缝迁移

背景 因为公司换电脑了&#xff0c;接触的项目比较多&#xff0c;不同项目&#xff0c;不同环境的数据库连接有好几十个&#xff0c;如果在新电脑上挨个重新连接一遍劳心劳力&#xff0c;所以想看一下能不能直接将之前保存的连接信息直接迁移到新的电脑上面。 为此&#xff0c…...

不就是G2O嘛

从零开始一起学习SLAM | 理解图优化&#xff0c;一步步带你看懂g2o代码 SLAM的后端一般分为两种处理方法&#xff0c;一种是以扩展卡尔曼滤波&#xff08;EKF&#xff09;为代表的滤波方法&#xff0c;一种是以图优化为代表的非线性优化方法。不过&#xff0c;目前SLAM研究的主…...

C#开发的OpenRA游戏之系统参数选项按钮

C#开发的OpenRA游戏之系统参数选项按钮 前面分析了信标按钮,从图上可以看到,靠右边的按钮,就是系统参数选项按钮: 这个按钮与前面三个按钮是不一样的,虽然它们在排列位置上是放在一起,但是处理的方法方式是不一样的,因为这个选项按钮,并不需要发命令给服务器,再返回来…...

苹果启动2024年SRDP计划:邀请安全专家使用定制iPhone寻找漏洞

苹果公司昨天&#xff08;8月30日&#xff09;正式宣布开始接受2024 年iPhone安全研究设备计划的申请&#xff0c;iOS 安全研究人员可以在 10 月底之前申请安全研究设备 SRD。 SRD设备是专门向安全研究人员提供的iPhone14Pro&#xff0c;该设备具有专为安全研究而设计的特殊硬…...

std::make_shared和new初始化智能指针的区别

先看代码&#xff1a; class Base {public:Base(int num):a(num) {std::cout << "Base() construct" << std::endl;}~Base() {std::cout << "Base() deconstruct" << std::endl;}int Get() {return a;}private:int a; };void tes…...

RAG的墓志铭:当AI不再需要检索

上个月读到一篇在 Hacker News 上引发热议的文章——《The RAG Obituary: Killed by Agents, Buried by Context Windows》。作者 Nicolas Bustamante 是金融科技公司 Fintool 的创始人&#xff0c;他在文中抛出了一个颇具争议的观点&#xff1a;RAG&#xff08;检索增强生成&a…...

Obsidian Local Images Plus 终极指南:如何一键解决所有本地图片管理难题

Obsidian Local Images Plus 终极指南&#xff1a;如何一键解决所有本地图片管理难题 【免费下载链接】obsidian-local-images-plus This repo is a reincarnation of obsidian-local-images plugin which main aim was downloading images in md notes to local storage. 项…...

D-Net:动态大内核与特征融合如何革新三维医学影像分割?

1. 为什么医学影像分割需要动态大内核&#xff1f; 医学影像分割就像给CT或MRI照片上的器官、肿瘤画精确边界线。传统方法像用固定倍数的放大镜观察——要么看不清细节&#xff08;小内核&#xff09;&#xff0c;要么错过整体结构&#xff08;大内核&#xff09;。我在处理腹…...

LabVIEW新手避坑指南:用For循环和数组搞定水仙花数,别再手动算啦!

LabVIEW实战&#xff1a;用For循环与数组高效求解水仙花数的5个关键技巧 水仙花数这个经典的编程练习题&#xff0c;在文本编程语言中可能只需十几行代码&#xff0c;但切换到LabVIEW的图形化编程环境时&#xff0c;不少初学者会陷入连线混乱和逻辑纠结。本文将从实际工程视角…...

Beyond Compare 5 三步快速激活方案:从评估错误到专业版授权的完整指南

Beyond Compare 5 三步快速激活方案&#xff1a;从评估错误到专业版授权的完整指南 【免费下载链接】BCompare_Keygen Keygen for BCompare 5 项目地址: https://gitcode.com/gh_mirrors/bc/BCompare_Keygen Beyond Compare 5 作为业界领先的文件比对与合并工具&#xf…...

3KW无线充电系统设计:开环控制与闭环控制的MATLAB Simulink仿真模型,采用双边L...

3KW无线充电系统设计&#xff08;MATLAB simulink仿真模型&#xff09; 控制方式&#xff1a;开环控制闭环控制 拓扑结构&#xff1a;双边LCC拓扑结构 输入电压&#xff1a;750V 输出电压&#xff1a;400V 传输功率&#xff1a;3KW 最近在折腾一个3KW无线充电系统的仿真项目&am…...

GLM-OCR开发者实操手册:Gradio client调用+批量图片识别脚本示例

GLM-OCR开发者实操手册&#xff1a;Gradio client调用批量图片识别脚本示例 你是不是也遇到过这样的场景&#xff1a;手头有一堆发票、合同或者产品说明书图片&#xff0c;需要把里面的文字、表格甚至公式都提取出来&#xff1f;一张张手动录入或者用传统OCR工具&#xff0c;不…...

wan2.1-vae开源可部署:支持国产操作系统(麒麟/UOS)的适配方案

wan2.1-vae开源可部署&#xff1a;支持国产操作系统&#xff08;麒麟/UOS&#xff09;的适配方案 1. 平台介绍 muse/wan2.1-vae 文生图是基于 Qwen-Image-2512 模型的AI图像生成平台&#xff0c;支持中英文提示词&#xff0c;可生成高质量、高分辨率的图像。该平台特别针对国…...

bully使用教程

bully是一款用于破解Wi-Fi Protected Setup&#xff08;WPS&#xff09;的工具&#xff0c;主要通过暴力破解WPS PIN码来获取无线网络的访问权限。WPS是一种简化Wi-Fi设备连接的协议&#xff0c;由于其设计缺陷&#xff0c;使得通过暴力破解PIN码来获取网络密钥成为可能。bully…...

软件工程实战:如何用数据流图搞定图书馆管理系统设计(附避坑指南)

软件工程实战&#xff1a;如何用数据流图搞定图书馆管理系统设计&#xff08;附避坑指南&#xff09; 图书馆管理系统是软件工程课程中的经典案例&#xff0c;但许多初学者在绘制数据流图时容易陷入"画了等于没画"的困境——要么遗漏关键外部实体&#xff0c;要么数据…...