Posts by hostmaster

题意 给定一颗 $n$ 个节点的树，要求添加尽可能少的边，使得任意删除一条边之后，整个图依然联通。 $3 \leq n \leq 10^5$ 题解 首先给出结论：仅需要添加 $\lceil\dfrac m2\rceil$ 条边，其中 $m$ 为叶子节点的数量。构造方法为：从任意一个非叶子节点开始 DFS，按 DFS 顺序给每个叶子节点编号…

题意 给定一个 $n$ 个点，$m$ 条边的无向图。$q$ 次询问，每次询问给出 $a, b, c$，问能否找出一条从 $a$ 到 $b$ 的路径，中途不经过 $c$ 点。 题解 首先对这个图建出一个圆方树。 如果 $c$ 不是割点那肯定有满足条件的路径。 否则判断 $c$ 点是否在圆方树上 $a$ 到 $b$ 的路径中，树剖实现。 cl…

一般来说，如果我们要求出 $F\left(x\right)$ 和 $G\left(x\right)$ 的卷积，会把它们分别 FFT ，然后对应每项乘起来，最后再 IFFT 回来。 但是我们可以合成一个新函数 $H\left(x\right) = F\left(x\right) + iG\left(x\right)$，求出 $H^2\left(x\right)$…

题意 把 $n$ 个颜色不同的球放入 $m$ 个相同的盒子里，且不存在一个盒子里装着超过 $k$ 个球。求方案数对 $998244353$ 取模。 两个方案不同，仅当存在对应盒子，使得第一个方案中的盒子中有一个 第二个方案的盒子中没有的 颜色的球。 $T$ 组数据。 $1 \leq T \leq 200, 1 \leq m, k \leq n \leq 10^6，\sum n \leq 10^8$…

题意 在 $\left[1, 2000\right]$ 中选若干个数，求有多少种方法使得它们的和是 $5$ 的倍数？ 题解 首先，可以猜测答案差不多是 $\dfrac15 \cdot 2^{2000}$，因为 $5$ 种选法里平均会有 $1$ 种满足要求。 但是 $\dfrac15 \cdot 2^{2000}$ 这个东西并不是一个整数，…

题意 有一个无限长的字符串 $s$，其中 $s_i = \operatorname{popcount}\left(i\right)$ 给定 $n$ 个区间 $\left[l_i, r_i\right]$，令字符串 $S = s_{l_1\ldots r_1} + \cdots + s_{l_n\ldots r_n}$。 $q$ 次询问，每…

题意 加里敦大学的生物研究所，发现了决定人喜不喜欢吃藕的基因序列 $T$,有这个序列的碱基序列就会表现出喜欢吃藕的性状，但是研究人员发现对碱基序列 $S$，任意修改其中不超过 $3$ 个碱基，依然能够表现出吃藕的性状。现在研究人员想知道这个基因在 DNA 链 $S$ 上的位置。所以你需要统计在一个表现出吃藕性状的人的 DNA 序列 $S$…

题意 给出一个 $n$ 个点的有向图，每条边的权值都在 $\left[1, 9\right]$ 之间。给出 $t$ ，求从 $1$ 到 $n$，经过路径边权和恰好为 $t$ 的方案数模 $2009$。 $1 \leq n \leq 10, 1 \leq t \leq 10^9$ 题解 将 $1$ 个点拆成 $9$ 个点连成链，每次将出点对…

题意 给定长度为 $n$ 的数组 $a$。你要处理 $m$ 次询问，每次询问需要输出区间中出现次数严格大于区间长度一半的数，或者判断没有这样的数。 $1 \leq n, m \leq 5 \times 10^4$ 题解 这里给出一种乱搞做法。 考虑在区间中随机 $k$ 次，如果区间中存在出现次数严格大于区间长度一半的数，那么每次随机选到这…

之前没见到过这种题，感觉挺有意思的。 题意 给定函数 unsigned int Hash(unsigned int v){ unsigned int t = v; t = t + (t << 10); t = t ^ (t >> 6); t = t + (t << 3); t = t ^ (t >> 11); t = t + (t <<…