The Coronation（2019 ICPC Southern and Volga Russian Regional E题+ 2-Sat）

The Coronation

题意：

给定 $n$n个长度为 $m$m的 $01$01串，定义两个串相似：两个串对应位置相同的位置数量不小于某给定值 $k$k；可以通过反转字符串使得两个 $01$01串从不相似变成相似，求最少的反转次数使得所有的 $01$01串两两相似。

思路：

1. 刚看到这题时还想过网络流、双向bfs？QAQ，后面突然想到好像可以2-Sat，于是就A了。。。
2. 那怎样想到2-Sat呢？考虑到每个 $01$01串有两种状态，只能选其中一个；并且这些 $01$01串的状态受到其他 $01$01串的限制，很像2-Sat！
3. 2-Sat关键就是从“不能怎样”->“一定要那样”，也就是从模糊的条件推出必须满足的有向边。而这里先 $O(n^2\ast m)$O(n2∗m)预处理出所有这样的关系；对于任意两个 $01$01串处理出都不反转和一个反转这两种情况是否相似，若都不相似，说明这对 $01$01串没救了！直接退出程序输出 $-1$−1；若两种情况都满足相似，则说明这两个 $01$01串直接没有任何限制，不连边；剩下的就是只有一种情况相似，根据情况连双向边即可（为什么是双向边呢？其实是两条单向边的叠加）。
4. 现在最关键的问题来了，如何使得反转的 $01$01数量最少呢？考虑到前面连边的方式（双向边）导致不同的GCC之间没有任何边，也就是没有任何限制。因此对于每个没有确定的字符串，先随便确定它的状态进行 $dfs$dfs，若失败了，说明反转后也会失败！（这点很有趣）然后就可以直接退出程序输出 $-1$−1了。那如果成功了呢？怎样保证反转次数最少呢？单独考虑当前GCC，GCC的整体（包含的所有字符串）都反转，则当前GCC依然合法（毕竟都反转等于都不反转）；因此若当前GCC中选择反转的数量大于其包含点数的 $\frac{1}{2}$21​，则选择整体反转，这样就保证了反转的数量尽可能小啦。

代码

#include "bits/stdc++.h"
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0,f=1;char c=getchar();while(c!='-'&&(c<'0'||c>'9'))c=getchar();if(c=='-')f=-1,c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return f*x;}

const int maxn = 100+10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const double eps = 1e-7;

int n, m, k;
string s[maxn];
int head[maxn], to[maxn*maxn], nxt[maxn*maxn], tot;
int tmp[maxn], top;
bool choose[maxn];

inline void add_edge(int u, int v) {
    ++tot; to[tot]=v; nxt[tot]=head[u]; head[u]=tot;
    ++tot; to[tot]=u; nxt[tot]=head[v]; head[v]=tot;
}

bool dfs(int u) {
    if(choose[u^1]) return 0;
    if(choose[u]) return 1;
    choose[u]=1, tmp[++top]=u;
    for(int i=head[u]; i; i=nxt[i]) if(!dfs(to[i])) return 0;
    return 1;
}

void solve() {
    n=read(), m=read(), k=read();
    for(int i=0; i<2*n; ++i) head[i]=choose[i]=0; tot=0;
    for(int i=0; i<n; ++i) cin>>s[i];
    for(int i=0; i<n; ++i) {
        for(int j=i+1; j<n; ++j) {
            int c1=0, c2=0;
            for(int t=0; t<m; ++t) {
                if(s[i][t]==s[j][t]) c1++;
                if(s[i][t]==s[j][m-1-t]) c2++;
            }
            if(c1<k&&c2<k) return (void)printf("-1\n");
            if(c1>=k&&c2>=k) continue;
            else if(c1>=k) add_edge(2*i,2*j), add_edge(2*i+1,2*j+1);
            else if(c2>=k) add_edge(2*i,2*j+1), add_edge(2*i+1,2*j);
        }
    }
    vector<int> ans;
    for(int i=0; i<n; ++i) {
        if(choose[2*i]||choose[2*i+1]) continue;
        top=0;
        if(!dfs(2*i)) return (void)printf("-1\n");
        int rev_num=0;
        for(int j=1; j<=top; ++j) if(tmp[j]%2) rev_num++;
        if(rev_num>top/2) {
            for(int j=1; j<=top; ++j) if(tmp[j]%2==0) ans.push_back(tmp[j]/2+1);
        }
        else for(int j=1; j<=top; ++j) if(tmp[j]%2) ans.push_back(tmp[j]/2+1);
    }
    cout<<ans.size()<<endl;
    for(auto p: ans) printf("%d ", p);
    puts("");
}

int main() {
    int T=read();
    while(T--) solve();
}