<h1>2019.11.05 模拟赛总结</h1>

<h2>赛时</h2>

开场看了 T1,发现实质上是对完全图求 $n-1$ 完备匹配,求完后就删掉。发现自己只会暴力(其实是构造题想不出来),就去看了 T2
T2 一开始感觉和树堆那个题差不多...?但是发现其实这个性质是不独立的 ,写了写代码发现了不独立之后,就只有链的分了。
由于肝 T2 花费了大量时间,没好好看 T3,写了个大众暴力
最后 30+40+30 = 100,三题暴力光荣省三

<h2>题解</h2>

<h3>A. 小 D 与原题</h3>

一开始肯定都想过 $\frac{n}{2}$ 的构造,大概是将左边的转一圈。
然后我们考虑这种操作,本质上可以看成是一些数旋转后按照某一个中心点做对称,对称的就匹配起来。
如果 $4|n$ ,这显然是对的,但是如果不满足的话,就会出现一个点自己匹配到自己,我们将这个点和最后一个点删除,就变成了 $4|n$ 的子问题,直接构造就可以了。
代码

<h3>B. 小 D 与随机</h3>

感觉是全场最难的题了...每一个 Subtask 都是有启发意义的

<h4>Subtask1</h4>

这里要求 $n \leq 20$。
没有给 $O(n!)$ 的分感觉很不爽,但是也只能这样了。
这里介绍一种 $O(3^n)$ 做法(虽然过不了不过复杂度不带阶乘了)
我们考虑先枚举哪些点是好点,然后我们可以按照点之间的权值大小关系建出一个有向图。我们考虑这个图实际上是一个外向树+一些内向边组成的。如果没有内向边,每个节点成立的概率就是 $\frac{1}{sz}$。(一个来自树堆的结论)。
我们考虑外向树容斥:容斥掉向上的边。这样我们枚举边集,一部分变成向下一部分直接扔掉算一下答案即可。
这种方法实际上是可以导出正解的(把这东西 dp 出来),可是蒟蒻太菜了不会,如果有大佬会可以评论区教我[可怜]

<h4>Subtask2</h4>

这里保证是一条链。
也就是点都独立,直接 $f_i = (\frac{k}{sz}+\frac{sz-1}{sz})f_{i+1}$ 就可以了。

<h4>Subtask3</h4>

也就是正解了...
考虑最终答案一定是形如 $\sum_{i=0}^n x_ik^i$ 的形式。发现直接 dp,我们转移的时候就必须要记录这个状态的好点个数。

我们考虑如何去掉:如果没有这个 $k$ 的话我们可以考虑用 $[\geq k]-[geq k+1] = [=k]$,但是现在有个底数了,我们考虑如何类似的去掉。

考虑某一项 $k^m$ 可以有 $k^m = \sum_{i=0}^m \binom m i (k-1)^i$。

考虑对于后面的每一项 $(k-1)^i$,它都会被算它的超集个数次。考虑原先 dp 直接转移错误在这两个状态合并后的点可能不是一样的(即,你不能快速算出有 k 个好点的个数),但是这样我们相当于将 k 减一之后就可以将 $>k$ 造成的方案变化算在这上面了。
之后的 dp..:
对于每一个方案,它的贡献是它的方案数乘上 $k^{|S|}$。一个经典套路是如果你转移到了使用这个点就全都乘上 $k$。
现在我们可以 dp 了:设$f_{v,i}$ 表示考虑 v 子树,最小的好点的排名是 $i$
为什么…?
因为我们可以看成每次考虑根节点加和不加(就可以考虑出所有情况),根节点如果加入,那么子树内所有好点都要比它大。
然后按照定义转移..
合并:
暴力:枚举原序列最小排名 $p$,新序列最小排名 $q$,我们钦定前者作为新的最小值,那么最小值的取值就是 $[p,p+q-1]$
考虑转移系数:我们让 $k$ 表示合并后的最小值,那么
$$f_{v,k} = \binom {k-1} {p-1} \binom {sz-k} {sz_x-p} f_{v,p} f_{to,q} $$
因为 $f$ 是需要有序的,所以转移时只需要考虑它们之间的相对位置关系,不需要考虑到底选择了哪些数(到根的时候所有点都被考虑了)。
优化:考虑枚举 $p,k$,可行的 $q \geq k-p+1$,可以后缀和优化
但是现在还有个小 bug:我们状态没有考虑转移时子树为空的情况,事实上任意一种情况都可以和这个情况合并,所以后缀和全体加上 $sz[y]!$
最后考虑加入当前的点,在 $f_{v,i}$ 加入时讨论一下:

  1. 通过在 $f_{v,i-1}$ 中作为一个前面的白点得到,转移系数为 $(i-1)$(有 $i-1$ 个空)
  2. 自己作第 $i$ 个黑点,转移系数为 $k$(看成单点和树合并,也需要后缀和)
  3. 考虑空子树的插入:直接是 $k*(sz-1)!$

代码

<h3>C. 小 D 与游戏</h3>

首先特判掉全都相同的情况(答案是 1)和 $len \leq 3$ 的情况(爆搜)
然后考虑 $len \geq 4$ 时,把 abc 看成 012,他们的和 mod3 并没有发生改变。换一句话:我们需要记和为 x 的序列的数量。
可以设 $f_{i,j,k,0/1}$ 表示考虑到第 $i$ 位,和 mod3 为 $j$,这一位是 $k$,前面是否有相同的连续段,按照定义转移即可。
如果一开始两两都不相同要额外特判一下(因为我们这个 dp 只会记录有连续段的情况)
代码

<h2>总结</h2>

  1. 自己太菜了,还要努力
  2. T1 这种构造题没切掉,太菜了
  3. T2 应该第一时间意识到不独立去搞别的题的。。。事实证明我尝试搞出最难的题,但是没啥用,那个让 $k$ 转化为 $k-1$ 然后求联通块贡献的方法挺强的,并且组合计数的时候也要找对到底要记什么,dp 的时候也要考虑加入新点/合并的时候的判断依据,不要记录无用状态/漏记有用状态
  4. T3 这种题目感觉不是很难...但就是不能抓题目性质,如果能证明一种序列和一种性质充要的话,通常我们会考虑将这个性质放在状态里进行 dp
  5. CSP2019.rp++

<h3>附:关于 T2 一类容斥的理解</h3>

一般情况下,我们是限制了 $[x=k]$ ,有时候我们只能快速求 $[x \geq k]$ 的方案数,那么我们就可以减一下就的出来正确的结果了。
所以当我们注意到最终答案一定是形如 $\sum_{i=0}^n x_ik^i$ 的时候($x_i$ 表示恰好 $i$ 个好点的方案数),展开可以得到 $\sum_{i=0}^n x_i \sum_{j=0}^i \binom i j (k-1)^j$ ,整理一下:
$$\sum_{i=0}^n (k-1)^i \sum_{j=i}^n x_j \binom j i$$
还是枚举了大于其的所有子集,那么考虑对这个进行 dp:我们合并的时候 考虑状态中 $(k-1)^i$ 前面的系数,其实是可以任意去合并的,不需要考虑个数(因为即使合并后会产生新点,这也会作为超集方案被算进去)
好难啊...
所以以后看到 $k^m$ 就可以直接枚举每种集合 求超集个数 乘 $(k-1)^m$ 了

Last modification:April 7th, 2020 at 10:14 pm
如果觉得我的文章对你有用,请随意赞赏