标签 欧拉路径 下的文章

「Codeforces 1186F」Vus the Cossack and a Graph

题目链接：Codeforces 1186F

Vus 有一张包含 $n$ 个点和 $m$ 条边的图。设 $d_i$ 表示第 $i$ 个点的度数。他需要保留 $\left\lceil\frac{n + m}{2}\right\rceil$ 条边，设 $f_i$ 表示新图中第 $i$ 个点的度数。他需要对于所有的 $i$ 保证 $\left\lceil\frac{d_i}{2}\right\rceil \le f_i$。

请你帮 Vus 保留一些边使这张图满足条件。

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

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