比赛地址

Scc Puzzle

直接算一下就好了。

代码

Menagerie

枚举前两只是羊还是狼,那么后面的都可以直接推出来,判断一下第一只和最后一只是否满足条件即可。

代码

Frequency

我们肯定是选一个最高的标号最小的,然后把最高的标号大的减去 $1$。

于是把所有数从大到小排序,那么在一个 $a_i\neq a_{i+1}$ 的地方,我们会把前面 $i$ 个 $a_i$ 都削成 $a_{i+1}$,也就是前面标号最小的那个多了 $i\times(a_i-a_{i+1})$ 个。

代码

Flags

显然二分答案,问题变为是否存在一组方案满足相邻两个的距离 $\geq mid$。

因为每个旗帜有两种选择,可以想到 2-SAT。

考虑连边。对于某个位置 $p$,有一个位置在 $(p-mid,p+mid)$ 中的那些旗帜都只能选另外一个位置,于是直接连过去即可。

这样子连边和边数都是 $\mathcal{O}(n^2)$ 的,考虑优化。可以发现我们实际上是向一个区间的反点连边,于是可以考虑用线段树优化连边。我们建一棵线段树,每个叶节点存的都是反点的编号,这样子连边时二分出对应的区间就好了。注意自己不能向自己的反点连边,所以还要二分出自己的位置。

代码

最后修改:2020 年 09 月 16 日 08 : 33 PM