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

20251002NOIP模拟赛

T4:

题目大意:

定义一个数组 \(a\) 是良好的,当且仅当可以选择若干个(可以为 0)不交的区间,将他们内部 reverse 之后升序。
给定 \(n\) 和排列 \(a\),对于每个 \(k\),求有多少子序列不包含 \(a_{k}\) 且是良好的。
\(n \le 3 \times 10^3\)

解题思路:

考虑刻画一个良好的数组,发现一定能将其分为若干段,使得段内倒序,段之间正序,且互不相交。
这显然是一一对应的。
f
由于 \(n \le 3000\) 且合法性与相邻的有关,所以考虑 dp。
自然的,设 \(dp_{i,j}\) 表示前 \(i\) 个数,最大值为 \(j\) 的方案数。
转移可以直接用前缀和优化,而且 \(i,j\) 内部可以预处理 \(f_{i,j}\),表示 \(i\) 开头, \(j\) 结尾的递减子序列的方案数。
\(O(n^2 \log n)\)

我们要算每一个 \(x\),求不包含 \(x\) 的方案数,但我们发现枚举完 \(x\) 之后要合并前后缀,但直接做是 \(O(n^3)\) 的。
因为不包含 \(x\) 需要在 \(y \ne x\) 时更新,而这样是不好更新的,所以考虑拿整体减去经过 \(x\) 的方案。

那么我们枚举 \(l,r\) 表示 \(x\) 所在的段内的开头和结尾,那么内部的方案数是 \(f_{l,x} \times f_{x,r}\),而外部的则是 \(pre_{l - 1, a_{r} - 1} \times suf_{r + 1, a_{l} + 1}\)
其中 \(pre\)\(suf\) 分别为做一遍前缀/后缀 \(dp\) 的二维前缀和。

但是这些数看起来都是相互关联的,而 \(pre\)\(suf\) 的结构比较复杂,所以考虑优化一些 \(f_{l,x} \times f_{x,r}\) 之类的东西。
由于 \(n \le 3000\),也就是说我们有枚举两个值的机会,考虑先枚举 \(l\) 试试。

因为 \(x \le r\),所以后面的能影响前面的,而且前面的不影响后面的。
所以我们倒着枚举 \(x\),看一下后面的 \(x\) 作为 \(r\) 时对前面的 \(x\) 有什么影响。

对于后面一个 \(r\) 对于当前点的影响,我们可以发现只有 \(f_{x,r}\) 不确定,但是我们发现 \(f\) 是可以递推的,所以将不同的 \(r\) 赋一个对应的权值,相加即可。
\(O(n^2 \log n)\)

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

相关文章:

  • P10279 [USACO24OPEN] The Winning Gene S题解
  • zsh
  • 从零搭建雷池WAF:环境配置、安装部署与Web防护实战
  • 论文速读记录 | 2025.10
  • 【Rust GUI开发入门】编写一个本地音乐播放器(15. 记录运行日志) - Jordan
  • 6 种常见 AI 编程协作便捷的方法总结
  • DeploySharp开源发布:让C#部署深度学习模型更加简单
  • 别样的国庆作业大战
  • ROS2之服务
  • macOS上优雅运行Docker容器
  • 题解:CF1770H Koxia, Mahiru and Winter Festival
  • HarmonyOS之LocalStorage - 详解
  • Spring Boot Logback:实现定时任务日志与业务日志隔离 - Higurashi
  • 网络流 最小割 Dinic算法
  • 15.VLANIF(2025年9月30日) - 教程
  • 树莓派搭建NAS之一:安装系统
  • 新手Markdown学习
  • 马云归来,“新零售”不死 - 指南
  • RNN
  • 10.2笔记
  • Shell / Bash 学习
  • 【Linux 架构探幽:从入门到内核・系统编程开篇】基础指令与权限精讲,筑牢框架制作根基
  • 使用 Dart 进行验证码识别
  • 用 Rust 进行验证码识别
  • teset3
  • Java并发编程(5)
  • 定时任务详解
  • 华为wlan无线配置 - 教程
  • PINN训练新思路:把初始条件和边界约束嵌入网络架构,解决多目标优化难题
  • 可持久化数据结构