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

题解 QOJ 7766 [集训队互测 2023] 栞

网上的唯一一篇题解写的就是屎,还有一堆错误 /fn。

来发篇自己理解的题解,可能有问题,可能是我犯唐了 /dk。

考虑 sub3 的特殊性质 \(q_i=i\) 怎么做:

发现对于一个前缀 \(p[1 \sim i]\),且值域上恰好对应 \(1 \sim i\)\(\max_{1 \le j \le i} p_j=i\),可以直接对 \(1 \sim i\) 排序会满足 \(q\)\(i\) 项的限制。而且如果有两个满足该条件的前缀 \(1 \sim i, 1 \sim j(i \le j)\),那么对 \([1,i]\) 排序,\((i,j]\) 也是一个 \((i,j]\) 值域上的排列,也对 \((i,j]\) 排序,也会得到排列 \(q\) 的前 \(j\) 项。

由于 \(k\) 越小,答案字典序单降。所以我们应该尽可能让段数更多。因此我们对极小的段的个数 dp。设 \(f_{i,j}\) 代表前 \(i\) 个数划分成了 \(j\) 个极小段的方案数。答案即为 \(\sum_{k \le i \le n} f_{n,i}\) 对于 \(j \ge 1\),枚举最后的一个极小段长度 \(k\),有转移:

\[f_{i,j} = \sum_{1 \le k \le i - j + 1} f_{k,1}f_{i-k,j-1} \]

考虑 \(f_{i,0}\) 怎么算,考虑对于一个 \(1 \sim i-1\) 的排列,插入 \(i\),找到第一个满足上面条件的前缀 \(j\),那么 \(j\) 前面必须插入一个 \(i\)。则有转移:

\[f_{i,0} = \sum_{1 \le j < i} f_{j,0}j(i-1-j)! \]

接下来考虑正确做法:我们记满足 \(q_{i-1}>q_i\) 的点为一个断点。

考虑 \(f_k(p)\) 是怎么生成的,在 \(i \in [1, n-k]\) 选出一个最小值,删除它,得到 \(q_1\),继续这个流程得到 \(q_{2,3...}\),直到选中 \(n-k\)。按照上面的分段思路,很容易可以得到,\(1 \sim i\) 可以划分为一段的条件是 \(\{q_1,q_2,...,q_i\} = \{p_1,p_2,...,p_i\}\)

我们记 \(q\) 的第一个断点为 \(t\),第二个断点为 \(t'\),那么有以下结论:

\(q\) 生成的 \(p\) 的形态如下:

\([1,t)\) 被划分成若干段,\([t,t')\) 整体成一段,并且如果 \(t'>t+1\),则有 \(\min_{t \le i \lt t'} p_i\) 位于 \(t'-1\)\(q_{t+1}>q_{t-1}\),然后 \([t',n]\) 每个数字单独成一段。

一个简要的证明:

\([t,t')\) 单独成段的意义在于,可能会刚好把最小值卡在最后一个并且 \(k\) 刚好要求最小值独立成段,例如 \(q=[1,3,2,4,5,7,6],k=4\),一种存在的 \(p=[3,1,5,4,2,7,6]\)。如果最小值不在 \([t,t')\) 的末尾,完全可以把最后一个数单独裂出去,答案更优。如果不满足 \(q_{t-1}<q_{t+1}\),把 \(q_t\) 或者 \(q_{t+1}\) 合并到前面,答案更优。

那么枚举 \(t'\),答案即为 \(\sum_{t'}f_{t-1,k-(n-t'+2)}(t-t'-1)!\),时间复杂度 \(O(n^3)\)

http://www.hskmm.com/?act=detail&tid=35272

相关文章:

  • 遥感的基本概念
  • d435i 标定 imu和相机 用来复现vins_fusion - 教程
  • 20232418 2025-2026-1 《网络与系统攻防技术》实验二实验报告
  • CF1777E Edge Reverse
  • CSP-S 模拟赛 Day 19
  • CSP-S 模拟赛 Day 18
  • 2025年锥芯板品牌口碑排行榜单Top10:行业精选与选择指南
  • 2025年给汤机/重力铸造自动化/机加工自动化厂家推荐榜单:专业设备与智能解决方案权威解析
  • 2025年发电机厂家权威推荐榜:柴油发电机组/康明斯/玉柴/高压/大功率发电机组专业选购指南
  • 强网杯s9初赛 PolyEncryption wp
  • 基于TPS5450DDAR的24V转12V降压电路设计
  • 【STM32项目开源】基于STM32的智能宠物防丢监控便捷的系统
  • 20232409 2025-2026-1 《网络与系统攻防技术》实验三实验报告
  • 训高代
  • Spring AOP 原理
  • 详细介绍:医疗人读懂 LLM 的第二课: 使用 Transformer 下篇
  • 250921
  • P11233 [CSP-S 2024] 染色题解
  • 位运算(早晚得学会)
  • Jvm参数分类
  • 10/20
  • 2025年市面上工程石材产品排名前十:选购指南与品牌深度解析
  • 2025年市面上工程石材产品排名前十:权威榜单与选择指南
  • 意大利居留 办理 看小红书上的材料就行,部分材料可以到按手印再补交
  • 机器学习领导者分享AI技术与行业洞见
  • 利用错误配置的postMessage()函数实现DOM型XSS攻击
  • 听说今年很多应届硕士很难找到工作...
  • el-upload上传配合$confirm使用的问题
  • 博客的意義
  • 例子:vue3+vite+router创建导航菜单