ZigZagK的博客
[生成函数+记忆化搜索]HDU7057【Buying Snacks】题解
题目概述HDU7057解题报告首先这道题很显然可以用生成函数做,但是 $n$​ 太大了,因此需要考虑类似矩阵快速幂或者分治的办法。定义 $F_i$​​ 表示花费 $i$​​ 时的生成函数,那么不...
[差分+二分+主席树]2021牛客暑期多校训练营7 K【xay loves sequence】题解
题目概述xay loves sequence解题报告先对数组差分,令 $c_i=a_i-a_{i-1}$ 。每次区间加或者区间减就是对 $c$ 的两个位置 $+1$ 和 $-1$ ,所以不难发现...
[线段树+复杂度分析+差分+树状数组]2021牛客暑期多校训练营7 B【xay loves monotonicity】题解
题目概述xay loves monotonicity解题报告首先我们很自然联想到楼房重建那道题,定义 $Find(p,l,r,i)$​​​ 表示在 $[l,r]$​​​ 的节点 $p$​​​ 前...
[期望DP+分治FWT]2021牛客暑期多校训练营6 D【Gambling Monster】题解
题目概述Gambling Monster解题报告显然是个期望DP,倒着考虑正常一点(因为在 $n-1$ 处结束,步数为 $0$ ),所以我们倒着DP。定义 $f(i)$​ 表示 $i$​ 走到 ...
[矩阵维护DP+树链剖分+不重叠ST表]2021牛客暑期多校训练营6 K【Starch Cat】题解
题目概述Starch Cat解题报告正解是猫树,但是我不会,所以我选择黑科技。首先我们能想到一个比较暴力的做法,每次询问 $x,y$ 路径上的最大独立集,就是求 $x\to LCA(x,y),y...