C++14(g++5.4) 解法, 执行用时: 755ms, 内存消耗: 480K, 提交时间: 2020-06-08 23:43:13

#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<sstream>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<cmath>
#include<stack>
#include<set>
#include<map>
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define per(i,n,x) for(int i=n;i>=x;i--)
#define sz(a) int(a.size())
#define rson mid+1,r,p<<1|1
#define pii pair<int,int>
#define lson l,mid,p<<1
#define ll long long
#define pb push_back
#define mp make_pair
#define se second
#define fi first
using namespace std;
const double eps=1e-8;
const int mod=1e9+7;
const int N=1e5+10;
const int inf=1e9;
int T,n,m,K;
char s[110][110];
int a[110],b[110][11];
int main(){
    ios::sync_with_stdio(false);
    //freopen("in","r",stdin);
    cin>>T;
    while(T--){
        cin>>n>>m>>K;
        rep(i,1,n) cin>>s[i]+1;
        ll ans=0;
        rep(i,1,n){
            rep(j,1,m) a[j]=0;
            rep(j,i,n){
                rep(k,1,m){
                    if(s[j][k]=='1') a[k]++;
                    rep(p,0,9) b[k][p]=b[k-1][p];
                    if(s[i][k]==s[j][k]) b[k][s[i][k]-'0']++;
                }
                if(j==i) continue;
                int now=0,cnt=0;
                for(int k=1;k<=m;k++){
                    if(now<k){
                        now=k;
                        cnt=0;
                    }
                    while(now<=m&&cnt+a[now]<=K){
                        cnt+=a[now];
                        if(s[i][now]==s[j][now]&&now>k) ans+=b[now-1][s[i][now]-'0']-b[k-1][s[i][now]-'0'];
                        now++;
                    }
                    if(now>k) cnt-=a[k];
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 469ms, 内存消耗: 608K, 提交时间: 2020-06-07 16:10:50

#include<bits/stdc++.h>
using namespace std;
const int N=105;
int n,m,k,a[N][N],b[N],c[N],z[N][10];
char s[N][N];
int solve()
{
    int ans=0;
    for(int i=1;i<=m;i++)
    {
        b[i]+=b[i-1];
        for(int j=0;j<10;j++)
            z[i][j]=z[i-1][j]+(c[i]==j);
    }
    for(int i=1,j=1;i<=m;i++)
    {
        while(j<=m&&b[j]-b[i-1]<=k) j++;
        assert(j>=i);
        if(j-1>=i&&c[i]!=-1)
        {
            ans+=z[j-1][c[i]]-z[i][c[i]];
        }
    }
    assert(ans>=0);
    return ans;
}
int main()
{
    int t;scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&n,&m,&k);
        for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
        {
            a[i][j]=(s[i][j]=='1')+a[i-1][j];
            //assert(s[i][j]=='0'||s[i][j]=='1');
        }
        long long ans=0;
        for(int i=1;i<=n;i++)
            for(int j=i+1;j<=n;j++)
        {
            for(int k=1;k<=m;k++)
                b[k]=a[j][k]-a[i-1][k],c[k]=(s[i][k]!=s[j][k])?-1:(s[i][k]-'0');
            ans+=solve();
        }
        printf("%lld\n",ans);
    }
}