A.乘积Product
,那么
可以用
unsigned long long
存,直接枚举即可。注意
。
也可以对每个算其贡献,答案是
。
B.求和Summation
到
可以表示,有
个位置,每个位置可以放一个球或者不放。设第一个球到
位置的距离为
。对
求和就是在所有情况中,
的和。
枚举第一个球在位置,那么贡献是
,所以答案就是
。
(发现能到,也不知道怎么评价难度...
于是只能扔到B了...)
是非负整数,请特判
,没有卡常的问题。
C.排序Sort
操作可以简化成,每次花费的代价交换相邻两个位置。
考虑枚举最终的字符串中每种字符的相对位置,然后依次将每个字符换到对应位置上去。
容易想到只考虑向左的代价,向右的不计算。事实上不对,比如AGCAG
,如果最终序列是AACGG
,会算出的花费,偏小...
将位置的字符放到
位置会影响
之间的字符(若
,则
的字符位置减
;否则会令
的字符位置
)。
先枚举放在最前面的字符,将序列中这种字符的出现位置依次放到
位置上去,同时统计一下代价,再令
这一段区间加
(可以把左端点直接设成
)。这个可以直接差分,然后求一遍前缀和,再枚举下一个字符即可。
复杂度。
D.955
暴力的做法就是每次求出家店的花费,
sort
一下取前个最小的。
正解是和nth_element
(或者快速排序)类似的算法。
对于当前区间,随机选取一个元素
作为基准数
。然后维护两个指针,将区间中所有小于
的元素放到
的左边,大于
的元素放到
右边。这一步可以
完成。
设结束时两个指针(即)在
位置。
左边元素都小于
,
右边的元素都大于
(可能等于,不影响答案)。
那么我们统计左边的元素个数
,如果
就递归到区间
;否则答案加上
左边的所有花费,
-=
,递归到区间
。
复杂度为。总复杂度
。
注意nth_element
中只有随机取才能保证不被卡掉。我造了几组数据,取
mid
和mid+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) 回帖