【题解】牛客IOI周赛18-普及组

首先对这次比赛的题面以及D题数据的一些问题表示十分的抱歉....对不起耽误了大***贵的时间

A

对于出现的个数字,我们可以开四个变量来分别表示最大,次大,最小,次小.四个值.然后每次对比当前数字与这四个变量的大小关系并更新即可.

B

发现最大只有,所以我们可以枚举所有的区间,然后在枚举每一个区间时同时记录区间内的数字出现次数,然后再根据数字的出现次数统计答案即可.

C

发现我们可以先在这个地宫中使用把所有可以到达的格子搜索出来,并且在搜索的过程中找到所有能够使用的宝藏并记录下他们的能力值.然后我们把这些宝藏的能力值当成一个序列,发现我们要求这个能力值之差最小,如果我们要枚举能力值区间的左端点的话.那么我们把某个宝藏的能力值当成这个能力值区间的左端点一定会比枚举其他的值当作左端点会更优.而且这个右端点也一定是落在某个宝藏的能力值上最优.而对于这个能力值区间,我们关心的是它是否包含了个不同的能力值,如果我们把每个能力值当成一个点的话,我们要求的就是让这个区间包含个点并且这个区间的长度最长.

但是这样的话我们会遇到一个问题:有很多的权值没有出现过,而且权值的范围太大,不允许我们直接枚举.

所以我们就要将出现过的这些权值离散化,根据我们之前的结论,我们可以在离散化之后将序列去重,然后我们使用双指针的方法,枚举每个左端点,然后右端点可以通过计算计算出来,然后统计一下现在的权值之差,取一个最小值即为答案.

D

发现我们可以枚举一下最早不能释放的法术是哪个.那么显然如果把法术按照能量消耗从小到大排序后.第个法术不能释放的话,消耗比小的法术一定都要被释放.
然后再来考虑一下消耗比大的法术
发现我们可以用计数类的背包来解决.
最后需要注意一点,如果全都能释放的话,也需要算一种方案,所以我们要枚举到第个法术.