题目链接: Prefix Enlightenment
任何3个集合的交集为空,这就说明了每个灯最多属于两个集合。题目保证能够使灯变亮。显然如果某个灯不被任何集合所控制,我们不用去考虑。我们先假设每个灯被两个集合所控制
如果某个灯原本就是亮的,那么控制该灯的两个集合要么同时翻转,要么都不翻转。如果某个灯原本就是暗的,那么控制改灯的两个集合必定是一个翻转,一个不翻转。
我们把每个集合抽象成一个点,然后每个点有两个属性:翻转和不翻转。然后根据上面讨论的情况,我们在控制该灯的集合的属性上连边。答案显然就是翻转的次数。可以用并查集来完成,这样我们就得到了每个连通块的大小,既是翻转的次数,我们取最小即可。
那么如果某个灯仅属于一个集合呢,这种情况下该集合是否翻转就可以根据灯的初始情况确定了,然后我们把该集合的对立情况连到代价为无穷的点去,保证不取这种情况。
#include<bits/stdc++.h>
#define SZ( v ) ((int)(v).size())
using namespace std;
typedef long long ll;
const int N = 6e5 + 10
const int inf = 0x3f3f3f3f;
vector < int > G[N];
int n , k , fa[N] , cnt[N];
char s[N];
int get ( int x ) {
if ( x == fa[x] ) return x;
return fa[x] = get ( fa[x] );
}
int getmin ( int x ) {
return min ( cnt[get ( x )] , cnt[get ( x + k )] );
}
void merge ( int u , int v ) {
u = get ( u ) , v = get ( v );
if ( u != v ) {
fa[u] = v;
cnt[v] += cnt[u];
}
}
int main () {
scanf ( "%d%d%s" , &n , &k , s + 1 );
for ( int i = 1 ; i <= k ; ++ i ) {
int c , x;
scanf ( "%d" , &c );
while ( c -- ) {
scanf ( "%d" , &x );
G[x].push_back ( i );
}
fa[i] = i; // 翻转
fa[i + k] = i + k;//不翻转
cnt[i] = 1;
}
int ed = 2 * k + 1; // 只有一个点连接到这个点
fa[ed] = ed;
cnt[ed] = inf; // 代价设为无穷,保证不取这个点
int ans = 0;
for ( int i = 1 ; i <= n ; ++ i ) {
if ( SZ( G[i] ) == 1 ) {
int u = G[i][0] + k * ( s[i] == '0' ); //不取的情况的编号
ans -= getmin ( G[i][0] );
merge ( u , ed );
ans += getmin ( G[i][0] );
} else if ( SZ( G[i] ) == 2 ) {
int u = G[i][0] , v = G[i][1];
if ( s[i] == '1' ) {
if ( get ( u ) != get ( v ) ) {
ans -= getmin ( u );//每次都要减去之前的
ans -= getmin ( v );
merge ( u , v );
merge ( u + k , v + k );
ans += getmin ( u );//再加上新的
}
} else {
if ( get ( u ) != get ( v + k ) ) {
ans -= getmin ( u );
ans -= getmin ( v );
merge ( u + k , v );
merge ( u , v + k );
ans += getmin ( u );
}
}
}
printf ( "%d\n" , ans );
}
return 0;
}