ZigZagK的博客
[BFS]HHHOJ208【圈地游戏】题解
解题报告题目里已经告诉我们怎么判断宝藏和陷阱是否被圈起来了……由于只和奇偶性有关,所以可以状压:$f_{x,y,A,B}$ 表示目前在 $(x,y)$ ,宝藏的状态是 $A$ ,陷阱的状态是 $...
[凸包]HHHOJ222【简单题】题解
解题报告我不会“简单题”.jpg。可以考虑从 $(a,b)$ 到 $(c,d)$ 的两种走法:先上再右 $A_a(c-a)+B_d(d-b)$ 以及先右再上 $B_b(d-b)+A_c(c-a)...
[斯坦纳树+随机]HHHOJ200【稗田的梦中之梦】题解
解题报告题目里要我们找出的实际上是一个满足条件的连通块,又因为数据范围这么小,所以想到斯坦纳树来做这种连通块最小值问题。令 $f_{i,j,s}$ 表示 $i,j$ 这个点与 $s$ 这些颜色连...
[霍尔定理+主席树+复杂度分析+DP]HHHOJ197【古明地】题解
解题报告题解里有个很厉害的 $O((n+s)log_2n)​$ 做法,但是我不会……我只会这种比较好想的做法。首先这明显是一个二分图完全匹配问题,我们可以把每项工作 $K_i$ 看成 $K_i$...
[思维]HHHOJ189【Garrafeira】题解
解题报告陈老师的题解和没讲一样……考虑每一个二进制位的贡献,发现只要存在 $a_i$ 有 $j$ 这个二进制位,这个二进制位就有 $2^{n-1}2^{j}$ 的贡献,因为可以通过 $a_i$ ...
[二维偏序+三维偏序]HHHOJ183【Drinks】题解
解题报告很明显至多选 $3$ 个就能构成一种方案,所以我们只需要考虑选 $1,2,3$ 个的情况就行了。考虑不合法的情况,即物品之间有包含的情况,如:1 1 1 | 3 2 2 2 2 2 | ...
[除法分块+杜教筛]HHHOJ173【B】题解
解题报告重新看一遍发现这题十分斯波……我们要求的是:$$ \sum_{\{a_k\}}e[(a_1,a_2,\cdots,a_k)]\\ \sum_{\{a_k\}}\sum_{d|(a_1,a...
[点分治]HHHOJ174【C】题解
解题报告摆明了要你点分治……每次统计 $x$ 子树的时候记录两个值:到 $x$ 路径最大值和到 $x$ 路径点权和。按照最大值排序之后,枚举 $i$ ,只要看前面有多少 $dis_j\equiv...
[IDDFS]HHHOJ110【布加勒斯特的人偶师/Bucureşti】题解
解题报告考虑决策树,每次枚举操作,根据返回的结果把符合当前状态的排列分成三份(当然如果符合当前状态的只有 $1$ 个排列就不需要继续分了),我们要做的是把决策树的深度弄小。没错这就是个IDDFS...
[多项式+牛顿二项式定理]HHHOJ108【爱丽丝/Alice】题解
解题报告题目中显然给出了一个卷积形式,所以我们移下项,凑凑常数,得到:$$ {A(x)-A_0\over x}-A_1=A(x)A(x)-A_0^2\\ A(x)-A_0-A_1x=xA^2(x...