HBC20470[ZJOI2007]HIDE 捉迷藏题解

凌晚轩算法基础篇 2023-11-25 16:23:01 84 0

全网最全C++题库，助您快速提升编程技能！题库丰富多样，涵盖各个领域，让您在练习中不断成长！

捉迷藏 Jiajia和Wind是一对恩爱的夫妻，并且他们有很多孩子，某天，Jiajia、Wind和孩子们决定在家里玩捉迷藏游戏，他们的家很大且构造很奇特，由N个屋子和N-1条双向走廊组成，这N-1条走廊的分布使得任意两个屋子都互相可达，游戏是这样进行的，孩子们负责躲藏，Jiajia负责找，而Wind负责操纵这N个屋子的灯，在起初的时候，所有的灯都没有被打开，每一次，孩子们只会躲

捉迷藏 Jiajia和Wind是一对恩爱的夫妻，并且他们有很多孩子。某天，Jiajia、Wind和孩子们决定在家里玩捉迷藏游戏。他们的家很大且构造很奇特，由N个屋子和N-1条双向走廊组成，这N-1条走廊的分布使得任意两个屋子都互相可达。游戏是这样进行的，孩子们负责躲藏，Jiajia负责找，而Wind负责操纵这N个屋子的灯。在起初的时候，所有的灯都没有被打开。每一次，孩子们只会躲藏在没有开灯的房间中，但是为了增加刺激性，孩子们会要求打开某个房间的电灯或者关闭某个房间的电灯。为了评估某一次游戏的复杂性，Jiajia希望知道可能的最远的两个孩子的距离（即最远的两个关灯房间的距离）。我们将以如下形式定义每一种操作： C(hange) i 改变第i个房间的照明状态，若原来打开，则关闭；若原来关闭，则打开。 G(ame) 开始一次游戏，查询最远的两个关灯房间的距离。