【2018 集训队互测 Day 4】小修和小栋玩♂游戏

链接

毒瘤司司出题

我在这个链接找到的这题,原数据范围只有

我不会于是拿给司,司第二天和我讨论了一个搜索过掉了。

于是司打算搞成集训队互测,自称说新加入的数据也许要用不同的方法过,还给我演示了如何退火。

最后范围是

冷静分析

一开始没想到,但后来突然发现了一个事实:

如果存在一个 的答案,那么可以直接应用于所有 上,其中

一个沙比的100分做法

全都退火。

一个优秀的76分构造

来自 cdsf。

cdsf 说这后面的数据是 IOI 练习赛题。

(cdsf 已经开始准备 IOI 了!)

本质上 cdsf 构造了一个 的方案,给这 个灯标号 ,Alice将亮着的标号都异或起来,与目标数再异或一下就是需要调整的灯的编号。

把它应用于后 个点,期望得分

一个优秀的88分构造

很显然我们可以优化一下 cdsf 的做法。

号灯显然可以使用“不进行操作”代替,所以需要的灯的数量变成了 ,本质上是一个 的方案。

代码非常简洁。

下面给出一个 的构造:

 

可以过后 个点,期望得分

一个优秀的100分做法

当时刚拿到这道题的时候,司是如何快速地搜出第一个点的?

首先状压搜一下包含 的数的集合 ,满足

一共 种。

然后选 个出来使得两两没有交就 OK 了。这一步搜索非常快。

一个优秀的100分构造

???

一个优秀的100分手玩

0