ZigZagK的博客
[可持久化平衡树]洛谷5055【可持久化文艺平衡树】题解
题目概述Luogu5055解题报告带tag的可持久化平衡树,Pushdown需要在新建的节点上进行,并且Pushdown需要新建两个儿子,以避免影响之前的信息。好像看到了很多Pushdown在原...
[可持久化平衡树]洛谷3835【可持久化平衡树】题解
题目概述Luogu3835解题报告由于非旋Treap的Split和Merge都是自上而下的操作,因此可以很方便的可持久化。未解之谜:Split肯定需要新建节点,但是Merge好像并不需要?洛谷这...
[广义后缀自动机+DP+单调队列]洛谷4022(CTSC2012)【熟悉的文章】题解
题目概述Luogu4022解题报告不难想到二分答案 $mid$ ,然后求 $L\ge mid$ 是否可行。令 $K={\lfloor{len\over 10}\rfloor}$ ,那么舍弃的位置...
[离线+线段树+堆]洛谷4747(CERC2017)【Intrinsic Interval】题解
题目概述Luogu4747解题报告找性质题过于困难……首先很明显,如果两个合法区间有重叠部分,那重叠部分一定也是合法的。更进一步,根据这个性质可以得知答案一定是唯一的,否则两个答案区间的重叠部分...
[生成函数+分治NTT+多项式ln]洛谷4705【玩游戏】题解
题目概述Luogu4705解题报告二项式展开后:$$ {t!\over nm}\sum_{k=0}^{t}{1\over k!}(\sum_{i=1}^{n}a_i^k){1\over(t-k)...
[分数规划+长链剖分+线段树]洛谷4292【[WC2010]重建计划】题解
题目概述洛谷4292解题报告题解里很多点分治,但其实用长链剖分十分的直白。首先先用01分数规划,二分答案 $mid$ ,然后问题转化为边权为 $w-mid$ 的树上选出一条和 $\ge0$ 且长...
[阈值优化+分块]洛谷5309【[Ynoi2011] 初始化】题解
题目概述Luogu5309解题报告题目保证 $y\le x$ ,因此每次都是全局 $i\bmod x=y$ 的 $a_i$ 加上 $z$ 。不难想到 $x>\sqrt n$ 时,我们直接暴...
[线性代数+多项式取模]洛谷4723【常系数齐次线性递推】题解
题目概述给出递推 $f$ 的 $[0,K-1]$ 项,给出系数 $\{a_K\}$ ,$f_n=\sum_{i=1}^{K}a_if_{n-i}(n\ge K)$ ,求第 $n$ 项。$n\le...
[并查集]洛谷6786【GCDs & LCMs】题解
题目概述洛谷6786解题报告假设 $(b_i,b_j)=A,b_i=BA,b_j=CA(C>B)$ ,然后推式子:$$ BA+CA+A={BA\cdot CA\over A}\\ BA+C...
[多项式多点求值]洛谷5050【多项式多点求值】题解
题目概述给出一个多项式 $F(x)$ ,有 $m$ 个询问,每次求 $F(a_i)$ 。解题报告将 $F(x)$ 在 $x=a$ 处进行泰勒展开:$$ F(x)=F(a)+F'(a)(x-a)+...