Nearest Opposite Parity

题目链接

题意:给定序列a[],每个a[i]代表到达这点是可以跳转至i+a[i]和i-a[i],要求求出每个点出发,至少要跳转几次才能使跳转后的点a[j]和这个点a[i]奇偶性不同。
思路:这里就是设两个超级源点,超级源点是最短路里面衍生出来的技巧,不知道可以点这个看,一个连接所有偶数,一个连接所有奇数,然后这些数之间,反向建边,比如从奇数点出发,那么从超级奇数点到任何一个偶数点的最短距离都代表他所能到某一个奇数点最短距离(反向思维).所以过程就是分别建立两个超级源点,可以一个下标0,一个下标n+1,然后把0指向所有偶数点,n+1指向所有奇数点,数之间反向建边,然后就是分别求0出发的最短路和n+1出发的最短路,用spfa和dijkstra都行。

全部评论

相关推荐

10-25 12:05
已编辑
湖南科技大学 Java
若梦难了:我有你这简历,已经大厂乱杀了
点赞 评论 收藏
分享
Yushuu:你的确很厉害,但是有一个小问题:谁问你了?我的意思是,谁在意?我告诉你,根本没人问你,在我们之中0人问了你,我把所有问你的人都请来 party 了,到场人数是0个人,誰问你了?WHO ASKED?谁问汝矣?誰があなたに聞きましたか?누가 물어봤어?我爬上了珠穆朗玛峰也没找到谁问你了,我刚刚潜入了世界上最大的射电望远镜也没开到那个问你的人的盒,在找到谁问你之前我连癌症的解药都发明了出来,我开了最大距离渲染也没找到谁问你了我活在这个被辐射蹂躏了多年的破碎世界的坟墓里目睹全球核战争把人类文明毁灭也没见到谁问你了😆
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务