竞赛讨论区 > 【题解】牛客练习赛16
头像
牛客网小运营
发布于 2018-12-27 16:40
+ 关注

【题解】牛客练习赛16

(题解由比赛出题人提供,点击右侧“本文相关内容”的题目即可开始做题)

T1 字典序最大的子序列
我们让循环一开始的起始位置为0 。然后做26次循环,从'Z'到'A'。若当前循环的字符为k,我们从起始位置开始找所 有出现的字符k,每出现一次就加到答案字符串末尾,然后更新起始位置为当前位置。这样构造出的一定是字典序 最大的字符串。

T2 漂亮的树
我们先考虑前图片说明 的数字,由于图片说明 ,所以必须调成递增的差值为1的递增序列。我们最朴素的想法是先确定的值,对于不同的图片说明 我们算有多少个图片说明 ,找最大的那个。这样就把 图片说明 分成了几个集合。但是这样枚举想想会超时。但是这时你会惊奇的发现,对于在一个集合里的元素图片说明 是相同的~。因此我们统计一下对于每个值图片说明 的数量。对于后半段的数字也是类似的操作。然后我们找这些数量的最大值图片说明图片说明 就是答案。 鉴于可能出现负数,做桶排的时候下标要在加个P=1000000。

T3 任意点
我们建个图,对于任意两个在同行或同列的点我们都连一条边。如果两点可达,那么这两个点一定在一个联通块里。因此我们拿并查集统计下有多少联通块。若有k个联通块,然后最少加k-1个点把这些联通块连起来全部可达了。因此答案为k-1。

T4 k进制数
由于这个题求的是一个字符串所有的子串有多少数字满足k进制下d(x)=b,这个数字很明显会满足一些性质。 考 虑这个每次转化的过程,每一次进位相当于把一个k转化成了一个1,也就是说,在数位和mod(k-1)的意义下, 转化前和转化后的数字是等价的,最终会成为(x-1)mod(k-1)+1然后就不能动了 如果b=0,那么显然只有这 个串的所有数字都为0(也就是说这个数字为0)才成立,否则一个串一定不能转化为0否则这个串的和一定在mod(k-1)的意义下和b(mod(k-1))等价,这里简单的前缀和或者维护一个偏置值,维护前面的和(用map啥的)都 可以做 所以总之按照b=0分类,然后分类计算一下即可。

T5 求值
E的话我们把数按二进制分成 位,因此我们现在有两维,一维是序列,一维是数位。我们先要计算一下在当 前下标为i的位置,每个数位 最后一次出现的下标位置,这个可以递推解决之后后我们做一下前缀或prei
然后我们接下来固定区间右端点r,然后找不同的 的情况下会产生的数。这样的数最多20个。一开始我们的数 是[1,r]或后的结果,也就是pre[r]。我们前面算过下标为r,数位k出现的最晚位置,那么我们把这些位置和数位按照 位置的前后顺序排序,然后把这些数位按前后顺序从pre[r]中从1变为0,这个排序+亦或解决。当然位置相同的必须 同时变换。然后每次变换以后看看这个数字是否出现过,没有答案+1。因此我们还要写一个标记数组来确认数字是 否出现过。
对了还要特判一下0有没有在序列中出现过,有的话答案+1。
因此总合一下复杂度图片说明 差不多 。后面图片说明 是排序的复杂度。

T6 选值
你先排序一下。当确定最大值为aj时, 用lower_bound找找前面大于等于图片说明 的第一个数图片说明 ,因此我们可以在图片说明 中任选两个数作为一个组合,对答案的贡献为 图片说明

其他疑问可加以下交流群(加入一个即可啦~)
牛客多校算法训练营1:453799454
牛客全国算法训练营2:330766563
牛客多校算法训练营3:934889305

全部评论

(0) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐