Codeforces1290C Prefix Enlightenment

tomaito

February 5, 2020

1158views

No comments

1031 words

ACM

题目链接: [Prefix Enlightenment](https://codeforces.com/contest/1290/problem/C)

任何3个集合的交集为空，这就说明了每个灯最多属于两个集合。题目保证能够使灯变亮。显然如果某个灯不被任何集合所控制，我们不用去考虑。我们先假设每个灯被两个集合所控制

如果某个灯原本就是亮的，那么控制该灯的两个集合要么同时翻转，要么都不翻转。如果某个灯原本就是暗的，那么控制改灯的两个集合必定是一个翻转，一个不翻转。
我们把每个集合抽象成一个点，然后每个点有两个属性:翻转和不翻转。然后根据上面讨论的情况，我们在控制该灯的集合的属性上连边。答案显然就是翻转的次数。可以用并查集来完成，这样我们就得到了每个连通块的大小，既是翻转的次数，我们取最小即可。

那么如果某个灯仅属于一个集合呢，这种情况下该集合是否翻转就可以根据灯的初始情况确定了，然后我们把该集合的对立情况连到代价为无穷的点去，保证不取这种情况。

```cpp

#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;
}
```

Last modification：February 5th, 2020 at 09:00 pm

如果觉得我的文章对你有用，请随意赞赏

Codeforces1290C Prefix Enlightenment