黑块小,删除的数字就少;黑块大,黑块数量就少;黑块大小取中间,勉强不超时。

#include <stdio.h>
#define N 305
int n, m, i, j, k, x, y, s, a[N][N], c[N];
void cal(int n, int m, int s){
    int i, j, k, v[N];
    for(i=0; i<N; i++) v[i] = c[i];
    for(i=1; i<=x; i++){
        for(j=1; j<=y; j++){
            if(--v[a[n+i][m+j]] == 0) s--;
        }//一个数字删除到没有,减少一种数字
    }
    printf("%d ", s);
}
int main(){
    scanf("%d%d%*d%d%d", &n, &m, &x, &y);
    for(i=1; i<=n; i++){
        for(j=1; j<=m; j++){
            scanf("%d", &a[i][j]);
            if(++c[a[i][j]] == 1) s++;
        }
    }
    for(i=0; i<=n-x; i++){
        for(j=0; j<=m-y; j++){
            cal(i, j, s);
        }//暴力删除涂黑的数字
        printf("\n");
    }
    return 0;
}

kangly时间复杂度好,但比较恶心的代码:

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <math.h>
#include <deque>
#include <set>
#define in(x) freopen(#x".in","r",stdin)
#define out(x) freopen(#x".out","w",stdout)
#define make(x) freopen(#x".in","w",stdout)
#define ll long long

using namespace std;

inline int read()
{
    int s=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=s*10+ch-'0';
        ch=getchar();
    }
    return s*f;
}
int f[310][310][310],H,W,n,h,w,a[310][310],sum[310][310][310];
int main()
{
    H=read(),W=read(),n=read(),h=read(),w=read();
    for(int i=1,j;i<=H;i++) for(j=1;j<=W;j++) a[i][j]=read();
    for(int i=1,j,k;i<=H;i++)
        for(j=1;j<=W;j++)
            for(k=1;k<=n;k++)
                sum[i][j][k]=sum[i-1][j][k]+sum[i][j-1][k]-sum[i-1][j-1][k]+(a[i][j]==k);
    for(int i=1,j,k,ans;i<=H-h+1;i++){
        for(int j=1;j<=W-w+1;j++){
            ans=0;
            for(int k=1;k<=n;k++){
                if(sum[H][W][k]-(sum[i+h-1][j+w-1][k]-sum[i-1][j+w-1][k]-sum[i+h-1][j-1][k]+sum[i-1][j-1][k])!=0) ans++;
            }
            printf("%lld ",ans);
        }
        puts("");
    }
    return 0;
}

作者 crxis

发表回复