ZigZagK的博客
[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.询问区间和。解题报...
[去绝对值]HDU6435(2018多校训练赛第十场)【CSGO】题解
题目概述你在play♂CSGO,被第 $i$ 种枪打跪体现你有 $S_i$ 的手残值,并且有 $K$ 个参数 $\{x_{i,K}\}$ ,被第 $j$ 种刀捅挂体现你有 $S_j$ 的手残值,...
[Dsu on tree]HDU6430(2018多校训练赛第十场)【TeaTree】题解
题目概述给出一棵带点权的树,求每个节点 $i$ 的 $max\{(a_x,a_y)|LCA(x,y)=i,x\not=y\}$ 。解题报告因为 $10^5$ 内质因子个数最多只有 $2^7=12...
[DP]HDU6415(2018多校训练赛第九场)【Rikka with Nash Equilibrium】题解
题目概述有 $n\times m$ 的网格,现在要不重复的填入 $1\sim nm$ ,如果一个格子比同行同列的数都大就称这个格子占领了这行这列。求只有一个格子占领一行一列时的方案数。解题报告显...
[莫比乌斯函数+调和级数]HDU6390【GuGuFishtion】题解
题目概述咕咕咕。求 $f(a,b)={\varphi(ab)\over\varphi(a)\varphi(b)},\sum_{a=1}^{n}\sum_{b=1}^{m}f(a,b)$ 。解题报...