B. Coffee Chicken 链接:登录—专业IT笔试面试备考平台_牛客网 来源:牛客网 题目描述 Dr. JYY has just created the Coffee Chicken strings, denoted as S(n). They are quite similar to the Fibonacci soup --- today's soup is made by m
Metropolis 题意: p p p个点 m m m条无向边,对于这 p p p个点,问距离其它点最近的距离。 题解:首先,如果我们考虑最暴力的方法, p p p次单源最短路。但是 p p p的大小有 2 e 5 2e5 2e5,明显是不可能了。那就考虑多源最短路吧。将这 p p p个点都加入队列作为源点。对于每一个节点,我们记录它是由哪一个源点扩展出来的。当从一个源点 i i i,扩展到
链接:https://www.nowcoder.com/acm/contest/204/E 来源:牛客网 题目描述 小 Bo 是某省乒乓球名列前茅的选手,现在他有 n 颗乒乓球一字排开,第 i 颗乒乓球的权值为 wi 每次他会随机从现有的乒乓球中等概率选一颗拿走,然后得到的收益是这颗球左边第一个乒乓球和右边第一个乒乓球的权值的乘积,如果左边没有乒乓球或者右边没有乒乓球,则收益为 0,这个过
题目链接:传送门 题目大意: 给出两条平行线和 n n n个圆,计算从一条线走到另一条线所消耗的体力。同时,在线上、圆上、园内走不消耗体力,求体力的最小花费。 解题思路: 一开始没想到是最短路,后来仔细一想,除了最短路也没啥其他的了。将线和圆都想象成一个个点,每个点之间的距离满足以下关系: L L L 1 1 1 到 L L L 2 2 2 之间连边权值 ∣ C 1 −