Solutions

RBS 题面 定义括号序列为只包括 $\texttt{(}$ 和 $\texttt{)}$ 的字符串。一个匹配的括号序列（简记为 RBS）满足，可以在其中加入 $1$ 和 $+$ ，将其转化为合法的代数式，例如： $\texttt{()()}$ 和 $\texttt{(())}$ 是匹配的 $\texttt{)(}$ 和 $\texttt{(}$ 和 $\text …

Jayun 发布于 2023-11-06 16:32:22

00

DZY Loves Modification 题面 给出一个 $n\times m$ 的矩阵，并进行 $k$ 次操作，每次操作将矩阵的一行或一列的所有元素的值减 $p$ ，得到的分数为这次修改之前这一列 / 一行的元素和，求分数最大值。 $n,m\le 10^3$ , $a_{i,j}\le10^3$ , $k\le 10^6$ , $p\le 100$ 题解 以减去一 …

Jayun 发布于 2023-11-06 16:25:44

00

题意 定义 $f(i)$ 为非 $i$ 因子的最小正整数，现给出正整数 $n$ ，求 $\sum_{i=1}^nf(i)$ 对 $10^9+7$ 取模后的值。 $n\leq10^{16}$ 。 题解 傻逼题。枚举每个 $f(i)$ 的贡献即可。要容斥掉已经统计的部分。复杂度大概 $\mathcal{O}(1)$ 。 代码 const int N = 1, mod = 1e …

Jayun 发布于 2023-11-06 16:17:57

00

题意 小 Ω 在小学数学课上学到了“幂次”的概念： $\forall a, b \in \N^+$ ，定义 $a^b$ 为 $b$ 个 $a$ 相乘。 她很好奇有多少正整数可以被表示为上述 $a^b$ 的形式？由于所有正整数 $m \in N^+$ 总是可以被表示为 $m^1$ 的形式，因此她要求上述的表示中，必须有 $b \geq k$ ，其中 $k$ 是她事先选取 …

Jayun 发布于 2023-11-05 20:19:08

00

题意 给出一棵树和一个常数 $m$ ，对于每一个 $i~(1\leq i\leq n)$ ，求 $\sum_{j=1}^n\text{dist}(i,j)^m$ 。 题解 关于斯特林数有性质 $x^n=\sum_{i=1}^n\frac{x!}{(x-i)!}\begin{Bmatrix}n\\i\end{Bmatrix}$ ，组合意义相当于枚举非空盒。 则原题有， $$\sum_{k=1 …

Jayun 发布于 2023-11-04 22:46:52

00

第二类斯特林数·行 题目描述 输出 $\begin{Bmatrix} n \\0 \end{Bmatrix},\begin{Bmatrix} n \\1 \end{Bmatrix},\begin{Bmatrix} n \\2 \end{Bmatrix},\dots,\begin{Bmatrix} n \\n \end{Bmatrix}$ 的值。 $1\leqslant n\leqslant 2\ …

Jayun 发布于 2023-11-03 11:57:26

00

题意 给定一棵树，初始时非叶节点均为无色，叶节点会是红色、蓝色或无色。小红和小蓝轮流给无色叶子染色（小红染红色，小蓝染蓝色，小红先染）。所有叶子染完后，非叶节点的颜色将被逐一确定：一个非叶节点的颜色是它所有儿子的颜色中出现较多的那个（保证有奇数个儿子）。最后，根是谁的颜色谁就获胜。求小红是否能赢，若能赢，求出第一步选择哪些叶子能赢。 $n\leq10^6$ 。 题解 一个点有四种情况： 必红。 …

Jayun 发布于 2023-11-02 17:13:53

00

题意 给定整数序列 $A$ ，要构造一个数列 $B$ ，其中 $B$ 由 $0, 1$ 组成，且 $0$ 的个数等于 $1$ 的个数。 在此前提下，构造一个数列 $B$ 使得 $\sum_{i=2}^n A_i*(B_i \otimes B_{\left\lfloor\frac{i}{2}\right\rfloor})$ 最大。输出这个值的最大可能值。 其中， $\ot …

Jayun 发布于 2023-11-02 17:01:29

00

【模板】"动态 DP"&动态树分治 题目描述 给定一棵 $n$ 个点的树，点带点权。 有 $m$ 次操作，每次操作给定 $x,y$ ，表示修改点 $x$ 的权值为 $y$ 。 你需要在每次操作之后求出这棵树的最大权独立集的权值大小。 $1\le n,m\le 10^5$ ， $1 \leq u, v , x \leq n$ ， $-10^2 \leq a_i, y \le …

Jayun 发布于 2023-11-02 08:20:11

00

题意 一个无向图， $n$ 个点 $m$ 条边。 需要构造长度为 $d$ 的序列，要求必须包含 $[1,k]$ 的点，且相邻项有边连接，相邻不相同，可以重复。求序列数量。 $1\le n \le 20, 1 \le m \le \min(150,n*(n-1)/2),0 \le k \le \min(n,7),1\le d \le 10^9$ 。 题解 考虑 $k=0$ 的情况 …

Jayun 发布于 2023-11-01 13:52:57

00