题目链接
solution
因为(n)比较小,所以我们可以(2^n)枚举每一行是不是翻转。然后对于每一列答案就唯一了。
对于每一列状态压缩,用(b[i])表示(i)这个状态最小的(1)的个数(也就是这个状态里0和1更少的那个)。然后我们如果想把一列从状态(x)变成状态(y),那么我们需要操作的行就是(xotimes y)。用(a[i])表示(i)这个状态的数量。用(ans_x)表示操作的行为(x)这个状态的时候的答案,就有(ans_x=sumlimits_{iotimes j=x}a[x]b[y])。用(fwt)优化即可。
code
/* * @author: wxyww * @date: 2020-04-26 10:45:28 * @last modified time: 2020-04-26 11:21:07 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<ctime> using namespace std; typedef long long ll; const int n = 1 << 20; // #define int ll ll read() { ll x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); } return x * f; } char s[n]; int n,m; void fwt(ll *a,int xs) { for(int i = 0;i < n;++i) { for(int j = 0;j < (1 << n);++j) { if((j >> i) & 1) continue; ll l = a[j],r = a[j | (1 << i)]; a[j] = l + r;a[j | (1 << i)] = l - r; } } if(xs == -1) for(int i = 0;i < (1 << n);++i) a[i] /= (1 << n); } ll a[n],cnt[n],a[n],b[n]; int main() { n = read(),m = read(); for(int i = 1;i <= n;++i) { scanf("%s",s + 1); for(int j = 1;j <= m;++j) a[j] = (a[j] << 1) | (s[j] - '0'); } for(int i = 1;i <= m;++i) a[a[i]]++; for(int i = 0;i < (1 << n);++i) { cnt[i] = (cnt[i >> 1]) + (i & 1); b[i] = min(cnt[i],n - cnt[i]); } fwt(b,1);fwt(a,1); for(int i = 0;i < (1 << n);++i) a[i] = a[i] * b[i]; fwt(a,-1); ll ans = n * m; for(int i = 0;i < (1 << n);++i) { ans = min(ans,a[i]); } cout<<ans; return 0; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/599706.html