首页 > 其他分享 >数二数 题解

数二数 题解

时间:2024-07-29 21:31:27浏览次数:13  
标签:那么 二数 题解 不可 端点 binom 识别 询问

我们定义 \(f_i\) 表示考虑 \(n=i\) 时的答案。

考虑怎样才能使得 Bob 存在一种出题方案使得 \(l\) 与 \(r\) 无法确定。假设包含点 \(i\) 的询问集合为 \(S_i\),那么当 \(S_l=S_r\) 时 \(l\) 与 \(r\) 无法确定。


发现:如果 \(a<b<c<d\),\(S_a=S_c\),\(S_b=S_d\),那么 \(S_a=S_b=S_c=S_d\)。也就是说,如果 \(a,c\) 无法确定,\(b,d\) 无法确定,那么 \(a,b\) 肯定也是无法确定的。

证明:\(S_a\) 肯定是 \(S_b\) 的子集。\(S_d\) 肯定是 \(S_a\) 的子集,因为 \(S_b=S_d\),那么 \(S_a=S_b=S_c=S_d\)。


定义区间 \([l,r]\) 为不可识别段,当且仅当 \(l\) 与 \(r\) 无法确定。特殊地,当 \(l=r\) 时,我们意义上认为 \(l\) 与他自己也无法确定(想象一下你不可能区分你自己和你自己),但实际上可以表示为 \(l\) 不与任何一个点产生关系。那么肯定存在一种划分方法,可以将 \([1,n]\) 不漏地划分为若干个互不相交的不可识别段。

证明:当两个不可识别段相交或包含时,可以使用上面的发现将其化为若干个互不相交的不可识别段。当一个点不与任何其它点产生关系时,可以将其自己作为一个不可识别段。


我们定义 \(g_{i,j}\) 表示将 \([1,i]\) 独立地划分为 \(j\) 个尽量长的不可识别段[1]、不考虑左右端点的询问方案数[2],这里的“独立地”表示每个询问只在不可识别段内,不会跨区间。

那么我们要计算跨区间的方案数。容易发现跨区间的询问的左端只能在区间的左端点,询问的右端只能在区间的右端点(如果询问端点在区间内部,一定不能保证某个 \(S_l=S_r\),不满足条件)。我们可以方便地将这 \(j\) 个区间缩为 \(j\) 个点。那么 \(g_{i,j}\times f_j\) 表示将 \([1,i]\) 划分为 \(j\) 个尽量长的不可识别段的询问方案数。这里乘上 \(f_j\) 是为了将这 \(j\) 个不可识别段区分,以保证不可识别段尽量长[3]

考虑 \(g\) 数组的转移。我们假设 \([i+1,i+k]\) 是一个新的不可识别段,因为不考虑左右端点,只有 \(k-2\) 个数,那么有 \(2^{\binom{k-1}{2}}\) 种方案。

\[g_{i+k,j+1}\gets g_{i,j}\times2^{\binom{k-1}{2}} \]

特殊地,当 \(i=j\) 时,因为每个不可识别段两端都是相同的,我们认为不存在不可识别的数,那么容易发现这就是答案。

但是因为转移需要用到 \(f_i\) 本身,所以我们考虑计算他的补集,再用 \(2^{\binom{i+1}{2}}\) 减去即可。

有:

\[\sum_{j=1}^{i}g_{i,j}\times f_j=2^{\binom{i+1}{2}} \]

因为 \(g_{i,i}=1\)。

那么就有:

\[f_i=2^{\binom{i+1}{2}}-\sum_{j=1}^{i-1}g_{i,j}\times f_j \]

时间复杂度 \(O(n^3)\)。

当钦定 \(S_a = S_b\) 与 \(S_c=S_d\) 时,也就是不可识别段为 \([a,b]\),\([c,d]\)。但是如果有 \(S_a=S_c\) 时,那么 \([a,d]\) 也可以作为不可识别段。

如果 \([a,d]\) 为不可识别段,那么它也会统计 \([a,b]\),\([c,d]\) 会统计的方案数,就算重了。

所以,当我们将 \([a,b]\),\([c,d]\) 作为不可识别段时,其实就包括一个隐含条件: \(S_a\neq S_c\)。

对于不可识别段 \([a,b]\)。考虑左右端点无非只有一种询问:询问 \([a,b]\)。而这个我们会在下面计算上。

在同一段数下,因为保证了每一个不可识别段尽量长,那么不可确定点对不会算重。举个例子,当 \(n = 6\),分段为 \([1,2,3],[4,5,6],[7,8]\),这里分段表示钦定了 \(S_1=S_3,S_4=S_6,S_7=S_8\),为了保证每一个不可识别段尽量长,那么 \(S_1\neq S_4\);如果我们不将这些不可识别段区分,变成 \(S_1=S_4\) 的话,就有 \(S_1=S_6\),\([1,2,3,4,5,6]\) 就是一个新的尽量长分段,不满足定义。


  1. 为什么要尽量长: ↩︎

  2. 为什么不考虑左右端点: ↩︎

  3. 为什么不是 \(g_{i,j}\times 2^{\binom{j+1}{2}}\): ↩︎

标签:那么,二数,题解,不可,端点,binom,识别,询问
From: https://www.cnblogs.com/znpdco/p/18331118

相关文章

  • P8314 Parkovi 题解
    题意:树,边有边权,求一种选出\(k\)个点染色的方案,使得每个点到最近的一个被染色点的距离的最大值最小,\(n\le2\cdot10^5\).Solution先看部分分:\(n\le20\):直接\(C_n^k\)爆搜.\(k=1\):对每个点\(u\)求出\(f(u)\)和\(g(u)\)分别表示\(u\)到子树内点距离的最大值、\(u\)......
  • luogu P2371 [国家集训队] 墨墨的等式 题解
    luoguP2371[国家集训队]墨墨的等式题目传送门思路同余最短路同余最短路同余最短路与差分约束有异曲同工之妙,都将约束条件转化为边,每种状态转化为点。把本来与图论毫不相干的问题抽象到具体的图上,通过拓扑排序,最短路等基础算法获得最小状态,从而解决问题。在本题中,以\(0\)......
  • vue3中使用keepAlive缓存路由组件不生效的问题解决
    在Vue3中使用keep-alive缓存路由组件时,可能会遇到一些问题导致缓存不生效。以下是一些常见的问题及其解决方案:keep-alive写法错误:在Vue3中,使用keep-alive需要将router-view包裹在keep-alive中,并通过插槽传递组件。例如:<template><router-viewv-slot="{Co......
  • CF1523D Love-Hate 题解
    CF1523DLove-Hate题解传送门题目大意:给定\(m\)和\(n\)个集合,而且这\(n\)个集合的元素都是\(1\)~\(m\)中的数且没有重复,而且大小都不超过\(15\)。求一个最大的集合,使得这个集合是至少\(\left\lceil\frac{n}{2}\right\rceil\)个集合的子集。先想一个问题:题目是让......
  • CF1523E Crypto Lights 题解
    CF1523ECryptoLights题解传送门。题目大意:有\(n\)个台灯,初始时都是暗的,每次随机点亮一个暗台灯,若点亮后存在一个长度为\(k\)的连续段有大于一个台灯被点亮则立刻停止,求期望点亮多少台灯。(就是直接把原题翻译搬过来了)很明显的期望dp,状态定义也很明显,设\(f_i\)表示......
  • P8347 「Wdoi-6」另一侧的月 题解
    P8347「Wdoi-6」另一侧的月题解第一次自己思考出来紫题,题解纪念一下。下面为大家讲解如何一步步推到最终结论:首先,原树没有根,不妨设它的根为\(1\),将它转化成有根的,便于操作。为了方便描述,我们称将一个非根节点的点的父亲删去,保留含这个点的连通块这个操作为截取操作(就是......
  • CF538G Berserk Robot 题解
    Description有一个机器人,第\(0\)秒时在\((0,0)\)位置。机器人会循环执行一个长度为\(l\)的指令序列,每秒执行一个指令。指令有ULDR四种,分别代表向上/左/下/右移动一格。你不知道这个指令序列具体是什么,但是你知道\(n\)条信息,第\(i\)条信息为「第\(t_i\)秒时机器......
  • CF1634F Fibonacci Additions 题解
    CF1634FFibonacciAdditions题解传送门。题目大意:给定两个序列\(A\)和\(B\),每次一个可以选一个区间,并在区间的第\(i\)个数加上\(F_i\),其中\(F\)是斐波那契数列,你需要在每次询问结束时输出两个序列是否相等。可以先求一个序列\(C\)表示\(A\)和\(B\)每个位置的......
  • 剑指Offer题解合集
    剑指Offer题单及题解题目顺序为牛客上剑指Offer专题JZ3、数组中重复的数字分析可以直接对数组进行排序,通过判断首末数字大小来判断数字越界情况,注意数组为空的情况。发现\(0\leqnums[i]\leqn-1\),因此直接开一个数组判断是否有重复数字即可,返回第一个重复数字。代码......
  • 力扣题解2-两数相加
    问题的描述如下:分析过程:为了解决这个问题,我们需要逐位相加两个链表对应位置的值,并处理进位问题。具体步骤如下:初始化一个新的链表,用于存储结果。使用两个指针遍历两个输入链表,逐位相加,同时考虑进位。如果一个链表比另一个短,则将其视为0进行计算。处理最后可能存在的进位......