ZigZagK的博客
[生成函数+记忆化搜索]HDU7057【Buying Snacks】题解
题目概述HDU7057解题报告首先这道题很显然可以用生成函数做,但是 $n$​ 太大了,因此需要考虑类似矩阵快速幂或者分治的办法。定义 $F_i$​​ 表示花费 $i$​​ 时的生成函数,那么不...
[斜率优化+cdq分治]HDU3842【Machine Works】题解
题目概述HDU3842解题报告先按 $D$ 排个序,然后不难想到DP(注意,根据题目要求 $f_j$ 必须 $\ge 0$ ):$$ f_i=\max\{f_j+(D_i-D_j-1)G_j+R...
[cdq分治+动态凸包]HDU5127【Dogs' Candies】题解
题目概述HDU5127解题报告我们分析在甜度热爱为 $x$ ,酸度热爱为 $y(y>0)$ 时,$A(p_1,q_1),B(p_2,q_2)(p_1<p_2)$ 中 $A$ 比 $B...
[二分+后缀数组]HDU2328【Corporate Identity】题解
题目概述HDU2328解题报告首先将所有串中间隔开接起来(注意中间隔开的字符不能相同)。二分枚举答案 $len$ ,然后根据 $Height$ 数组分块,每个块中检查是否 $n$ 个字符串都出现...
[后缀数组]HDU3518【Boring counting】题解
题目概述HDU3518解题报告枚举子串的长度 $len$ ,然后将后缀数组按照 $Height\ge len$ 分块,每个块中检查最左和最右的子串是否交叉就行了。示例程序#include<...
[DP套DP]HDU4899【Hero meet devil】题解
题目概述给出长度为 $m$ 的基因串 $S$ ,对于每个 $i$ 求有多少个长度为 $n$ 的基因串 $T$ 使得 $LCS(S,T)=i$ 。解题报告DP套DP好像是丽洁姐取的名字……是这样的...