2020ICPC·小米网络选拔赛第一场 J题

短命女 2022-11-20 09:51 18阅读 0赞

[题目链接][Link 1]

链接：https://ac.nowcoder.com/acm/contest/7501/J  
来源：牛客网

题目：Matrix Subtraction  
分析：中等难度题，  
可以用差分来解决、也可以直接套二维树状数组的模板，也可以利用dp来解决  
注意，从头减到尾，注意矩形越界时的处理即可。

### AC代码： ###

![在这里插入图片描述][20201028151214276.png_pic_center]

#include <cstdio>
    #include <iostream>
    
    using namespace std;
    
    const int N = 1001;
    
    inline int getInt(void)
    {
        
        char c=getchar();
        int ret=0;
        while(c<'0' && c>'9')
        {
        
            c=getchar();
        }
        while(c>='0' && c<='9')
        {
        
            ret=ret*10+c-'0';
            c=getchar();
        }
        return ret;
    }
    
    int f[N][N],g[N][N];
    
    inline int getsum(int x0,int y0,int x1,int y1)
    {
        
        return g[x1][y1]-g[x0-1][y1]-g[x1][y0-1]+g[x0-1][y0-1];
    }
    
    bool solve(void)
    {
        
        int n=getInt(),m=getInt(),a=getInt(),b=getInt();
        for(int i=1;i<=n;++i)
        {
        
            for(int j=1;j<=m;++j)
            {
        
                f[i][j]=getInt();
    
            }
        }
        for(int i=1;i<=n;++i)
        {
        
            for(int j=1;j<=m;++j)
            {
        
                g[i][j]=g[i][j-1]+g[i-1][j]-g[i-1][j-1];
                f[i][j]-=getsum(max(1,i-a+1),max(1,j-b+1),i,j);
                if(f[i][j]<0)
                    return false;
                if((i+a-1>n || j+b-1>m) && f[i][j]>0)
                {
        
                    return false;
                }
                g[i][j]+=f[i][j];
            }
        }
        return true;
    }
    
    
    int main()
    {
        
        for(int i=getInt();i;--i)
        {
        
            if(solve())
            {
        
                puts("^_^");
            }
            else
            {
        
                puts("QAQ");
            }
        }
        return 0;
    }

[Link 1]: https://ac.nowcoder.com/acm/contest/7501/J
[20201028151214276.png_pic_center]: /images/20221120/ba2f52c7ba464556a4549bbe9a80c4c6.png