ZigZagK的博客
[生成函数+记忆化搜索]HDU7057【Buying Snacks】题解
题目概述HDU7057解题报告首先这道题很显然可以用生成函数做,但是 $n$​ 太大了,因此需要考虑类似矩阵快速幂或者分治的办法。定义 $F_i$​​ 表示花费 $i$​​ 时的生成函数,那么不...
[期望DP+分治FWT]2021牛客暑期多校训练营6 D【Gambling Monster】题解
题目概述Gambling Monster解题报告显然是个期望DP,倒着考虑正常一点(因为在 $n-1$ 处结束,步数为 $0$ ),所以我们倒着DP。定义 $f(i)$​ 表示 $i$​ 走到 ...
[离散+线段树分治+并查集按秩合并]2020 ICPC 小米 网络选拔赛热身赛 E【Explorer】题解
题目概述有 $m$ 条边,每条双向边 $(x_i,y_i)$ 只有人数在 $[l_i,r_i]$ 时才能通过,如果人数 $x$ 能够从 $1$ 到 $n$ 则可行,求可行的 $x$ 的数量。解题...
[容斥+生成函数+分治NTT]ACL Beginner Contest F【Heights and Pairs】题解
题目概述ACL Beginner Contest F解题报告直接求不太可做,我们考虑容斥,用总方案数减去至少一组相同的方案数加上至少两组相同的方案数……$2n$ 个元素两两组合的方案数为 $f_...
[斜率优化+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...
数据结构水题选讲(By AwD)部分题解
课件链接Problem A考虑莫队之后在移动指针时怎么维护第 $K$ 大值。带 $log$ 大概会GG。由于答案在 $[1,n+K]$ 范围内,所以可以把值域也分块,这样移动指针就不需要带 $l...
[分治NTT+拆系数FFT+复杂度分析]BZOJ5398【admirable】题解
题目概述有 $n$ 个点的树,现在要覆盖 $K$ 条简单路径,需要满足每条边只能被覆盖 $0,1,K$ 次,求方案数。解题报告这题有毒,CF原题模数是 $998244353$ ,这里强行改成了 ...
[指数型生成函数+分治NTT+广义容斥]LOJ6503(雅礼集训 2018 Day4)【Magic】题解
题目概述有 $n​$ 种颜色的膜法卡,每种颜色有 $a_i​$ 种,总共有 $m​$ 张。现在要把所有卡片排成一排,如果相邻两个卡片颜色相同则产生一个膜法对,求膜法对个数为 $k​$ 的排列个数...
[二维偏序+三维偏序]HHHOJ183【Drinks】题解
解题报告很明显至多选 $3$ 个就能构成一种方案,所以我们只需要考虑选 $1,2,3$ 个的情况就行了。考虑不合法的情况,即物品之间有包含的情况,如:1 1 1 | 3 2 2 2 2 2 | ...