一道抽象题

Le0Chan · 2025-02-13 17:55:10 · 题解

CF1091E

看到题，首先想到怎么 check 一个度数序列是否合法。可以想到一个贪心做法：每次找出度数最小的点 x，然后找出度数前 dg_x 大的点，将这些点与 x 配对。中间任何一步配不出来就倒闭。

但是这样的贪心形式显然没法快速计算。我猜测是这个贪心做法还有别的较为好做的形式，但是试了一下应该只有这种贪心做法是对的。

于是我就不会了，打开题解后发现题面里给出了一个链接。链接里可以注意到一个叫 Erdős–Gallai_theorem 的东西，打开之后发现就是一个形式化的 check 度数序列的方式。原来出题人以这种方式来提供基础的做题思路。。。我还以为在打愚人节比赛。

然后看到样例可以猜测答案是一个区间内的同奇偶的数。00111000 这样的东西一般是二分不了的，但是注意到一个问题是：假如不合法，那么考察一下是哪个位置被 ban 了，如果这个位置在 mid 左边，那么说明 mid 需要被调大，否则反之。