比赛地址

4-adjacent

我们把所有数分成 $3$ 类:$4$ 的倍数、不是 $4$ 的倍数但是是 $2$ 的倍数、奇数。

那么肯定是第三种和第一种交错排,在最后放第二种最好。直接判一下第一种的数量是否 $\geq$ 最后一种的数量即可。

当没有第二种数时最后还可以放一个第三种数,此时应该是第一种的数量 $+1\geq$ 最后一种的数量。

代码

Grid Coloring

蛇形填上每种颜色即可。

代码

Young Maids

考虑反着做,即每次选出能选的最小的放在开头 。

考虑什么是能选的。首先,把它去掉后留下的段长度都应该是偶数;其次,选的两个数不能跨过某个已经被选走的数。

我们把已经被选走的数拿掉,相当于分成了若干段,则我们选的数中前面那个数应该在奇数位、后面那个数应该在偶数位。

于是我们每次要选一个最小的出来,可以用堆维护每个区间中奇数位的最小值,这个可以在线段树上查询。然后要确定偶数位的最小值,同样可以在线段树上查询。

代码

Prime Flip

考虑差分,则我们每次可以选两个位置 $i,j$ 满足 $|i-j|$ 是奇素数,然后把 $a_i,a_j$ 反转。

考虑任意两个数 $i,j$ 要多少次操作才能一起反转:

  • $|i-j|$ 是奇素数:显然只要一次。
  • $|i-j|$ 是偶数:根据哥德巴赫猜想,需要 $2$ 次。(需要注意的是 $2,4$ 并不满足,但是我们可以拆成 $7-5$ 和 $11-7$)。
  • $|i-j|$ 是奇合数:同理,需要 $3$ 次。

那么一个贪心是让第一种尽可能多,其次第二种尽可能多,第三种最少。

如果 $a_i,a_j$ 都需要反转且 $|i-j|=1$,则在 $i,j$ 间连一条边。不难发现形成的图是二分图。那么最大匹配即为第一种最多的数量。

最后可能还会剩下一些奇数和偶数,那么内部两两匹配,使得第二种尽可能多。

最后可能还会剩下一奇一偶,那就只能这两个匹配了。

代码

最后修改:2020 年 09 月 23 日 02 : 27 PM