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

【解题报告】牛客挑战赛70 maimai

题目链接

这个挑战赛的 F F F是我出的,最后 zhoukangyang 爆标了。。。orzorz

记所有有颜色的边的属性集合 S S S

首先在外层容斥,枚举 S ∈ [ 0 , 2 w ) S\in [0,2^w) S[0,2w),计算被覆盖的的边中不包含 S S S 中属性,并且没有被覆盖的边的数目恰好为 i i i 的配对方案数。

暴力的 DP 做法是记录子树内还没有被匹配的点的数目,复杂度 O ( n 5 ) O(n^5) O(n5),不能通过。出题人特意卡了这种做法。

如果一条边没有覆盖,那么所有点对间的路径都不能经过这条边,这样我们可以把一个连通块分成两个子联通块进行求解。但是这样就要记录连通块里面所有的点,无法通过

考虑二项式反演。记 g ( i ) g(i) g(i) 表示钦定断了 i i i 条边(即 i i i条边没有被覆盖)的方案数, f ( i ) f(i) f(i) 表示恰好断了 i i i 条边的方案数,注意这里的下标 i i i 不包含一定不被覆盖的边。那么有:

g ( i ) = ∑ j = i n − 1 ( j i ) f ( j ) ⇒ f ( i ) = ∑ j = i n − 1 ( − 1 ) j − i ( j i ) g j g(i)=\sum _{j=i}^{n-1}\binom{j}{i}f(j)\Rightarrow f(i)=\sum_{j=i}^{n-1}(-1)^{j-i}\binom{j}{i}g_j g(i)=j=in1(ij)f(j)f(i)=j=in1(1)ji(ij)gj

g ( i ) g(i) g(i) 是好算的,也就是剩下的每个连通块内部任意连边的方案数的乘积

h ( n ) h(n) h(n) 表示大小为 n n n 的连通块任意连边的方案数,如果 n n n 为奇数那么答案是 0 0 0,如果 n n n 为偶数那么答案是 ( n − 1 ) × ( n − 3 ) × . . . × 1 (n-1)\times (n-3)\times ...\times 1 (n1)×(n3)×...×1

考虑 DP。设 d p ( u , i , j ) dp(u, i, j) dp(u,i,j) 表示以 u u u 为根的子树,已经断了 i i i 条边,连通块大小为 j j j 的方案数。对于一条边 ( u , v , w ) (u,v,w) (u,v,w) 转移式子如下:

1.1 1.1 1.1 d p ( u , i , j ) × d p ( v , i 2 , j 2 ) × h ( j 2 ) → d p ( u , i + i 2 + 1 , j ) dp(u, i, j) \times dp(v, i_2, j_2) \times h(j_2) \to dp(u, i + i_2+1, j) dp(u,i,j)×dp(v,i2,j2)×h(j2)dp(u,i+i2+1,j)

1.2 1.2 1.2 如果 w ∉ S w\notin S w/S d p ( u , i , j ) × d p ( v , i 2 , j 2 ) → d p ( u , i + i 2 , j + j 2 ) dp(u,i,j)\times dp(v,i_2,j_2)\to dp(u,i+i_2,j+j_2) dp(u,i,j)×dp(v,i2,j2)dp(u,i+i2,j+j2)

这个 DP 的时间复杂度上界是 O ( n 4 ) O(n^4) O(n4) 的,因此总复杂度 O ( 2 w n 4 ) O(2^wn^4) O(2wn4)

但是注意到每个连通块大小都是必须偶数,因此常数极小,实测单次 DP 计算量在 1 0 6 10^6 106 左右,链的情况可以卡满。注意要把 DP 值为 0 的状态跳过,否则无法通过

数据里面造了一些几条链并起来的情况,暴力要跑 4s 以上,std 能稳定在 0.5s 内出解。随机数据下基本卡不了。如果有人暴力冲过去了或者正解被卡常了,出题人在这里谢罪:(

考虑到打这场比赛的大佬肯定还是比较多的,如果场切这道题的大佬们有更精确的分析复杂度的方式欢迎赛后分享。

upd:F 存在 O ( 2 w n 3 ) O(2^wn^3) O(2wn3) 的做法,具体是将DP状态的第一维看成多项式并用点值来维护。详见zhoukangyang的代码。

http://www.lryc.cn/news/192088.html

相关文章:

  • 算启新程 智享未来 | 紫光展锐携手中国移动共创数智未来
  • thinkphp5.1 获取缓存cache(‘cache_name‘)特别慢,php 7.0 unserialize 特别慢
  • 【Linux】UNIX 术语中,换页与交换的区别和Linux 术语中,换页与交换的区别?
  • 零基础学python之集合
  • PromptScript:轻量级 DSL 脚本,加速多样化的 LLM 测试与验证
  • 强化学习(Reinforcement Learning)与策略梯度(Policy Gradient)
  • JUC之ForkJoin并行处理框架
  • 【牛客面试必刷TOP101】Day8.BM33 二叉树的镜像和BM36 判断是不是平衡二叉树
  • CSS padding(填充)
  • C语言达到什么水平才能从事单片机工作
  • Java架构师理解SAAS和多租户
  • 关于Java线程池相关面试题
  • ExcelBDD Python指南
  • 基于深度学习的驾驶员疲劳监测系统的设计与实现
  • B树、B+树详解
  • 使用hugging face开源库accelerate进行多GPU(单机多卡)训练卡死问题
  • IDEA 修改插件安装位置
  • 牛客网SQL160
  • HDFS Java API 操作
  • 论文阅读之【Is GPT-4 a Good Data Analyst?(GPT-4是否是一位好的数据分析师)】
  • 【数据结构】:二叉树与堆排序的实现
  • 纯css手写switch
  • PyTorch 深度学习之处理多维特征的输入Multiple Dimension Input(六)
  • LeetCode【438】找到字符串中所有字母异位词
  • 关于LEFT JOIN的一次理解
  • 各报文段格式集合
  • 【算法-动态规划】最长公共子序列
  • 区块链游戏的开发流程
  • 目标检测网络系列——YOLO V2
  • 15. Java反射和注解