ZigZagK的博客
[离散+线段树分治+并查集按秩合并]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 | ...
[cdq分治+NTT]洛谷4721【分治 FFT】题解
题目概述给出 $g$ 以及 $f(0)=1$ ,求:$f(i)=\sum_{j=1}^{i}f(i-j)g(j)$ 。解题报告其实我是想学分治+NTT来着的,结果搜分治FFT就搜到这个了,于是填...
[分治+LCT+二分图判定]Codeforces19E【Fairy】题解
题目概述有 $n$ 个点 $m$ 条边,问有多少边删除了之后让原图是二分图。解题报告远古CF题。删除一条边可以考虑分治,然后用LCT判断有没有奇环就行了。这是斯波做法,时间复杂度 $O(nlog...