标签 构造 下的文章

「Codeforces 1217D」Coloring Edges

题目链接：Codeforces 1217D

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

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

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

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

「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}$。

「Codeforces 1199E」Matching vs Independent Set

题目链接：Codeforces 1199E

给定一个由 $3 \cdot n$ 个点、$m$ 条边组成的图。你需要找到一组大小为 $n$ 的边的匹配，或者找到一组大小为 $n$ 的独立集。

一组边的匹配表示不存在两条边拥有一个共同的点。

一组独立集表示不存在两个点被同一条边相连。

如果能找到一组边的匹配，输出 Matching 和方案；如果能找到一组独立集，输出 IndSet 和方案；否则输出 Impossible。

本题有 $T$ 组数据。

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

「Codeforces 1180D」Tolik and His Uncle

题目链接：Codeforces 1180D

你有一个 $n \times m$ 的网格图，最初你在 $(1, 1)$ 的位置。每次你需要选择一个 $(dx, dy)$，从当前位置 $(x, y)$ 移动到 $(x + dx, y + dy)$ 的位置。显然你不能离开网格，而且你必须将每个格子访问恰好一次（最初的 $(1, 1)$ 被认为是已经访问过了），所使用的 $(dx, dy)$ 还需要保证两两不同。

数据范围：$1 \le n \cdot m \le 10 ^ 6$。

「Codeforces 1148E」Earth Wind and Fire

题目链接：Codeforces 1148E

数轴上有 $n$ 块石头。最初，第 $i$ 个石头位于坐标 $s_i$ 的位置。同一个地方可能有不止一块石头。

你可以进行如下操作任意次（可以为 $0$ 次）：

• 拿出下标为 $i, j$ 且满足 $s_i \le s_j$ 的两块石头，选择一个整数 $d$ 满足 $0 \le 2 \cdot d \le s_j - s_i$ 并将第 $i$ 块石头放到坐标为 $(s_i + d)$ 的地方，将第 $j$ 块石头放到坐标为 $(s_j - d)$ 的地方。换言之，将两块石头相互靠近。

你想通过移动，将石头的坐标变为 $t_1, t_2, \dots, t_n$，注意石头的顺序是无关紧要的。

判断是否存在一种移动石头的方法。如果可以，输出 YES 并构造一种方法；否则输出 NO。你不需要最小化移动次数。

数据范围：$1 \le n \le 3 \times 10 ^ 5$，$1 \le s_i, t_i \le 10 ^ 9$。

「Codeforces 1152E」Neko and Flashback

题目链接：Codeforces 1152E

现在 Neko 有一个长度为 $n$ 的数组 $a$ 和一个长度为 $n - 1$ 的排列 $p$。现在他进行如下操作：

• 构造一个长度为 $n - 1$ 的数组 $b$，其中 $b_i = \min(a_i, a_{i +1})$。
• 构造一个长度为 $n - 1$ 的数组 $c$，其中 $c_i = \max(a_i, a_{i +1})$。
• 构造一个长度为 $n - 1$ 的数组 $b'$，其中 $b'_i = b_{p_i}$。
• 构造一个长度为 $n - 1$ 的数组 $b'$，其中 $c'_i = c_{p_i}$。

然而 Neko 只记得数组 $b'$ 和 $c'$ 了，将原来的数组 $a$ 和排列 $p$ 都忘记了。他想让你帮他找到任何一个合法的数组 $a$。如果没有任何一个可能的数组，那么输出 -1。

数据范围：$2 \le n \le 10 ^ 5$，$1 \le b'_i, c'_i \le 10 ^ 9$。

「ARC 102B」All Your Paths are Different Lengths

题目链接：ARC 102B

给定一个整数 $L$，构造一张满足如下条件的有向图。图中可以包含重边，可以证明这样的图一定是存在的。

• 这张图的点数 $n$ 至多为 $20$，点从 $1$ 到 $n$ 标号。
• 这张图的边数 $m$ 至多为 $60$，边的长度为 $[0, 10 ^ 6]$。
• 每条边从标号小的点连向标号大的点，也就是说 $1, 2, \cdots, n$ 是这张图的一种可能的拓扑序。
• 从点 $1$ 到 $n$ 有 $L$ 条不同的路径，这些路径的长度两两不同，长度分别为 $0$ 到 $L - 1$。

此处路径的长度为这条路径上所有边的长度之和。当两条路径包含的边的集合不同时，这两条路径是不同的。

数据范围：$2 \le L \le 10 ^ 6$。

「ARC 103D」Distance Sums

题目链接：ARC 103D

你有一个长度为 $n$ 的序列 $D_1, D_2, \cdots, D_n$，所有的 $D_i$ 是两两不同的。是否存在一棵树满足如下条件？

• 节点从 $1$ 到 $n$ 标号，边从 $1$ 到 $n$ 标号。
• 对于每个节点 $i$，它到其他节点的距离之和为 $D_i$，注意每条边的长度都是 $1$。

如果存在这样一棵树，求出这棵树。

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

「ARC 103C」Tr/ee

题目链接：ARC 103C

你有一个长度为 $n$ 的字符串 $s$。是否存在一棵有 $n$ 个节点的树满足如下条件？

• 节点从 $1$ 到 $n$ 标号。边从 $1$ 到 $n - 1$ 标号。
• 如果字符串 $s$ 的第 $i$ 个字符为 $1$，那么我们可以通过删掉其中一条边得到一个大小为 $i$ 的连通块。
• 如果字符串 $s$ 的第 $i$ 个字符为 $0$，那么我们不能通过删掉任何一条边得到一个大小为 $i$ 的连通块。

如果存在这样一棵树，求出这棵树。

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