hihoCoder太阁最新面经算法竞赛2题解

1
0

Problem A

很经典的问题。可以证明如下结论:如果最多的时候有X个任务同时进行,那么需要最少的机器数目就是X。
我们可以把所有起止点按时间排序。如果时间相同,那么代表结束的点排在代表开始的点前。
之后按顺序扫描所有起止点。设置一个变量s,遇到开始点+1,遇到结束点-1。扫描过程中s的值就是此时同时进行的任务数目。s的最大值就是答案。

Problem B

DFS搜索出所有岛屿,同时把每个岛屿包含的像素坐标也保存起来并按照坐标排序。
岛屿数目和面积相同的岛屿数目很容易直接统计得到。
形状相同的岛屿数目我们可以通过逐一比较岛屿的每一个像素得到。当我们比较岛屿x和岛屿y时,如果每对像素的坐标差都相同,那么x和y的形状>就是相同的。

Problem C

我们可以把10进制小数0.X表示成Y / 10^n,其中n是X的位数;例如0.125可以表示成125/1000。然后我们把Y / 10^n化简成最简分数A / B。可以证 明0.X的二进制表示是有限的当且仅当B不包含因子5。
如果B不包含因子5,那B就只包含因子2,不妨设B = 2^m。此时我们把A表示成m位二进制数C(C可能包含前导0),那么0.C就是0.X的二进制表示。

2 answer(s)

0

Hi Dear. How are you? I hope fine, My name is Adelina,I work as an Senior Audit / banker, I wish us to become friends. Contact me with my mail: (adelinaserrano1980@gmail.com) Let us share details and photos. I expect your message.Thank Adelina

0

FANTASY

write answer 切换为英文 切换为中文


转发分享