【11.15】Codeforces 刷题

$\text{DP}$ ：

---

E. Packmen

题意：

输入 $n(2\le n\le 10^5)$ , 接着给你一个长度为 $n$ 的字符串。
$\ast$ 代表包装， $P$ 代表人, $.$ 代表为空, 人移动一单位距离需要花费一秒，人可以向左或者向右移动。人只要走到包装的位置，就会把包装吃掉，问你最少需要多少秒。所有的包装就被人全吃完。

题解：CF847E Packmen 题解

思路：虽然是在 $\text{DP}$ 题单里，但是我用二分写的。这道题二分细节特别多。

首先二分答案。check ：

实时维护第一个没有被清理的垃圾的位置，然后从左到右遍历每一个人。

容易知道，一个人的策略是要么先右后左，要么先左后右。我们把第一个垃圾作为左边界，二分出来一个右边界，问这个人能把指针指向的这个垃圾清理掉，向右最远能走多远。这样能在这个人的最优策略下，把第一个垃圾清理掉，并尽可能向右走。

AC代码：https://codeforces.com/contest/847/submission/181033864

---

C. Helga Hufflepuff’s Cup

题意：

给你一棵 $n(1\le n\le 10^5)$ 个节点的树，可以染 $m(1\le m\le 10^9)$ 种颜色，定义一个特殊颜色 $k(1\le k\le m)$，要求保证整棵树上特殊颜色的个数不超过 $x(1\le x\le 10)$ 个。同时，如果一个结点是特殊颜色，那么它的相邻结点的颜色编号必须全部小于 $k$。求方案数。

思路：树上背包。不多解释，详见 题解 。

AC代码：https://codeforces.com/contest/855/submission/181046023

---

构造题 ${}^{\ast }1700{\sim }^{\ast }2000$ ：

---

E. MEX and Increments

题意：

给你一个长度为 $n(1\le n\le 2\cdot 10^5)$ 的数列 $a(0\le a_i\le n)$ ，每次可以花费 $1$ 代价将其中一个数加一。从 $0$ 到 $n$ 分别输出至少要花费多少才能使这个数是数列中没有出现的最小的非负整数。

思路：简单贪心题。优先队列实现。

AC代码：https://codeforces.com/contest/1619/submission/181050825

---

B. Edge Weight Assignment

题意：

给定一棵 $n(1\le n\le 10^5)$ 个点的无根树，要求给每条边分配一个正整数权值，使得任意两个叶子节点之间路径上的边权异或值为 $0$。求最少要多少种不同权值，以及最多可以使用多少种不同权值。
这里，填入的边权值可以为任意大。

思路：推理找性质和结论。最小值只可能为 $1,3$ 两种。最大值表达式为 $ans={\sum }_u({\sum }_{v\in son(u)}[v是非叶子节点]+[存在v\in son(u)为叶子节点])$ 。易知换根不影响两者的答案，因此随便钦定一个非叶子节点为根即可。

AC代码：https://codeforces.com/contest/1338/submission/181056728

---

G. A/B Matrix

题意：

第一行包含一个整数$t$ $(1\le t\le 1000)$，表示数据的组数。

接下来有$t$行输入，每行输入都包含四个正整数：$n$, $m$, $a$, $b$ $(1\le b\le n\le 50;1\le a\le m\le 50)$。其中，$n,m$为矩阵的行数和列数、$a,b$为矩阵中每行包含的$1$的个数和每列包含的$1$的个数。

思路：自己手摸了几个数据，想了一个方法，但有点麻烦。这个 题解 的方法更简单一些。

AC代码：https://codeforces.com/contest/1360/submission/181062481

---

E. Directing Edges

题意：

给定一个由有向边与无向边组成的图，现在需要你把所有的无向边变成有向边，使得形成的图中没有环。

如果可以做到请输出该图，否则直接输出"NO"。

$2\le n\le 2\cdot 10^5,m\le 2\cdot 10^5$

思路：和拓扑序结合起来的一道妙题。先把有向边抽出来拓扑，得到一个拓扑序，在拓扑序上从左到右连接无向边即可。

对于树，根据深度来确定先后顺序；对于拓扑图，根据拓扑序确定先后顺序。

AC代码：https://codeforces.com/contest/1385/submission/181076648