揽月摘星辰

题解

/ 注册

全部文章 / 题解（共3篇）

C-路径难题题解

C-路径难题分析显而易见，这是一道图论中的最短路问题。发现n和m很大，但q<=10，且没有负边，所以基本可以确定是dijkstra了。分析这道题的特别之处：存在公交车系统，与出租车系统的收费方式不相同。考虑朴素的想法，显然我们可以给每一路公交车的所有站点两两连边，但显然对于大数据...

2020-10-30

2 850

B-艰难睡眠题解

B-艰难睡眠分析最开始看到题目时我是完全没有一点思路的，直到题面更新发现必须睡连续的时间。。。。再考虑到一天最多有2000分钟，k也是固定的，很自然的就可以想到可以枚举在哪段时间里睡觉，然后将所有人的吵闹时间移动至这段时间之外即可。然后考虑怎么优化。发现当我确定了睡眠的时间段后，每个人可选的...

2020-10-30

2 850

牛半仙的妹子图题解

牛半仙的妹子图分析：考场看题首先判断是道图论，然后发现因为困难程度接受度是单增的，所以当前能走的边以后一定能走，所以便考虑走到每个类型的妹子家的最小困难度。因为每段路径的限制是这条路径上最大的困难度，所以是典型的最小生成树问题。找出最小生成树后树上遍历一遍即可求出分别能去每个点的最小接受程度...

2020-10-23

1 665