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

Zhengrui #3346. DINO

被我暴力干过去了qwq。

你考虑一个事情,打开大样例,点击 .out 文件,发现几乎全是 \(0\),你想一想为什么,本质上是你的 \(mex\) 每增加 \(1\),你的点的数量就会至少翻一倍,也就是说,答案最多是 \(O(\log n)\) 级别的。

此时考虑直接设 \(f_{i, j}\) 为以 \(i\) 为根的子树进行完操作后有多少种满足 \(a_i = j\) 的,但是你发现这个转移不太好转。

没关系,先想暴力转移是,状压 DP,每次设一个 \(g_s\) 表示我的值的所用情况为 \(s\) 的方案数,然后你惊奇的发现这个 \(2^{ans}\) 正好和 \(O(\log n)\) 抵消掉了,所以答案就是 \(O(n^2 \log n)\) 的了(\(O(\log n)\) 是转移内部时间复杂度)。

然后此时加个只有一个儿子的特判,你就能通过此题了。


当然,还是要说明一下本题的正解。

考虑让重儿子单独合并,轻儿子按照我们上面的那个做法做,发现此时每做一次的时间复杂度为轻儿子的子树大小,由于一个点至多跳 \(O(\log n)\) 次,所以复杂度被优化到了 \(O(n \log^2 n)\)

其实本质上就是类似折半合并的过程可以减少复杂度一样。

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

相关文章:

  • Pytorch深度学习训练
  • P11894 「LAOI-9」Update
  • ZR 2025 NOIP 二十连测 Day 3
  • 读书报告
  • P14223 [ICPC 2024 Kunming I] 乐观向上
  • 别再用均值填充了!MICE算法教你正确处理缺失数据
  • 非主流网站程序IndexNow添加方法
  • 卷积神经网络视频读书报告
  • C 语言 - 内存操作函数以及字符串操作函数解析
  • 以*this返回局部对象的两种情况
  • 2025.10.15
  • 软件开发流程
  • Kali 自定义ISO镜像
  • 2025秋_12
  • 10月15日
  • 第七章:C控制语句:分支和跳转
  • 感知节点@5@ ESP32+arduino+ 第三个程序FreeRTOS 上 LED灯显示 和 串口打印ASCII表
  • pytorch实训题
  • 数据库基础知识1
  • 近期模拟赛汇总
  • 实用指南:部署Tomcat11.0.11(Kylinv10sp3、Ubuntu2204、Rocky9.3)
  • Hbase的安装与配置
  • 【Azure App Service】App Service是否支持PHP的版本选择呢?
  • OAuth/OpenID Connect 渗透测试完全指南
  • Problem K. 置换环(The ICPC online 2025)思路解析 - tsunchi
  • Go 语言和 Tesseract OCR 识别英文数字验证码
  • Markdown转换为Word:Pandoc模板使用指南 - 实践
  • 2025年10月小程序开发公司最新推荐排行榜,小程序定制开发,电商小程序开发,预订服务小程序开发,活动报名小程序开发!
  • 复习CSharp
  • Rust 和 Tesseract OCR 实现英文数字验证码识别