wjyppm's Blog

带限制的期望我们一般喜欢用 DP 来解决，因为这样能够更好的处理相邻之间的限制。其实一般说来好多期望都是通过 DP 来解决，而一小部分是直接能够算出概率求得。 观察题目总共 444 个限制，同时还有大小王的灵活使用。不难有状态 f(a,b,c,d,e,f)f(a,b,c,d,e,f)f(a,b,c,d,e,f)，表示用了 aaa 个黑桃，bbb 个红桃，ccc 个梅花，ddd 个方块，小王状态 eee，大王状态 fff。其中大小王状态格式为：000 为未使用，1→31\rightarrow 31→3 为当作黑桃，红桃，梅花，方块。 不妨设已经用过的牌数量为 sumsumsum，显然 sum=a+b+c+d+[e≠0]+[f≠0]sum=a+b+c+d+[e\neq 0]+[f \neq 0]sum=a+b+c+d+[e=0]+[f=0]。对于一个状态合法，即满足 a,b,c,d≤13,sum≤54a,b,c,d\le 13,sum \le 54a,b,c,d≤13,sum≤54。考虑转移方程，有如下情况： 黑桃：抽中的概率为 13−a54−sum\dfrac{13-a}{5...

可能更洛谷的阅读体验 很好的题，能够很好的练习枚举最大值转移 DP。 我们一步一步来，顺着 subtask 来走： 有一个显然的想法，就是暴力选取开会的位置，直接做即可，复杂度 O(n2q)O(n^2 q)O(n2q)。 考虑 sub 2 如何做，首先注意到询问的是一个区间的答案，我们可以暴力预处理出来，但时间复杂度要在 O(n2)O(n^2)O(n2) 以内，怎么做？注意到我们实际上不用暴力枚举，我们只需要一个区间的最大值出现在哪里，这个最大值将会贡献答案，让后枚举把会议丢在该位置左边还是右边即可。 具体来说，我们设 f(l,r)f(l,r)f(l,r) 表示在 [l,r][l,r][l,r] 的位置区间选会议的最小代价，转移是显然的： f(l,r)=min⁡{f(l,p−1)+(r−p+1)×ap,f(p+1,r)+(p−l+1)×ap}f(l,r)=\min\left\{f(l,p-1)+(r-p+1) \times a_p,f(p+1,r)+(p-l+1) \times a_{p} \right\} f(l,r)=min{f(l,p−1)+(r−p+1)×ap​,f(p+...

好题，话说我写黑题题解是不是有点飘了 www。 众所周知，第二类斯特林数有一个如下的性质： mn=∑i=0n{ni}×i!×(mi)m^n=\sum\limits_{i=0}^n \begin{Bmatrix} n \\ i \end{Bmatrix}\times i! \times \binom{m}{i} mn=i=0∑n​{ni​}×i!×(im​) 更众所周知的是，杨辉三角递推式： (nm)=(n−1m)+(n−1m−1)\binom{n}{m}=\binom{n-1}{m}+\binom{n-1}{m-1} (mn​)=(mn−1​)+(m−1n−1​) 原题的答案求的是： ansx=∑i=1n(dis(x,i))kans_{x}=\sum\limits_{i=1}^n (dis(x,i))^k ansx​=i=1∑n​(dis(x,i))k 其中 ansxans_xansx​ 表示在以 xxx 为根节点的情况下的答案，注意到选取的 xxx 不同所对应的答案不同，这启示我们进行类似于换根 DP 的计算（是不是有点太超前了）。 我们利用上面的公式变换一下： ansx=∑i...

可能更洛谷的体验 有一个 O(n3)O(n^3)O(n3) 的 DP 是很显然的，就是设 f(i,j,k,0/1)f(i,j,k,0/1)f(i,j,k,0/1) 表示第 iii 只怪兽，用了 jjj 的体力，用了 kkk 的魔力，当前打怪兽用不用魔力的最大打怪兽数量，这显然不能通过。 我们考虑什么状态中信息是有用的。首先，既然我们是一个一个按顺序打的怪物，遇到每一个怪兽我们肯定都要打。那么实际上我们根本就不用存储打怪兽的数量，只需要存储当前魔力或体力的信息，通过这个我们来判断是否到现在能够打怪兽。 那么，我们只需要把体力或魔力任一维度丢到我们 DP 求解的答案即可，因为这里我们有一个是否使用魔力的状态决策，我们考虑把魔力丢进去。 设 f(i,j,0/1)f(i,j,0/1)f(i,j,0/1) 表示第 iii 只怪兽，用了 jjj 的体力，当前打怪兽用不用魔力的最小魔力使用。转移方程是显然的： f(i,j,0)=min⁡{f(i−1,j+ai,0),f(i−1,j+ai,1)}f(i,j,1)=min⁡{f(i−1,j,0),f(i−1,j,1)}+bi\begin{align...

可能更洛谷的阅读体验 好题，写一篇题解记录一下。 首先考虑计数 DP，但是直接做发现不太好做，我们思考能否对删除操作进行进一步转化成好的条件取做。 对于原题目的限制，即只要一个数左右两侧一旦有一个大的就会被删，既有位置限制和数值限制。一步很妙的转化的就是将这个思想转成笛卡尔树，那么删除操作就是在笛卡尔树上删有儿子的点。 我们不妨设 gug_{u}gu​ 表示删空 uuu 子树（包括 uuu 号点）的所需次数，因为题意表明删除操作是同时进行的，不难有如下转移： gu=max⁡{gls,grs,min⁡(gls,grs)+1}g_{u}=\max\left\{ g_{\text{ls}},g_{\text{rs}},\min(g_{\text{ls}},g_{\text{rs}})+1 \right\} gu​=max{gls​,grs​,min(gls​,grs​)+1} 其中 ls 表示左儿子，rs 表示右儿子，注意在没有左儿子和右儿子的时候要特判。 方程表明如下情况： gls,grsg_{\text{ls}},g_{\text{rs}}gls​,grs​：因为操作是并行的，我...

推销自己的矩阵优化文章：矩阵快速幂优化DP 注意到点数及其小，边数也算小，而 LLL 极大，有一股浓烈的矩阵快速幂优化的味道。 首先这个问题肯定是一个 DP 的题，我们有一个暴力的想法，我们对于每一个操作，利用 Floyd 的 DP 思想，邻接矩表示图两点之间经过 111 条边的路径数量这个特点，对于每一个操作我们更新邻接矩阵，让后在上面跑矩阵快速幂，幂 LLL 次后的邻接矩阵代表的就是经过 LLL 条边的信息，一次次更新答案判断可达性即可，时间复杂度 O(Tn3log⁡L)O(T n^3 \log L)O(Tn3logL)，不能通过。 我们考虑如何优化，根据题意，每一次操作只会添加一条边，而要求的是求经过边中操作编号更靠后（也就是更大）的边。我们可以将这个操作编号绑到边权上，那么实际上我们就是要对经过的边的边权取 max⁡\maxmax 操作。 那么我们有一个显而易见的状态，设 f(i,j,k)f(i,j,k)f(i,j,k) 表示在从 iii 到 jjj 节点，经过 kkk 条边的最大边权，转移如下： f(i,j,k)=min⁡{max⁡p=1nf(i,p,k−1)+w(p...

可能更洛谷的阅读体验 前言 2025.6.11 UPD：更新了枚举最大值转移 DP，删除了杂项，大幅重写文章。 2025.11.11 UPD：由于 CSPS 考试，文章重构，加入更多的例题，新添加了多个方法。使用了较为严谨化的术语。 对于排列计数 DP，我们侧重研究的是在排列未知的情况下如何计数。 大家显然都是会指数级枚举排列来进行操作，但难点并非对于排列的枚举，而是在于找到一种合适的生成顺序。通过这种顺序，满足题目的限制，将已经生成的部分压缩成少量的关键量，从而把原本指数级的状态降到可解的多项式维度。 本文章将尝试整理和总结我在学习排列计数 DP 时的一些思路和方法。坦白地说，我对这一类问题的理解还不算完全透彻，很多细节可能只有在做了大量例题之后才能真正掌握。所以这里的内容更多是一个学习记录和思路整理，而非什么可以写进 Wiki 的内容。 不过，我写这篇文章希望能够提供一个大概的解题方法，让读者可以在遇见一些计数题目中可以有大致的参考做题方向和状态设计。 基本生成顺序 参考 YeahPotato 博客的分类，基本生成顺序分类如下： 绝对数值（预定） 相对数值（...

0. 前言 本文章还是不太完善的，这篇文章也只是我个人的一个经验总结，希望能帮助到后人学习。 1.矩阵小芝士 矩阵优化是干啥的啊？ 有的时候，你会发现你设计了一个极好的 DP 状态，没有后效性，没有重叠，你很开心，你去看数据范围就会炸掉！你死活都想不出来怎么优化，感觉去掉这个状态之后就感觉 “不完美” 了，让后点开题解，发现一堆密密麻麻的数学公式和矩阵，开心的点进去，郁闷的叉掉，那么怎么解决这种郁闷心情呢？当然就是学矩阵优化啦 好端端的那么优美的递推式子我们为什么要用矩阵来转移呢？答案很简单，因为矩阵乘法有结合律，可以快速幂！当转移式子固定的时候，我们可以通过快速幂，设置好初始矩阵和转移矩阵，通过矩阵快速幂就能轻轻松松的将复杂度变成 log⁡\loglog，是不是很好？（怎么可能？） 我们介绍一下矩阵乘法： 设 A=(ai,j)m×n,B=(bi,j)n×sA=(a_{i,j})_{m\times n},B=(b_{i,j})_{n\times s}A=(ai,j​)m×n​,B=(bi,j​)n×s​，定义 C=A×B=(ci,j)m×sC=A\times B=(c_{i,...

0. 前言 你需要知道——分治。 对于我们介绍的CDQ分治和整体二分，他们都属于离线分治算法的一类。 1. CDQ 分治 1.1 分治的经典应用 分治一个经典应用就是归并排序，我们可以参考它的运行过程。 回忆一下归并排序的步骤？ 把数组分成 [l,mid],[mid+1,r][l,mid],[mid+1,r][l,mid],[mid+1,r] 两个区间。 对左区间和右区间进行归并排序。 把左区间和有区间合并为一个有序数组。 这里引用GTWZeus大佬的文章的图： ok回忆完了分治的结构，记住这个图的结构，我们来看 CDQ 分治。 1.2 基于时间的分治算法 CDQ 分治不是一个模板，它是一个思想。 大多数数据结构问题都可以抽象为：“维护一堆数据，对一系列操作依次作出响应” 的形式。而这些操作一般分为所谓的 “查询” 操作或者 “更新” 操作。 而查询操作和更新操作也是有问题类型划分的。如果所有查询操作都在更新操作之后，那么这个问题就是一个静态问题。反之则为动态问题。 ——蓝书（非原文） 一般来说我们在做数据结构遇到的到多数都是动态问题，我们要想出来一个维护方法很...

0. 前言 你需要知道树状数组 1. 树状数组二分 1.1 概念 类似于线段树二分，树状数组当然也可以二分。 它解决的是如下一类问题： 对于序列 aaa，存在分割点 qqq 使得 ≤q\le q≤q 的位置满足某个限制而 >q>q>q 的位置不满足限制，求 qqq。 （注意是整个序列 aaa 找分割点），要求 O(nlog⁡n)O(n\log n)O(nlogn)。 nnn 类似于长度。 如果你是从某个位置开始二分，那这个就做不到，你可以考虑转化到整个序列二分。 考虑最后一个前缀和 ≤v\le v≤v 的位置，满足序列每个元素非负，则存在分割点 qqq 满足 ≤q\le q≤q 的位置的前缀和 ≤v\le v≤v ，而 >q>q>q 的位置的前缀和 >v>v>v ，那么 qqq 即为所求。 我们初始化两个变量，当前位置 ppp 和对应的前缀和 sss，初始权为 0。 我们从大到小枚举 1≤2k≤n1\le 2^k \le n1≤2k≤n，尝试将 ppp 加上 2k2^k2k。检查 s+∑i=p+1p+2kai≤vs...