首页 > 其他分享 >『MdOI R4』Phoenix 官解(也许)更清晰的阐释

『MdOI R4』Phoenix 官解(也许)更清晰的阐释

时间:2023-08-23 09:00:32浏览次数:43  
标签:R4 cnt 排列 Phoenix limits 官解 分裂 val 区间

\[\large(\sum\limits_{i=1}^n |s_i|)-(\sum\limits_{i=1}^{n-1} |s_{p_i}\bigcap s_{p_{i+1}}|)=|\bigcup\limits_{i=1}^n s_i| \]

观察题目中式子,不难想到如果对二进制拆位,那么相当于要求对于每个二进制位,包含这一位的集合必须排列在一段区间内,因为左式中每一位至少出现一次,而右式限制了至多出现一次,要让这一位只出现一次就只能排列在区间内

那么现在我们得到了 \(m\) 个区间,容易发现对于两个相交的区间,它们的顺序就会固定下来,或者倒过来,有两种方案,而完全包含的区间的限制就是挖掉一些段,剩下的任意排列,再对挖掉的段选位置放

如果这时直接用 \(PQ\ Tree\) 来做就可以得到一个 \(O(nm)\) 的做法,但是比较复杂,这里不赘述

考虑用并查集合并区间,然后对于包含关系建出一棵树

对于相交的区间,我们可以任意排列的部分实际上是下图所示分裂出来的三个区域

在相交区间合并的过程中维护这些分裂出来的段就可以得到所有能任意排列的区间,定义 \(cnt\) 为最后 \(size>1\) 的连通块数,最后分裂出来了 \(x_1,x_2,\dots,x_k\) 段,包含区间的树形结构上的答案是 \(val\),则最后的答案就是:

\[\large2^{cnt}\times val\times \prod\limits_{i=1}^kx_i! \]

\(cnt\) 可以用并查集统计,\(val\) 是 trivial 的组合问题,关键在于求后面的 \(\prod\)

\(PQ\ Tree\) 强行完成了这个分裂的过程,但是我们并不需要用数据结构,观察到对于每一个位,加入它对应的区间实际上进行了对所有集合是否包含这个位的区分,那么最终分裂下来的这些段,就一定会是一个个相同的集合

所以用一个 \(map\) 就可以轻松地解决这个问题

具体实现还是有一些细节

标签:R4,cnt,排列,Phoenix,limits,官解,分裂,val,区间
From: https://www.cnblogs.com/pidan123/p/17650122.html

相关文章

  • IdentityServer4 客户端模式(.net5)
    添加服务端(api)1.添加Nuget包Nuget添加IdentityServer42.添加Config.cs配置类publicclassConfig{///<summary>///提示invalid_scope添加///</summary>publicstaticIEnumerable<ApiScope>ApiScopes=>newApiScope[]{newApiS......
  • ASEMI肖特基模块MBR400100CT参数规格
    编辑-ZMBR400100CT参数描述:型号:MBR400100CT反向重复峰值电压(VRRM):100V正向直流电流(I0):400A正向(不重复)浪涌电流(IFSM):3300A结温(TJ):-40to+175℃储存温度(Tstg):-40to+150℃结壳热阻Rth(j-c):0.18℃/W正向峰值电压(VFM):0.75V反向重复峰值电流(IRRM):20mA重量(Weight)......
  • ASEMI肖特基模块MBR400100CT参数规格
    编辑-ZMBR400100CT参数描述:型号:MBR400100CT反向重复峰值电压(VRRM):100V正向直流电流(I0):400A正向(不重复)浪涌电流(IFSM):3300A结温(TJ):-40to+175℃储存温度(Tstg):-40to+150℃结壳热阻Rth(j-c):0.18℃/W正向峰值电压(VFM):0.75V反向重复峰值电流(IRRM):20mA重量(Weight):100g MBR400......
  • 如何在本地给 vue-router4 扩展功能?
    背景前段时间给基于vue3的H5项目做一些优化,该项目经常会有一些页面间的通信,譬如选择地址、乘机人等信息后回填到上一个页面。对于这种简单、频繁的通信,实在不想搞成重火力(eg:pinia)。最好让使用者用完即走,不用操心除业务逻辑之外的任何事情。路由控制页面通信既然是页面间的......
  • VueRouter4 路由
    import{createRouter,createWebHistory}from'vue-router'//createRouter创建路由实例,===>newVueRouter()//1.history模式:createWebHistory()http://xxx/user//2.hash模式:createWebHashHistory()http://xxx/#/user//vite的配置import.meta.env.BASE_......
  • 强化学习Chapter4——两个基本优化算法(1)
    强化学习Chapter4——两个基本优化算法(1)上一节导出了状态价值函数的贝尔曼方程以及最优状态价值函数:\[\begin{aligned}V^\pi(s)&=E_{a\sim\pi,s’\simP}[r(s,a)+\gammaV^\pi(s‘)]\\&=\sum_{a}\pi(a|s_t)(r(s_t,a)+\gamma\sum_{s'}p(s'|s_t,a)V^\pi(s'))\\V^*(s)&am......
  • IdentityServer4 密码模式
    1.Config添加用户的配置publicclassConfig{///<summary>///提示invalid_scope添加///</summary>publicstaticIEnumerable<ApiScope>ApiScopes=>newApiScope[]{newApiScope("api")};publicstaticIEnu......
  • Jmeter45 Dubbo Sampler 插件及其教程
    转载Jmeter(五十)DubboSampler-紫陌花间客-博客园(cnblogs.com) 一、前言随着分布式普及,日常工作中多少会接触到dubbo,对于dubbo接口的调用或者压测等等。调用最简单的方式便是telnet,或者泛化调用的方式。进入telnet命令行,invoke对应方法以及传入对应的参数即可。当然......
  • CSSYZ 思维训练 R4
    ProblemA题目大意给出一张只有0和1的矩阵,可以将$k$个点反转,求是否可以使这个矩阵中心对称,多测。算法分析这题是一个非常经典的贪心策略问题,我们发现,如果一个矩阵中心对称,那么$a_{i,j}$一定要和$a_{n-i+1,m-j+1}$所以,我们只要求出有几组应该对称的点并没有......
  • 怎么给hbase的表加二级索引映射到phoenix
    在HBase表中添加二级索引映射到Phoenix在大数据应用中,HBase是一个开源的分布式数据库,而Phoenix是一个基于HBase的SQL层。HBase提供了高性能的读写能力,而Phoenix则使得对HBase表的查询更加简单和直观,类似于传统的关系型数据库。然而,HBase自身并不支持二级索引,这对于一些需要高效查......