Posts by hostmaster

题意 进行以下操作，维护树结构： 换根 查询 LCA 子树加 查询子树和 $1 \leq n, m \leq 10^5$ 题解 首先你需要会 这个。 这题跟 P3979 遥远的国度 唯一的区别就是要求个 LCA 嘛。 但其实你会发现这个操作毫无难度。 我们开局的时候随便选一个点把树剖了，然后看怎么应付操作。 假设当前根为 $r$。 我们记…

前言 树剖其实在一些情况下是可以换根的，会多一些分讨。 过程 我们以一道题为例。 题意 进行以下操作，维护树结构： 换根 链赋值 查询子树最小值 $1 \leq n, m \leq 10^5$ 题解 我们现随便以一个点把树剖了，然后看看怎么应付这些操作。 注意到树上两点之间的简单路径是直接确定的，所以树剖并不影响我们的链操作。 我们在根为…

题意 给定 $n$ 和 $k$，生成一个长度为 $n$ 的数组 $a_i = i - 1$，如果一段区间 $\left[l, r\right]$ 是好的，仅当对于任意 $l \leq i \leq r$，都满足 $a_i$ 二进制表示中为 $1$ 的位的个数不超过 $k$。 找到 $a$ 中好的区间的个数，对 $10^9 + 7$ 取模。…

题意 给定一个 $n$ 个点，$m$ 条边的连通无向图。您的任务是最小化此图中存在路径的顶点对 $1 \leq u < v \leq n$ 的数量。要实现此目标，您可以从图中移除一条边。 找到最小数量的顶点对！ $1 \leq n, m \leq 10^5$ 题解 显然删除一个边双连通分量中的边没有任何用处。 于是先跑 Tarjan 缩边…

简述 对于某些电路，我们用一些特征来判断它的 复杂度。 复杂度类 $\mathsf{AC^0}$ 电路 由多项式大小，常数深度，无限扇入（fan-in）的电路系（circuit families）描述的语言。非门只允许出现在输入处。 $\mathsf{ACC^0}\left[m\right]$ 电路 由多项式大小，常数深度，无限扇入（fa…

前言 RSA（Rivest–Shamir–Adleman）算法是一种公钥加密算法，过程主要经历 钥生成，钥分发，加密和解密。 钥分发，加密和解密 比较简单。 思想 如果我们能找到三个大数 $e, d, n$，满足对于任意 $0 \leq x < n$，都有 $$\left(x^e\right)^d \bmod n = x$$ 那么，我们把…

题意 给定 $n, b, s, r$。 有 $n$ 个点，$r$ 条边的有向图，边有边权，表示通信成本。编号为 $b + 1$ 的点是中转点，任意两点发送信息都要先送到 $b + 1$，再由 $b + 1$ 送到目标点。 你要把前 $b$ 个点任意分成 $s$ 组，每组里的任意两个点都要互发消息。 总代价为所有组的通信成本之和。 求出最小…

复读 https://www.matrix67.com/blog/archives/6970 $9$ 个硬币，有一个假币。你有一个天平，可以告诉你哪边重或一样重。天平上可以放任意多枚硬币，问你至少几次保证知道哪个是假币。 假币一定比正常币轻一些。 两次就可以。这个问题大家小学五年级就在课本上看过了。 那假设这个天平离线了，两次称完之后才会…

约定 设 $F\left[i\right]$ 表示 $x_i$ 的系数。 四则运算 加减法 $$ F \left(x\right) \pm G\left(x\right) = \sum\limits_{i = 0}\left(F\left[i\right] \pm g\left[i\right]\right) x^i $$ 就是对应项做对…

题意 给定 $n \times n$ 的可逆矩阵 $A$，和一个矩阵 $C$，$C$ 与 $A$ 的逆矩阵不同的位置为 $k \leq 12$ 个。求 $A$ 的逆。 $1 \leq n \leq 2000$ 题解 大家应该都做过一道经典题： 给定 $2000 \times 2000$ 的矩阵 $A$ 和 $B$，判断 $AB$ 是否等于…