1919d

· · 题解

考虑将题目转化为：

D'$：对于一对相邻的差值为一的数，可以只留下较小的那个，问是否能使得只剩一个 $0

为什么可以这么转化？

考虑删去 1,2 两点，他们的权值上浮为 b 号店，容易发现不影响这颗二叉树的构成。

接下来考虑如何解决 D'。

考虑到序列最大值只能被其他值删去，而且对于一个最大值极长连续段，只要端点可以被删，那么一定可以删去这个连续段。

我们用一个 vector v[x] 存储值为 x 的所有点在链表中的迭代器位置。

我们考虑删除 v[x] 中的所有元素：

如果某点可以被删除，那么删掉，继续检查后面的点，如果有没被删掉的节点，那么说明不合法，输出 no。

最后检查链表中是否只有一个 0，若是，那么合法，否则不合法。

每个点只会被删除一次，时间复杂度 \mathcal{O}(n)，代码