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

深圳网页制作与网站建设服务器网站收录教程

深圳网页制作与网站建设服务器,网站收录教程,网站建设源代码怎么搭建,企业网站需要多少钱题目链接 这个挑战赛的 F F F是我出的,最后 zhoukangyang 爆标了。。。orzorz 记所有有颜色的边的属性集合 S S S 。 首先在外层容斥,枚举 S ∈ [ 0 , 2 w ) S\in [0,2^w) S∈[0,2w),计算被覆盖的的边中不包含 S S S 中属性&#xff0c…

题目链接

这个挑战赛的 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.ritt.cn/news/20018.html

相关文章:

  • 怎么网站是什么语言做的南通做网站推广的公司
  • 建设营销型网站公司百度视频推广
  • 360免费网站推广seo
  • 上传下载文件网站开发的php源码公司软文代写
  • 南宁网站建设报价seo优化排名
  • 一级a做爰片免费网站孕交视频营销培训
  • 合肥做推拉棚网站推广河南seo技术教程
  • 佛山建网站哪家好网络营销工具及其特点
  • 做商城的网站用什么框架好南昌seo报价
  • 嘉兴秀洲区建设局网站国际重大新闻事件2023
  • 顺义网站建设厦门人才网官网
  • 网站设计流程大致分为几个阶段武汉seo群
  • 大连专业手机自适应网站建设维护大泽山seo快速排名
  • 阿里云网站建设怎么样做网站公司
  • wordpress post提交seo关键词排名优化评价
  • 网站运营及推广方案如何写软文
  • 政府网站设计风格舆情报告范文
  • 大学生想做网站全球搜索引擎排名2022
  • 毕业设计网站前端代做广告精准推广平台
  • 如何做私彩网站华为手机网络营销策划方案
  • 新闻网站怎么做漯河搜狗关键词优化排名软件
  • 建网站一条龙免费网页模板网站
  • 公众号电影网站是怎么做的电脑优化大师哪个好
  • 网页翻译软件seo关键词优化培训
  • 临沂做商城网站设计营销推广计划书
  • asp网站开发全程视频内蒙古seo
  • 人与马做的网站网络营销渠道名词解释
  • 网站漏洞谷歌seo查询
  • 什么是网站结构网页设计基础
  • 做招聘网站需要多少钱网站开发公司排行榜