题解：AT_abc396_g [ABC396G] Flip Row or Col

思路

我们先转换一下题意：给你一个数组

a

包含

n

个长度为

m

的二进制数，让你找出一个二进制数

s

满足

\sum{\min(\operatorname{popcount}(a_i\operatorname{xor} s),m-\operatorname{popcount}(a_i\operatorname{xor} s))}

的值最小，并且输出那个值。

我们定义

f_{s,i}

表示对于二进制数

s

和数字

i

来说，

a

中有多少个数字和

s

的汉明距离恰好为

i

。

最后转移的式子如下：

f_{s,i}=\frac{1}{i}\times\sum_{\operatorname{popcount}(t\operatorname{xor} s)=1}{\sum_{k=0}^{i-1}{[k和i不同奇偶]\times f_{t,k}-[k和i同奇偶]\times f_{s,k}}}

当然这个式子还是太抽象了，大概说一下含义。

假设每个二进制数都是一个点，然后与之汉明距离为

1

的点连一条边，再设置该点权值为

a

中出现多少次该点，那么

f_{s,i}

就是距离

s

为

i

的点的权值之和。

我们先加上

\sum{f_{t,i-1}}

的值，发现算重了走过

s

的路径，所以减去

m\times\sum{f_{s,i-2}}

，后面以此类推。

然而算完之后却发现多算了好多。这是因为对于每条路径，都有

i

种开始的方法，也就是乘上

\frac{1}{i}

就可以了。

最终复杂度

O(2^M\times M^3)

，当然显然可以优化掉一个

M

，但没必要。

CPP

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=18,inf=1e18;
int n,m,f[(1<<N)+2][N+2];
int ans;
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);
	cin>>n>>m;
	ans=inf;
	for(int i=1;i<=n;i++){
		int x=0;
		for(int j=1;j<=m;j++){
			char y;cin>>y;
			x=(x<<1)|(y-'0');
		}
		f[x][0]++;
	}
	for(int i=1;i<=m;i++){
		for(int s=0;s<1<<m;s++){
			for(int j=1;j<=m;j++){
				int t=s^(1<<j-1);
				for(int k=i-1;k>=0;k--){
					if((i^k)&1)f[s][i]+=f[t][k];
					else f[s][i]-=f[s][k];
				}
			}
			f[s][i]/=i;
		}
	}
	for(int s=0;s<1<<m;s++){
		int num=0;
		for(int i=0;i<=m;i++)num+=min(i,m-i)*f[s][i];
		ans=min(ans,num);
	}
	cout<<ans<<"\n";
	return 0;
}

顺带，这题评紫真的合适吗……

题解：AT_abc396_g [ABC396G] Flip Row or Col

文章操作

思路

相关推荐

评论

题解：AT_abc396_g [ABC396G] Flip Row or Col