竞赛讨论区 > 【题解】牛客练习赛54
头像
SovietPower✨
编辑于 2020-04-12 11:58
+ 关注

【题解】牛客练习赛54

A.乘积Product

,那么可以用unsigned long long存,直接枚举即可。注意
也可以对每个算其贡献,答案是

B.求和Summation

可以表示,有个位置,每个位置可以放一个球或者不放。设第一个球到位置的距离为。对求和就是在所有情况中,的和。
枚举第一个球在位置,那么贡献是,所以答案就是
(发现能到,也不知道怎么评价难度...于是只能扔到B了...

是非负整数,请特判,没有卡常的问题。

C.排序Sort

操作可以简化成,每次花费的代价交换相邻两个位置。
考虑枚举最终的字符串中每种字符的相对位置,然后依次将每个字符换到对应位置上去。
容易想到只考虑向左的代价,向右的不计算。事实上不对,比如AGCAG,如果最终序列是AACGG,会算出的花费,偏小...
位置的字符放到位置会影响之间的字符(若,则的字符位置减;否则会令的字符位置)。
先枚举放在最前面的字符,将序列中这种字符的出现位置依次放到位置上去,同时统计一下代价,再令这一段区间加(可以把左端点直接设成)。这个可以直接差分,然后求一遍前缀和,再枚举下一个字符即可。
复杂度

D.955

暴力的做法就是每次求出家店的花费,sort一下取前个最小的。
正解是和nth_element(或者快速排序)类似的算法。
对于当前区间,随机选取一个元素作为基准数。然后维护两个指针,将区间中所有小于的元素放到的左边,大于的元素放到右边。这一步可以完成。
设结束时两个指针(即)在位置。左边元素都小于右边的元素都大于(可能等于,不影响答案)。
那么我们统计左边的元素个数,如果就递归到区间;否则答案加上左边的所有花费,-=,递归到区间
复杂度为。总复杂度

注意nth_element只有随机取才能保证不被卡掉。我造了几组数据,取midmid+1的应该都过不了。

E.树的直径Diameter

先考虑点不带权的情况。
一个结论:若边权为正,设两个集合的直径分别为,那么的直径一定是中的一种。
预处理表,我们可以用合并两个集合的直径。
考虑删掉条边,实际就是一棵大的子树中割掉了若干小的子树,也就是一段大的DFS序区间中扣掉了若干子区间,剩下的区间的并就是该连通块的DFS序区间。显然这些剩下的区间个数也是的。
而一个区间的直径可以用线段树求出。那么就可以解决了。
(具体一点,DFS序区间是互不相交的。观察发现它们可以构成一棵树的形态。把区间按右端点从小到大、左端点从大到小的顺序排序,拿栈维护出这棵树,在这棵树上DFS即可求出答案)
若点带权,仍可以这样做。证明可以考虑,将每个点的点权都加上一个很大的常数(不会改变直径两端点),然后每个点连向一个虚点,边权为此时的点权。
因为不需要修改,线段树可以换成查询(但是线段树也可以过,可能需要优化下常数)。
复杂度

F.染色Color

首先中必有两个数同色,而中任意两个不同元素的和,都是集合中的元素。所以是不合法的。所以有
于是我们可以先猜测,对任意正整数是合法的。
考虑怎么设计染色方案。
满足和小于或大于的数,可以都染同一种颜色。即满足:。不妨直接计算满足
的奇偶性讨论:

为奇数时:
,把染色为,把都染成
染色为
任意两个不同的同色数的和要么,要么,所以这是合法的。

为偶数时:
,把染色为,把都染成
染色为
同上,这也是合法的。
综上,

std:
A:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41771272
B:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41771280
C:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41771284
D:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41771289
E:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41771303
F:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41771323

全部评论

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

等你来战

查看全部

热门推荐