首页 > 极客资料 博客日记
「模拟赛」多校 A 层联训 15
2024-10-31 20:00:06极客资料围观16次
A. 追逐游戏 (chase)
没啥意义的水题,但赛时没调出来。
分讨,LCA
设 \(S\) 和 \(T\) 的 LCA 为 \(lca\)
-
\(S'\) 为 \(lca\) 的祖先节点的时候,\(S'\) 到达 \(s->T\) 这条链上的第一个点 \(x\) 一定是 \(lca\)
-
否则,用 LCA 求出来 \(S'\) 到 \(s->T\) 这条链上的第一个点 \(x\)(\(x\) 要么是 S 与 S' 的 LCA,要么是 T 与 S' 的 LCA)
判断 \(S'\) 到 \(x\) 的时候 \(S\) 有没有到 \(x\),到了则答案一定是两个人都到 \(T\) 点的时候;否则答案就是 \(S->S'\) 路径上 两人一起走,最早的相遇位置
B.统计
hash
举个例子,如以下形式时,\([i,j]\) 区间显然时合法区间
发现我们只需要维护多出来的红色部分的 hash 值,并用 map 记录每种 hash 值出现的次数即可
需要卡常,各种 map 好像很难过,需要手写哈希表,直接粘的板子,改天仔细学习一下
C.软件工程
贪心、思维、前缀最大值优化 dp
分为两种情况做
-
直接贪心,考虑把最长的 \(k-1\) 条线段各放一个集合,其余的放到一个集合里
-
处理一下 dp
线段大致分为以下几种形式:
对于 1 线段这种存在一条线段(2 线段)被自己完全覆盖的,容易发现它若和 2 线段放一起,那么贡献就是 2 号线段的贡献。
所以我们考虑去掉 1 线段这一类的线段,这样我们把剩余的线段按左端点排好序后,也能保证右端点是单调不减的,那么显然同一个集合里我们选连续的一些线段是较优的
这样 dp 就是显然的了,转移如下:
前缀最大值优化一下就好啦
最后记得把去掉的那些有包含线段的线段的贡献加到答案上,具体就是对于表示选了 \(j\) 个集合的 \(f_{j}\) 加上 去掉的那些线段里前 \(k-j\) 大的长度总和 更新答案
标签:
上一篇:多租户系统的应用架构
下一篇:你的第一个Solana SPL
相关文章
最新发布
- Nuxt.js 应用中的 prerender:routes 事件钩子详解
- 【问题解决】Tomcat由低于8版本升级到高版本使用Tomcat自带连接池报错无法找到表空间的问题
- 【FAQ】HarmonyOS SDK 闭源开放能力 —Vision Kit
- 六、Spring Boot集成Spring Security之前后分离认证流程最佳方案
- 《JVM第7课》堆区
- .NET 8 高性能跨平台图像处理库 ImageSharp
- 还在为慢速数据传输苦恼?Linux 零拷贝技术来帮你!
- 刚毕业,去做边缘业务,还有救吗?
- 如何避免 HttpClient 丢失请求头:通过 HttpRequestMessage 解决并优化
- 让性能提升56%的Vue3.5响应式重构之“版本计数”