ZigZagK的博客
[斜率优化+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好像是丽洁姐取的名字……是这样的...
[插头DP]HDU1693【Eat the Trees】题解
题目概述给出 $n\times m$ 的网格图,其中有些格子是障碍,求有多少种方法用若干个哈密顿回路覆盖没有障碍的格子。解题报告万年神坑插头DP,插头DP可以解决棋盘上的一些连通性问题(比如这题...
[三元环计数]HDU6184【Counting Stars】题解
题目概述给出一张无向图,求 $4$ 个点构成两个有公共边的三元环的方案数。解题报告填坑填坑,如果我们知道每条边所在的三元环个数 $num_i$ ,那么 $\sum_{i=1}^{m}{num_i...
[思维]HDU4473【Exam】题解
题目概述令 $f(x)=\sum_{a=1}^{+\infty}\sum_{b=1}^{+\infty}[ab|x]$ ,求 $\sum_{i=1}^{n}f(i)$ 。解题报告emm……其实就...
[BFS序+线段树]HDU5957【Query on a graph】题解
题目概述给一棵基环树,有两种操作:1.将到 $x$ 的距离 $\le K$ 的点权值均加上 $d$ 。2.询问到 $x$ 距离 $\le K$ 的点的权值和。解题报告emm……DFS序做多了都忘...
[线段树+复杂度分析]HDU5634【Rikka with Phi】题解
题目概述有一个序列 $\{a_n\}$ ,现在有三种操作:1.令 $i\in[L,R],a_i=\varphi(a_i)$ 。2.令 $i\in[L,R],a_i=x$ 。3.询问区间和。解题报...