关注
第四题:
对于每枚棋子它最终所在列只和它初始所在列、左右操作有关;它最终所在行只和它初始所在行、上下操作有关。于是将上下操作抽取出来、左右操作抽取出来分开处理。
求列的值(只考虑左右操作):
记"左" 对答案的影响为 -1
记"右" 对答案的影响为 1
然后遍历所有的左右操作,对操作统计一个前缀和sum。如果第 i 列+ sum < 1,那么它的结果将和第 i+1列相同,并查集合并第 i 列和第 i +1 列(将第 i 列合并到第 i+1 列);如果第 i 列 + sum >Y,那么它的结果将和第 i-1列相同,并查集合并第 i列和第 i-1列(将第 i 列合并到第 i-1 列)。那么第 i 列最后的结果就是它的祖先初始所在列+sum(祖先没有被合并,说明祖先并不会“碰壁”)。
特殊情况:合并到只剩一个列了,说明所有列的结果都相同,直接暴力模拟一遍左右操作对该列的影响即可。
求行的值同上。
查看原帖
2 评论
相关推荐
点赞 评论 收藏
转发
投票
投递奇瑞汽车等公司7个岗位
点赞 评论 收藏
转发
牛客热帖
正在热议
# 牛客帮帮团来啦!有问必答 #
346143次浏览 7203人参与
# 你更愿意参加线上面试还是线下面试? #
4370次浏览 68人参与
# 晒一晒我的offer #
2758858次浏览 49446人参与
# 如何确定求职岗位 #
100652次浏览 2389人参与
# 华为求职进展汇总 #
432397次浏览 4346人参与
# 机械人怎么评价今年的华为 #
48781次浏览 398人参与
# 第一次面试 #
13474次浏览 205人参与
# 非技术岗薪资爆料 #
4507次浏览 95人参与
# 如果再来一次,你还会学硬件吗 #
16662次浏览 329人参与
# 海信求职进展汇总 #
6759次浏览 90人参与
# 通信硬件薪资爆料 #
136228次浏览 965人参与
# 来聊聊机械薪资天花板是哪家 #
17841次浏览 136人参与
# 找工作,你会甘心进小厂还是猛冲大厂 #
21971次浏览 211人参与
# 除了offer,现在你还缺点啥? #
1972次浏览 44人参与
# 应届生应该先就业还是先择业 #
10596次浏览 103人参与
# 百度工作体验 #
18935次浏览 205人参与
# 通信硬件人笔面经互助 #
62371次浏览 1391人参与
# 讲讲我经历过的年终奖 #
5784次浏览 76人参与
# 软件开发薪资爆料 #
533656次浏览 9198人参与
# 租房前辈的忠告 #
19677次浏览 1575人参与