首页 / 资讯中心 / 文章详情

【题解】「COCI 2024.1」Milano C.le [附 LIS 模版]

📅 2026/6/30 4:31:53 👁️ 次浏览
【题解】「COCI 2024.1」Milano C.le [附 LIS 模版]
P10225 [COCI 2023/2024 #3] Milano C.le - 洛谷 (luogu.com.cn)不难发现能放在同一个站台的 ab 点对和必须满足且。转化成二维表格平面图就是一条单调下降的线最后有多少条这样的线就有多少个站台。进一步我们发现这些线的起始端点必须连成一条单调上升的线不然两条线就能并成一条。所以最后求的就是以为下标排序集合里最长上升子序列的长度。话说到这个 LIS 啊老久没看了已经更新换代到我有点不认识的版本了。LIS 模板代码长这样// hs 个人见解有错指出 // hansang 是我以前笔名proMatheus 是现用名 #includebits/stdc.h using namespace std; const int N 2e5 10; int a[N], b[N]; int len 0; int main () { ios::sync_with_stdio(false); cin.tie(0); int n; cin n; for (int i 1; i n; i ) { cin a[i]; } /* 我们需要维护一个 b 数组 其中 b[i] 代表当前上升子序列长度为 i 时可能的最小数值注意不是下标 定义 len 为当前 LIS最长上升子序列 的长度 按顺序遍历 a 数组时如果 a[i] b[len] 说明 a[i] 可以直接接在现有的 LIS 后面 反则 a[i] 替换 b 数组中第一个大于或等于它的数 有人会问了判断条件时不是只用到 b[len] 吗 为什么还要更新 b 数组里别的数 如果每次 a[i] b[len] 时都只用 a[i] 更新 b[len] 那怎么保证 a[i] b[len - 1] 呢 由此可得要维护整个 b 数组的递增关系 综上一个贪心加二分时间复杂度 O(nlogn)相当不错 */ len 0; b[len] 0; for (int i 1; i n; i ) { if (a[i] b[len]) { len ; b[len] a[i]; } else { *lower_bound(b 1, b len 1, a[i]) a[i]; } } cout len \n; return 0; }本题 ac 代码#includebits/stdc.h using namespace std; const int N 2e5 10; int a[N], b[N], t[N]; int bb[N]; int main () { ios::sync_with_stdio(false); cin.tie(0); int n; cin n; for (int i 1; i n; i ) { cin a[i]; } for (int i 1; i n; i ) { cin b[i]; } for (int i 1; i n; i ) { t[a[i]] b[i]; } int len 0; bb[len] 0; for (int i 1; i n; i ) { if (t[i] bb[len]) { len ; bb[len] t[i]; } else { *lower_bound(bb 1, bb len 1, t[i]) t[i]; } } cout len \n; return 0; }

相关新闻

大数据志愿填报“冲稳保”如何搭配院校梯度

大数据志愿填报“冲稳保”如何搭配院校梯度

高考出分在即，志愿填报成了千万考生和家长面前最棘手的一道题。“冲、稳、保”三个字说起来简单，可真正落到96个或45个志愿里，比例一旦失调——轻则高分低就，重则直接滑档。大数据专业近年热度不减、分数波动不小，梯度…

📅 2026/6/30 4:31:53
2026年上海楼道里的神秘追踪：管道井里的猫与狗故事

2026年上海楼道里的神秘追踪：管道井里的猫与狗故事

上海是一座高楼林立、弄堂密集的城市。可以说，每栋楼、每个小区的小角落都是宠物走失的高发地，尤其是那深邃的管道井里更是充满了神秘感。本报对上海多家专业寻宠团队进行了调研，其中有一家名叫“宠团圆”的本土老牌团队展现了惊人的寻宠成功…

📅 2026/6/30 5:41:56
IntelliJ IDEA 之偏好设置

IntelliJ IDEA 之偏好设置

打开设置界面5.2、设置外观主题如上图所示，本示例设置一个比较浅色的外观主题。5.3、设置文字大小如上图所示，可以设置使用鼠标滚轮改变编辑器中的文字大小。如上图所示，还可以手动设置文字大小、行高和字体。5.4、设置智能提示如上图所示&am…

📅 2026/6/30 5:41:56
医疗人工智能的Harness Engineering：面向安全、可控与合规的大模型系统工程（一）

医疗人工智能的Harness Engineering：面向安全、可控与合规的大模型系统工程（一）

摘要 将大语言模型与 AI Agent 应用于临床场景，面临的核心挑战已从单纯的模型性能转向系统的可靠性、安全性与可监管性。本文提出“医疗 AI Harness Engineering”的概念，定义为在医疗大模型周围构建的一套包含上下文管理、工具调用、护栏、评估回路、可观测性与人机协同的可…

📅 2026/6/30 5:41:56
PHP代码审计实战：从str_replace过滤绕过到RCE漏洞利用

PHP代码审计实战：从str_replace过滤绕过到RCE漏洞利用

1. 项目概述：一次典型的PHP代码审计与RCE实战复盘最近在CTFShow平台上刷题，遇到了这道名为“web11”的题目，它完美地融合了代码审计、PHP特性利用和远程命令执行（RCE）的考点。这类题目在CTF的Web安全赛道中非常经典&am…

📅 2026/6/30 5:41:56
GitHub Actions + 阿里云 OSS：OIDC 免密同步构建产物

GitHub Actions + 阿里云 OSS：OIDC 免密同步构建产物

装包同步到阿里云 OSS，后续官网可以提供国内镜像链接。全程使用 OIDC 免密认证，不存长期 AccessKey。 过程中遇到不少问题，带着 claude code 折腾了几个小时，才整好。下边是详细的过程记录。顺带说一句 Molio 在 github 上开源了&…

📅 2026/6/30 5:41:56
单台Nginx部署多个前端项目：IP路径区分 \+ 域名区分完整实战

单台Nginx部署多个前端项目：IP路径区分 \+ 域名区分完整实战

在日常开发、测试、内网生产环境中，我们经常遇到一个刚需场景：只有一台Nginx服务器，需要同时部署多个独立的Vue/React前端项目。 很多新手会在这里产生困惑：服务器只有一个公网/内网IP，没有多个域名，怎么区…

📅 2026/6/30 5:36:56
如何永久备份微信聊天记录：本地化数据管理完全指南

如何永久备份微信聊天记录：本地化数据管理完全指南

如何永久备份微信聊天记录：本地化数据管理完全指南 【免费下载链接】WeChatMsg 提取微信聊天记录，将其导出成HTML、Word、CSV文档永久保存，对聊天记录进行分析生成年度聊天报告 项目地址: https://gitcode.com/GitHub_Trending/we/WeChatMs…

📅 2026/6/30 0:01:32
专业级Windows系统优化工具：WinUtil一站式自动化解决方案

专业级Windows系统优化工具：WinUtil一站式自动化解决方案

专业级Windows系统优化工具：WinUtil一站式自动化解决方案 【免费下载链接】winutil Chris Titus Techs Windows Utility - Install Programs, Tweaks, Fixes, and Updates 项目地址: https://gitcode.com/GitHub_Trending/wi/winutil Windows系统管理长期以来…

📅 2026/6/30 0:01:32
审计来了，数据权限全开——审计走了，怎么确保权限全部关掉？

审计来了，数据权限全开——审计走了，怎么确保权限全部关掉？

引言：审计结束三个月了，审计员的权限还没关某城商行每年按照监管要求开展至少一次数据安全审计。审计期间，内审部门需要抽样检查各类业务数据——交易流水、客户信息、员工操作日志、权限配置记录。这些数据分布在不同系统中，审计…

📅 2026/6/29 4:18:42