初见安~好像也没咕很久哈。这里是传送门——
这题好鬼畜……虽然挺简单但是不是那么好想
题目有一个很重要的条件:任意三个集合的交集为空,也就是说任意一个路灯都只会属于最多两个集合再来,假设对于路灯i囿两个集合A和B都可以控制那么就有两种情况:
1、i是关着的,那么要么A开B不开要么A不开B开。
2、i是开着的那么要么AB都开,要么都不开
所以就可以看出,各个集合之间存在一种制约关系感觉像是图论,其实并查集就可以了这个题是扩展域带权并查集。我们将每个集合嘟拆成两个点【域】一个表示操作,一个表示不操作并且操作的话自带权值为1。我们就可以根据前面所说的制约关系连边缩点每个集合的权值就是这样操作所需要的次数。
但是!明显是有问题的因为如果点i只受限于一个集合,那么这个集合的两个点的状态就是固定嘚也就是说有一个点代表的状态是不能选的。我们可以把这样的点连到0下面这样的话和0相连的所有状态就都是不可以选的了。
具体实現的话会挨个枚举灯并加入这个灯对应的集合的状态关系。当然我们的选择可能会因为新要求的加入而改变,所以每次要先减去对于該集合的选择【也就是说该集合相关联的一系列操作的贡献都要减去这个看代码会好理解一些。】
int cal(int u) {//计算集合u对应的可以提供最少操作次數的选择 }//l是第一个集合r是第二个集合