「CodeForces-1250E」The Coronation(2-SAT)

发表于 | 分类于 ，

「CodeForces-1250E」The Coronation

给定一系列01串，求翻转次数最小的情况下，令任意两个串有至少k位相同的合法方案

题意

给定$n$个长度为$m$的01串，可以对任意串进行翻转，求满足任意两个串至少有k位相同的翻转方案，并使翻转次数最小。

题解

2-SAT问题。

设串不翻转为0，翻转为1，则对于任意两个串都有如下四种情况：

  1. a,b和a,rev(b)相同位数均大于等于k，此时a,b相互之间没有限制；
  2. a,b相同之间位数大于等于k，a,rev(b)之间相同位数小于k，此时a,b必须相同，即XOR(a,b)=0;
  3. a,b相同之间位数小于等于k，a,rev(b)之间相同位数大于k，此时a,b必须相反，即XOR(a,b)=1;
  4. a,b和a,rev(b)相同位数均小于k，即无论怎么翻转都不能使a,b两者匹配；

一旦出现4，整组情况一定是无解的。

相当于原串所代表的点形成若干个联通块，每一个联通块中的元素颜色是相互联系的（即如果翻转一个，必须翻转该块中的所有元素）。

建完图后对点$i$和点$i+n$进行dfs，因为图的两侧完全对称，一定会搜出一组点完全相反的两种染色方案，只要选择翻转次数较小的那一组即可。注意在dfs时需要判奇环，如果出现奇环则无解。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
const int maxn = 100 + 10;
 
int n, m, k;
ll id[maxn];
char s[maxn];
vector<int> g[maxn];
bool vis[maxn];
int res[maxn];
 
inline ll getid(char s[], int len)
{
	ll res = 0;
	for(int i = 0; i < len; i ++)	if(s[i] - '0') res += (1ll << (len - i - 1));
	return res;
}
 
inline int check(ll a, ll b) { return m - __builtin_popcountll(a ^ b); }
 
inline void add(int a, int b) { g[a].push_back(b);  } 
 
inline void XOR(int a, int b, int c)
{
	 if(c == 0) add(a, b), add(a + n, b + n), add(b, a), add(b + n, a + n);
	else add(a, b + n), add(a + n, b), add(b, a + n), add(b + n, a);
}
 
inline void init()
{
	for(int i = 1; i <= (n << 1); i ++) vis[i] = res[i] =  0, g[i].clear();
}
 
int dfs(int u, vector<int> &res)
{
	vis[u] = true;
	int t = 0;
	res.push_back(u);
	for(auto v : g[u]) if(!vis[v]) t += dfs(v, res);
	return t + (u > n);
}
 
int main()
{
	int _;
	scanf("%d", &_);
	while(_ --)
	{
		scanf("%d%d%d", &n, &m, &k);
		init();
		for(int i = 1; i <= n; i ++)
		{
			scanf("%s", s);
			id[i] = getid(s, m);
			reverse(s, s + m);
			id[i + n] = getid(s, m);
		}
		bool flag = true;
		for(int i = 1; i <= n; i ++)
		{
			for(int j = i + 1; j <= n; j ++)
			{
				if(check(id[i], id[j]) < k && check(id[i], id[j + n]) < k) flag = false;
				else if(check(id[i], id[j]) >= k && check(id[i], id[j + n]) < k) XOR(i, j, 0);
				else if(check(id[i], id[j + n]) >= k && check(id[i], id[j]) < k) XOR(i, j, 1);
			}
		}
		vector<int> ans;
		for(int i = 1; i <= n; i ++) if(!vis[i])
		{
			vector<int> A, B;
			int a = dfs(i, A);
			for(auto j : A) if(j == i + n) flag = false;
			int b = dfs(i + n, B);
			if(a < b) { for(auto i : A) if(i > n) ans.push_back(i - n); }
			else { for(auto i : B) if(i > n) ans.push_back(i - n); }
		}
		if(!flag) { printf("-1\n"); continue; }
		printf("%d\n", ans.size());
		for(auto i : ans) printf("%d ", i);
		puts("");
	}
	return 0;
}