牛客IOI周赛19-普及组题解

作者：DeBruyne17
链接：https://www.nowcoder.com/discuss/532747
来源：牛客网
Sol:

A:小y的考试

我们按照字符串的长度排序然后分类讨论判断长度的关系，按照题目的要求输出就可以了。
注意字符串的读入方式。

B:小y的序列

题目要求的本质上是a[i]与i的关系，因此我们发现如果两个数i,j,a[i+1]-sum(1,i)和a[j+1]-sum(1,j)的定值如果相同，这两个彼此的关系就不需要修改，所以我们直接开一个map统计一下哪个值出现的次数最大。

对于n<=1000这个出现次数最大我们可以把它存下来求一个暴力n方求出和这个数相同的数个个数。

C:小y的旅行

对于40%的数据我们朴素维护连通性dfs就可以。

对于100%的数据我们考虑如果一条边的两个端点都大于k那么我们记录为A类边

如果有一个端点小于等于k，那么我们就把这些边存起来设为B类边

对于A类边我们显然不会删，后面会简单证明，但是我们用并查集维护一下它们的连通性。

对于B类边我们如果连接以后没有产生环我们就连接反之这条边得删掉，我们在这里记录一下ans就可以。

我们考虑建出来的总是生成树，而对于生成树我们没有连成环，始终是一棵树的情况，我们对于那些点只要不构成环的保留哪条边都是可以的因此是等价的。

D:小y的游戏

对于4%的数据直接输出样例。

对于28%的数据这部分可以让优秀复杂度的搜索剪枝通过

对于44%的数据我们有一个四维dp，分别记录dp到第i位，每种操作都用了几次，然后我们可以对于这个可行性进行dp，我们二分答案即可

（这里的每种操作对应这个三连冲击波的三种操作，对应着-9 -3 -1的情况）

对于100%的数据我们发现这个四维dp的最后一位可以用技巧优化掉，我们把dp数组换成int类型的，然后我们记录一下前两个操作的使用次数的情况所需要导致到当前第三种操作也就是这个-1的最少需要用几次。

然后我们同样采用二分来变成一个判定性的条件就可以了。这题状态数不多，二分可以通过！