题解 | #F差异#->最大子串的应用

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
using namespace std;
const int mod=1e9+7;
typedef pair<int,int>pii;
const int N=3e5;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int num[N],inv[N];//阶乘以及阶乘的逆元
//ans=num[a]*inv[a-b]%mod*inv[b]%mod;
int kmi(int a,int b){
    int res=1;
    while(b){
        if(b&1)res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return res;
}

void init(){
     num[0]=1,inv[0]=1;
    for(int i=1;i<=2e5;i++){//预处理出2e5内的阶乘以及其逆元
        num[i]=num[i-1]*i%mod;
        inv[i]=kmi(num[i],mod-2);
    }
}
//最大子段和
void solve(){
    int n,m;cin>>n>>m;
    vector<string>s(n+1);
    vector<int>sum0(m+1),sum1(m+1);
    for(int i=1;i<=n;i++){
        cin>>s[i];
        s[i]=" "+s[i];
        for(int j=1;j<=m;j++){
            if(s[i][j]=='0') sum0[j]++;
            else sum1[j]++; 
        }
    }
    for(int i=1;i<=n;i++){
        vector<int>a(m+10);
        int ans=0;
        for(int j=1;j<=m;j++){
            if(s[i][j]=='0'){
                //原来的贡献->cnt1 现在的贡献->cnt0
                int cnt0=sum0[j]-1;
                int cnt1=sum1[j];
                ans+=cnt1;
                a[j]=-(cnt0-cnt1);
            }
            else{
                int cnt0=sum0[j];
                int cnt1=sum1[j]-1;
                ans+=cnt0;
                a[j]=-(cnt1-cnt0);
            }
        }
        //最大字串和
        /*
        将实际的贡献增加量变成自己的相反数->（原来的ans可以减去多少）
        然后进行最大子串和的模板即可求出贡献可以减少的最大值（原来的ans最多可以减去多少）
        */
        vector<int>dp(m+10);
        dp[0]=0;
        int maxx=0;//答案可以减去的最大值
        for(int j=1;j<=m;j++){
            dp[j]=max(dp[j-1]+a[j],0LL);
            maxx=max(dp[j],maxx);
        }
        cout<<ans-maxx<<endl;
    }
}
signed main(){
    ios_base::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
    int T=1;cin>>T;
    while(T--){
        solve();
       // cout<<endl;
    }
    return 0;
}