正題

題目鏈接:https://www.luogu.com.cn/problem/CF662C

---

題目大意

$n?m$的網(wǎng)格上有$0/1$，可以任意翻轉(zhuǎn)行和列，求剩下最少的$1$。

---

解題思路

知道是$FWT$之后就好做很多了。

首先因?yàn)?span id="ze8trgl8bvbq" class="katex--inline">$n$很小，所以可以考慮枚舉翻轉(zhuǎn)的行數(shù)，我們現(xiàn)在需要對(duì)于一個(gè)行的翻轉(zhuǎn)狀態(tài)快速知道最小值。

如果一行狀態(tài)$s$翻轉(zhuǎn)行狀態(tài)$w$之后就相當(dāng)于$val(sxorw)$反過來也就是若$c=sxorw$那么$sxorc=w$。

此時(shí)就可以上$FWT$了，設(shè)$va{l}_i$表示列狀態(tài)$i$的最小值，$nu{m}_i$表示列狀態(tài)$i$的數(shù)量。那么$$ans(s)=\sum _{ixorj=s}va{l}_i\times nu{m}_j$$

上$FWT$即可，時(shí)間復(fù)雜度$O(2^{n}n+nm)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=(1<<21); ll n,m,val[N],num[N],ans; char s[20][110000]; void FWT(ll *f,ll op){for(ll p=2;p<=n;p<<=1)for(ll k=0,len=p>>1;k<n;k+=p)for(ll i=k;i<k+len;i++){ll x=f[i],y=f[i+len];f[i]=(x+y)/op;f[i+len]=(x-y)/op;}return; } void solve(ll *a,ll *b){FWT(a,1);FWT(b,1);for(ll i=0;i<n;i++)a[i]=a[i]*b[i];FWT(a,2);return; } int main() {scanf("%lld%lld",&n,&m);for(ll i=0;i<n;i++)scanf("%s",s[i]);ll MS=(1<<n);for(ll i=1;i<MS;i++)val[i]=val[i-(i&-i)]+1;for(ll i=0;i<MS;i++)val[i]=min(val[i],n-val[i]);for(ll i=0;i<m;i++){ll w=0;for(ll j=0;j<n;j++)w+=(s[j][i]=='1')<<j;num[w]++;}n=MS;solve(val,num);ans=1e9;for(ll i=0;i<n;i++)ans=min(ans,val[i]);printf("%lld\n",ans); }

總結(jié)

以上是生活随笔為你收集整理的CF662C-Binary Table【FWT】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。