AtCoder Beginner Contest 320

https://atcoder.jp/contests/abc320

F - Fuel Round Trip

题意

题意很简单就是要在从 $0$ 位置走到 $X_n$ 位置，然后倒回来回到 $0$ 位置。并且每走一格需要 $1$ 的油，油箱最多携带 $H$ 的油，途中有一些只能使用一次的加油站，选择加油只能强制花费 $p_i$ 元加入 $f_i$ 的油，装不下只能抛弃。现在问你从 $0$ 开始有 $H$ 的油，走一个来回最小要多少钱。

题解

关键在于状态的设计。令 $f_{i,j,k}$ 表示考虑前 $i$ 个加油站，去的时候在第 $i$ 个加油站油量为 $i$ 返回的时候油量为 $j$ 的最小代价，然后考虑这个不加油、去的时候加油、返回的时候加油即可。

G - Slot Strategy 2 (Hard)

题意

给定 $n$ 个长度为 $m$ 的字符串 $s_i$（字符集为 0 ~ 9），在每一个时刻，你可以固定一个未固定的字符串，之后其他所有未固定的字符串，将向前循环移位一位，求让所有字符串固定且第一位相等的最小时刻。

题解

考虑枚举最终确定的数字，然后二分答案 $t$。

我们建立二分图检验，左边是每一行，右边是时间。每一行连向满足条件的时间，这样的时间点会很多，但我们只需要考虑前 $n$ 个就可以了。因为我们要保证最大匹配是 $n$，最坏情况就是前 $n-1$ 个被其他行匹配。