Siyuan 的博客

置顶CSP 2019 算法模板复习！

关于它，它咕了

「Codeforces 1228E」Another Filling the Grid

题目链接：Codeforces 1228E

你有一个 $n \times n$ 的网格和一个整数 $k$，在每个格子中都填入一个整数，满足如下条件：

• 所有格子中的整数都介于 $1$ 到 $k$ 之间。
• 第 $i$ 行的最小值为 $1$（$1 \le i \le n$）。
• 第 $j$ 列的最小值为 $1$（$1 \le j \le n$）。

请求出填数的方案数，答案对 $10 ^ {9} + 7$ 取模。

数据范围：$1 \le n \le 250$，$1 \le k \le 10 ^ {9}$。

「Codeforces 1217D」Coloring Edges

题目链接：Codeforces 1217D

你有一个包含 $n$ 个点和 $m$ 条边的有向图（没有自环或重边）。

定义一张图的 $k$ 染色为：将每条边染成 $k$ 种颜色中的一种。一个 $k$ 染色是好的当且仅当不存在一个环满足环上的所有边颜色相同。

你需要求出这张图的 $k$ 染色，并最小化 $k$ 的值。

数据范围：$2 \le n \le 5000$，$1 \le m \le 5000$。

「Codeforces 1204E」Natasha, Sasha and the Prefix Sums

题目链接：Codeforces 1204

Natasha 最喜欢的数字是 $n$ 和 $1$，Sasha 最喜欢的数字是 $m$ 和 $-1$。某一天他们写下了长度为 $n + m$ 且包含恰好 $n$ 个 $1$ 和 $m$ 个 $-1$ 的所有可能的序列。对于每一个序列计算出它的最大前缀和（允许为空）；形式化地，我们定义 $f(a)$ 表示序列 $a_{1, \dots, l}(l \le 0)$ 的最大前缀和，那么有：

$$ f(a) = \max \left (0, \max _ {i = 1} ^ {l} \sum _ {j = 1} ^ {i} a_{j} \right ) $$

现在他们想要对于所有满足条件的序列，求出 $f(a)$ 的总和。答案对 $998244853$ 取模。

数据范围：$0 \le n, m \le 2000$。

「Codeforces 662C」Binary Table

题目链接：Codeforces 662C

你有一个 $n \times m$ 的表格。每个格子都有一个数字 $0$ 或 $1$，你可以任意选择某一行或者某一列并将其翻转。请问通过任意次操作后表格中 $1$ 的个数的最小值是多少？

数据范围：$1 \le n \le 20$，$1 \le m \le 10 ^ {5}$。

「TJOI / HEOI 2016」求和

题目链接：LOJ 2058

在 2016 年，佳媛姐姐刚刚学习了第二类斯特林数，非常开心。

现在他想计算这样一个函数的值：

$$ f(n) = \sum_{i = 0} ^ {n} \sum_{j = 0} ^ {i} S(i, j) \cdot 2 ^ {j} \cdot j! $$

$S(i, j)$ 表示第二类斯特林数，递推公式为: $S(i, j) = j \cdot S(i − 1, j) + S(i − 1, j − 1), 1 \le j \le i − 1$。

边界条件为：$S(i, i) = 1(i \ge 0), S(i, 0) = 0(i \ge 1)$。

你能帮帮她吗？

数据范围：$1 \le n \le 10 ^ {5}$。

「Codeforces 1174F」Ehab and the Big Finale

题目链接：Codeforces 1174F

这是一道交互题。

给定一棵有 $n$ 个点的树，节点 $1$ 为根节点。

我们选择一个隐藏节点 $x$，你需要进行以下三种操作来找到这个节点 $x$ 的编号。

• d u：你会得到节点 $u$ 和 $x$ 之间的距离。两个节点之间的距离定义为最短路径上的边数。
• s u：你会得到节点 $u$ 到 $x$ 的最短路径上的第二个节点。但是如果 $u$ 不是 $x$ 的祖先，你会直接得到 Wrong answer 的结果！
• ! u：回答隐藏节点 $x$ 的编号为 $u$。

你需要在 $36$ 次询问（不包括回答）内找到 $x$ 的编号。这个隐藏节点 $x$ 不会根据你的询问而改变。

数据范围：$2 \le n \le 2 \times 10 ^ 5$。

「Codeforces 1189F」Array Beauty

题目链接：Codeforces 1189F

我们定义一个序列 $b_{1}, b_{2}, \dots, b_{n} (n > 1)$ 的「美丽值」为 $\min_{1 \le i < j \le n} \lvert b_{i} - b_{j} \rvert$。

我们给定一个序列 $a_{1}, a_{2}, \dots, a_{n}$ 个一个数字 $k$。请计算出所有长度恰好为 $k$ 的子序列的「美丽值」之和，答案对 $998244353$ 取模。

数据范围：$2 \le k \le n \le 1000$，$0 \le a_{i} \le 10 ^ {5}$。

「Codeforces 1189D2」Add on a Tree: Revolution

题目链接：Codeforces 1189D2

你有一个棵 $n$ 个点的树，初始所有的边上的数字都是 $0$。对于每次操作，你可以选择两个不同的叶子节点 $u,v$ 和一个任意整数 $x$ 并把 $u - v$ 这条简单路径上的边加上 $x$。

每条边都有一个目标状态，用一个两两不同的非负偶数表示。你需要判断这个目标状态是否可以通过有限次操作达到。如果可行则输出 YES 和构造的方案；否则输出 NO。

注意叶子节点的定义为度数为 $1$ 的点。

数据范围：$2 \le n \le 10 ^ {5}$。

「Codeforces 1189D1」Add on a Tree

题目链接：Codeforces 1189D1

你有一个棵 $n$ 个点的树，初始所有的边上的数字都是 $0$。对于每次操作，你可以选择两个不同的叶子节点 $u,v$ 和一个任意实数 $x$ 并把 $u - v$ 这条简单路径上的边加上 $x$。

我们令 $w_{i}$ 表示最终第 $i$ 条边上的实数，是否对于所有的 $w_{i} \in \mathbf{R}, 1 \le i < n$，都存在有限的操作使得所有的边都满足条件？如果可行则输出 YES 否则输出 NO。

注意叶子节点的定义为度数为 $1$ 的点。

数据范围：$2 \le n \le 10 ^ {5}$。

「Luogu 4173」残缺的字符串

题目链接：Luogu 4173

很久很久以前，在你刚刚学习字符串匹配的时候，有两个仅包含小写字母的字符串 $A$ 和 $B$，其中 $A$ 串长度为 $m$，$B$ 串长度为 $n$。可当你现在再次碰到这两个串时，这两个串已经老化了，每个串都有不同程度的残缺。

你想对这两个串重新进行匹配，其中 $A$ 为模板串，那么现在问题来了，请回答，对于 $B$ 的每一个位置 $i$，从这个位置开始连续 $m$ 个字符形成的子串是否可能与 $A$ 串完全匹配？

数据范围：$1 \le m \le n \le 3 \times 10 ^ {5}$。