CF1214

$Div.1+Div.2$

第一种货币只有面值 $1$ 有用,第二种货币只有面值 $5$ 有用.

枚举换了多少个第二种货币,时间复杂度 $O(\frac n {5e})$ .

读懂题后就是两个不等式,手动解一下.

第一次遇到不合法的 $-1$ 时,将它忽略,最后再放回去,看能否合法.

显然答案 $\le 2$ ,因为我们可以去掉与出发点相邻的两个点.

于是只需要判断 $0$ 与 $1$ 是否合法.

$0$ 就是判断起点能否到终点.

$1$ 就是判断是否存在一个点 $x$ ,使得每条从起点到终点的路径都经过 $x$ .

设 $f(x),g(x)$ 分别表示起点到 $x$ 的路径数, $x$ 到终点的路径数,判断是否有 $f(x)\cdot g(x)$ 等于起点到终点的路径数.

可以假定 $d_i$ 是从大到小排好序的,否则可以先排序.

建出一条链,链上节点依次为 $1,3,5,\dots,2i-1$ .

然后再将偶数编号的节点 $2i$ 依次挂上去,找到链上的第 $i+d_i-1$ 个节点,将 $2i$ 挂在它的旁边即可.

因为 $d_i$ 是从大到小排好序的,且 $d_i\le n$ ,所以这样做总能构造出合法解.

待更.

待更.

待更.