Helloworldwuyuze's Blog

01-Trie 进阶介绍$01-Trie$ 是一类解决有关异或问题的工具。它支持插入、删除、全局 $+1$、求异或和、求最大异或值的问题。 异或和 $01-Trie$插入，删除操作首先我们明确 $01-Trie$ 的基本形态。它类似于一个动态开点线段树。每个节点有两个儿子 $t_{p,0}$ 和 $t_{p,1}$ 分别表示下一位是 $0/1$ 的编号是多少。这里我们的 $Trie$ 树维护的二进制串是从最低位开始的。而我们需要维护三个信息： $t_{p,0/1}$，表示下一位是 $0/1$ 时的儿子编号是多少。这与普通的 $Trie$ 相同。 $w_p$，表示最后落在 $p$ 子树内的数有多少个。也可以理解为经过 $(p,fa_p)$ 这条边的数的数量。 $sum_p$，表示 $p$ 子树内的异或和。注意这里以 $p$ 为根节点就不需要考虑 $p$ 以上的部分，也就是原来 $11010$ 的东西现在可能是 $01011,1011,011,11$ 或者 $1$。 对于最终的异或和的答案，我们只关心在某一条 $1$ 边，它的 $w$ 是多少。因为只有权值 ...

整体二分一时间竟然不知道怎么切入，我们不妨按照 $\text{OI-Wiki}$ 的思路引入罢。 静态全局第 $k$ 小Ques 1 询问一次全局第 $k$ 小。 这样的解法是简单的。我们可以直接排序然后访问数组第 $k$ 个位置。也可以考虑二分，但二分要求我们快速知道 $\le x$ 的数有多少个，于是我们就可以使用树状数组（离散化）或者线段树（离散化或动态开点）维护即可。 注意，我们这里称 $kth$ 的算法为 二分，这是因为我们二分 $kth$ 是多少，然后再根据 $\sum\limits_{i=1}^n[a_i\le mid]$ 来判断是 $l=mid$ 还是 $r=mid$。因此，区间 $kth$ 的本质是一种二分。 Ques 2 询问多次全局第 $k$ 小（ $k$ 不同）。 显然，我们仍然可以排个序然后按顺序访问不同的 $k$，但同样，我们可以使用二分的方法。 考虑到二分答案的本质是把一个问题的答案不断缩小直至可以确定。而对于多个问题，这显然也不是问题。我们可以将这许多次询问放在一起，然后统一枚举一个 $mid$ 作为答案，然后根据 $\ ...

Summer Camping Day 5 Sol A.sharkDes给定两个序列 $a$ 与 $b$，其中可以对 $a$ 序列进行操作 $a_i\leftrightarrow a_j(i\not = j)$，使得最小化： $$\sum_{i=1}^n (a_i-b_i)^2$$ 求这个最小化的值和在保证这个值最小化的情况下的最小操作次数。保证 $\forall i, j$ 有 $a_i \not = a_j$ 且 $b_i\not = b_j$。 Sol我们不妨考虑对于一对 $(i,j)$。不妨设：$$\begin{cases}a_i< a_j\b_i<b_j\end{cases}$$那么，有：$$\begin{aligned}(a_i-b_i)^2+(a_j-b_j)^2&=a_i^2+a_j^2+b_i^2+b_j^2-2a_ib_i-2a_jb_j\&\le a_i^2+a_j^2+b_i^2+b_j^2-2a_ib_j-2a_jb_i\&=(a_i-b_j)^2+(a_j-b_i ...

Beakjoon19523Des给定一个 $h\times w$ 的矩阵，初始你处在 $(0,0)$ 的地方，每次你可以进行两个操作： $(x,y)\to ((x+1)\bmod h,y)$ $(x,y)\to (x,(y+1)\bmod w)$ 现在需要你求出对于每个点分配一个方向，求出其中有多少种是可以从 $(0,0)$ 经过所有的点恰好一次走回 $(0,0)$。 Sol于是，我们现在考虑，如果某个点 $(x,y)$ 确定了一定往下走，那么是不是对于点 $(x+1, y-1)$ 和 $(x-1, y+1)$ 也都确定了是往下走的。这是因为我们知道 $(x,y)\to (x,y+1)$，那么 $(x+1,y)$ 就只能通过 $(x+1,y-1)$ 走到。 继续把这个推广下去，我们会发现，对于任意的 $(x,y)$，只要与它处于一条对角线上，都会和它方向相同。而这里，对角线的概念有所不同，这里我们定义只要满足： $$\begin{cases}x+d\equiv x\pmod{h}\y-d\equiv y\pmod w\end{cases}$$ 这就等价于： $$\begin{cas ...

莫队 ——优雅的暴力 基本思想对于区间操作问题，如果我们并 不需要在线（重点！），并且我们可以快速地完成下面四个区间转换操作： $$(l,r)\to (l+1,r)$$ $$(l,r)\to (l, r+1)$$ $$(l,r)\to (l-1, r)$$ $$(l,r)\to (l,r-1)$$ 那么我们就可以通过对处理区间的顺序进行重新排列，那么我们就可以在 $O(n\sqrt n)$ 的复杂度内完成全部区间操作。 算法描述对于一些询问区间 $[l_i, r_i]$，加入我们把这些询问看成平面直角坐标系上的点，$l_i$ 对应横坐标，$r_i$ 对应纵坐标，那么我们可以画出一张图： 然后我们按照横坐标分块，取块长为 $B$： 在每个块内，按照纵坐标排序。显然，我们要转移的步数就是两点之间的曼哈顿距离。于是我们可以画出转移的路径： 乍一看感觉我们需要更新的路径非常长，但是我们仔细分析就会发现复杂度极其正确。 首先，对于块内，横坐标的移动距离一次一定不超过块长，也就是说移动一次横坐标一定是 $O(B)$ 的复杂度。而对于纵坐标，因为我们已经从小到大排序了，因此在一个块内走的复 ...

动态规划 动态规划有两个要点，就是状态和转移。 状态，很重要的一个点是它能够清晰地描述一个子问题。也就是说我们能够根据我们记录下来的东西能够方便得让我们知道我们在解决什么，要求什么，并且能够通过之前的状态转移过来。在满足这些条件的情况下，我们就可以进一步考虑我们到底需不需要记录这么多状态，是不是可以少记录一些来降低复杂度。 转移，就是状态与状态之间的关系。我们需要从一些已知的状态求出一个未知的状态，这个过程就叫转移。转移的快慢很大一部分取决于转移的技巧。例如通过寻找最优决策点的时候有斜率优化、单调队列优化或者四边形不等式优化。有时候，并不是所有的状态都可以通过已知的状态转移过来，很多时候状态是一种类似于方程的形式，这时候就可以使用高斯消元来解决问题，只是复杂度会上升为三次。 背包相信背包一定是大部分 $\text{OIer}$ 最早接触的一类动态规划问题，但我发现我到最近才对它进行系统的学习，实在是太弱了。它的核心问题是有限制条件的选择物品。而 物品 这个概念也可以被抽象化，一般地，一个或一些物品可以看成一个 价值 对于 重量 的函数 $v = f(w)$。但，物品也可 ...

容斥原理 引入首先，我们来看集合只有两个的情况。如果有集合 $A,B$，求 $|A\cup B|$，那么我们可以先将两个集合里面的元素数量加起来，然后再减去两个集合都有的元素，也就是 $|A\cup B| = |A|+|B|-|A\cap B|$。 然后，再看有三个的情况。对于集合 $A,B,C$，如果我们要求 $|A\cup B\cup C|$，那么显然就是三个集合内的元素个数加起来，再分别减去相交的，然后再加回来三个都相交的。即 $|A\cup B\cup C| = (|A|+|B|+|C|) - (|A\cap B| + |B\cap C| + |C\cap A|) + |A\cap B\cap C|$。 于是，我们不妨猜测结论有 $n$ 个集合 $S_i(i\in [1,n])$，则： $$\left |\bigcup_{i=1}^n S_i\right | = \sum_{i=1}^n(-1)^{i-1}\sum_{a_j\le a_{j-1}}\left |\bigcap_{j=1}^i S_{a_i} \rig ...

杂题P5021 [NOIP2018 提高组] 赛道修建Des给定一棵树，有边权，要求找一些简单路径，使得路径上的边无交，并且最大化最小路径长度。 Sol看到题面直接想二分，显然答案也满足单调性。这里二分答案，问题转换为判断某个权值可不可行。 考虑如何判断。首先考虑菊花的情况，显然，任意两条边可以连成一条路径，当然，一条边也可以独自成为一条路径。 我们设现在要判断的值是 $lim$，于是把所有边权大于 $lim$ 的拿出来单独做一条路径，然后剩下的 从小的开始 看能不能找到一条边使得能凑出一条大于 $lim$ 的路径。这个过程可以二分完成。复杂度 $n\log v\log n$。 然后考虑不是菊花图的情况。因为路径不重，因此每个儿子只会传递上来一条路径，这就又变成了菊花图的情况。因此，我们首先找到儿子传递上来的边权大于等于 $lim$ 的所有边加上贡献，然后删除。对于小于 $lim$ 的情况，也是 从小的开始 尝试配对。最后，如果还有剩余没有配对的，就直接选一个最大的当做传递到父亲的边即可。复杂度 $O(n\log n\log v)$。 这里有一些坑 因为从小的开始，因此 **不能够匹配 ...

二项式反演前置：组合数学基础插板法还是由一个例题引入。解不定方程 $\sum x_i = m$ 中正整数解的个数。 这就可以看成我们一共有 $m$ 个小球，然后分成 $n$ 组，其中每组不能为空。那这就相当于在 $m$ 个小球组成的 $m-1$ 个空隙中随意插板，这样就一共有 $\binom{m-1}{n-1}$ 种情况。 现在，如果 正整数 变为 非负整数，又该怎么办呢？ 我们发现，如果提前先给每个人分到 $1$ 个小球，问题就又变成了正常的正整数问题了。这样小球会多出来 $n$ 个，于是这问题就是 $n+m$ 个小球中插入 $n$ 块板，答案就是 $\binom{n+m-1}{n-1}$。 现在，我们又要求所有的 $x_i$ 有一个限制条件是 $x_i\ge b_i$，那么如何做呢？ 显然，我们先给每个人分 $b_i$ 个球，然后就变成了第二个问题，于是答案就是 $\displaystyle\binom{m-\sum b_i+n-1}{n-1}$。 多重集组合数如果有集合 $S = {n_1\times a_1, n_2\times a_2,\dots,n_ ...

CF615D题解题意以给定质因子的形式给定一个数 $n$，并给出具体的质因子，求： $$\prod_{d\mid n}d$$ Solution我们唯一分解 $n$，使得 $n=\prod p_i^{\alpha_i}$，我们考虑对于每一个素数 $p_i$，它在质因子中可能以 $p_i^k(0\le k\le \alpha_i)$ 的形式出现，即一共 $\frac{\alpha_i\times(\alpha_i+1)}{2}$ 次。并且对于每个幂 $k$，都会在别的质因子取任何值的时候出现，即对于一个 $p_i^k$，它会出现 $\frac{\prod_j(\alpha_j+1)}{\alpha_i+1}$ 次，因此它的贡献就是 $$p_i^{\frac{\prod_j(\alpha_j+1)}{\alpha_i+1}\times\frac{\alpha_i\times(\alpha_i+1)}{2}}=p_i^{\frac{\alpha_i\prod(\alpha_i+1)}{2}}$$ 这个东西就计算 $\prod(\alpha_i+1)$，然后每次乘 $\alp ...