Don’t Be a Subsequence
我们维护 $next$ 数组表示在第$i$个字符之后的第一个字符$c$的位置。
这是一种叫做子序列自动机的贪心方法,然后我们就可以靠倒序处理的方式更新,这是因为终态是已知的。
最后输出方案,本题是正序递推,与更新方向相反。
Chase
好题,给出一棵树,求一条路径,选择路上的V个点,
使得被选择的点的 相邻且不在路径上的点 的权值和最大。
如果用 $DP$,一个暴力的思路是每次都枚举树根(起点)做 $DP$,复杂度 $O(n^2v)$,
考虑优化冗余部分,直接转移换根过于困难,我们可以考虑其它方案。
我们发现合法的路径满足一条上一条下的类似自动机的模式,这样可以更快更简单地解决,
换根操作可以在第一次 $dfs$ 时完成,还有就是要先预处理一些数组,这里自己想。
甲虫
区间$DP$,但是水会根据时间变化,不难想到排序消除后效性,
由于扫完区间必在左端点或右端点,所以直接表示,不难发现这样的区间 $DP$ 是从左右端点扩展的。
但是水的变化依旧有后效性,没有这个限制的题目
这是因为当前区间最大时时间不一定是最优的,甚至可能为负,不利于后面的转移。
如果我们去看损耗的最小,就可以直接用转移方程计算而不需要新增时间数组,事实上,如果不能确定两个数组的目标相同,新增数组来转移是很危险的。
又因为水滴到了 $0$,就不会继续减少了,没有这个限制的题目
我们不能直接计算总费用,所以采用费用提前计算的加条件枚举方法,
也就是将当前产生的后效性(这里是时间)直接计算出来,以此消除。
连珠线
我们发现将珠头作为状态,状态数太多,所以将中点作为状态,想想怎么设计状态机。
我们发现折线的形式很特殊,状态数太多,所以用换根将折线变为直线。
换根要统计原儿子失去的贡献和原父亲的贡献,不难想到要存次长。
为了方便的换根,我们可以存一个 $vector$,这里相当有难度,自己想一想。
集合选数
发现没有直接的思路,去看一下不合法的数有什么特点,
显然这张图可以填充成一个矩阵。
要求是直接相邻的数不能都选,这个矩阵的长宽不大,是状压$DP$的板子,我们可以直接计算。
由于一个数没有在之前的矩阵里出现,那它的倍数也不会,所以用乘法原理统计。
值得一提的,矩阵相邻两行的方案并不是独立的,所以要用状压而不是直接乘。
~K Perm Counting
我们先将排列转化为网格问题,
所求的排列个数,就等于在这样的棋盘格子内放 $n$ 个互不攻击的車,且阴影格子不能放的方案数。
这种带限制的计数问题可以用容斥解决,本题多个集合的交集大小只和集合的数目有关。
我们发现它可以这么做
On the Bench
首先,想到要消掉平方因子,其次,多少种排列可以考虑用数学和$DP$求解,
如果用$DP$,就需要分情况讨论,这里不能被局限了,最好从最后一步出发(数学归纳法)。
这里我们虽然可以插入任何位置,但分析后发现这点不用设为状态。
Helping People
值很好算,考虑概率,不难想到操作满足交换律。
再看操作区间不相交的条件,这个条件使得区间之间构成树形的关系,所有操作就是一个森林了。
因此不难想到增加一个操作 $m+1 : l_{m+1}=1,r_{m+1}=n,p_{m+1}=0$ 这样既不会对答案有影响,又让所有区间形成了一棵树。
采用树形$DP$,不难想到我们只有维护变化值即可,时空都得到了优化。
如果越界了,就选一个不用的位置存即可。
求取最大值的期望根据 根区间的所有可能值的概率 计算。
Array GCD
首先发现首或尾必有一个剩下来,且有最多六种情况。
所以为了计算$gcd$,我们分解质因子,然后预处理每个位置上的数不删除情况下想不互质的代价。
由于区间删除可以拆成 未开始,删除,已结束 三个区间,用状态机表示即可。
随机树
好题,先看一个简单题 ,不难发现状态有当前用到了第几个结点和树的深度。
因为是二叉树,所以可以用$for$解决,本题虽然可以用前缀和优化,
但一个更聪明的想法是修改状态为小于等于,详情见这里 ,只有改变一下边界的赋值就可以了,这里可以先思考记忆化该怎么写,再修改为 $for$(如果有用)
还有就是然后枚举点的个数时只需要枚举奇数。
回归本题,第一问是简单的期望$DP$,有$f[i] = f[i-1] + \frac{2}{i}$,
第二问的方法类似简单题,有 $P(X = x) = P(X >= x) - P(X >= x+1)$,
本题$DP$状态是叶节点的数量,所以不能只枚举奇数,具体解法
Ribbons on Tree
不难想到 $n^3$ 的暴力,容斥原理优化 ,或者更准确点,是用 子集反演优化 ,
股票交易
考虑暴力,容易设计状态机,用单调队列优化一下就过了。
划艇
很容易想到将维护具体的值改为维护离散的区间,
然后是普及难度的分类转移方程分析,最后前缀和优化小于等于即可。
Good Contest
要求的是单调递减,每个区间都要选数,所以在不符合要求的区间时直接退出(不能再往前了)。
最后除以总选择数。
Sandy and Nuts
状压$DP$,我们可以限制某个点在子树里时转移,可以避免重复。
缩小社交圈
排序消除后效性,暴力的想法是同时维护大小、左右端点的最值和次值,
更优的想法是不维护大小和左端点的最值次值,而是维护最后一个和次后一个选什么线段的方案数。
代码拍卖会
好题,同时运用了数位和背包的思想,
由于时间复杂度太大,所以用循环节优化即可。
Game Relics
最优解一定是先抽卡,剩下的再全买。
所以先考虑抽卡的期望,期望DP的分享 ,然后处理买的期望,我们发现概率不好计算,
所以用公式 概率 = 方案数 / 总情况数,
因为 概率不等,所以用 概率乘以得分 统计答案即可。