题解 P4030 【「CodePlus 2017 12 月赛」可做题1】

消失的海岸线 · 2018-01-12 21:47:24 · 题解

丢一下博客链

题意：定义一个 n 阶方阵是巧妙的当且仅当对于长度为 n 的排列 p，取这个方阵的如下 n 个元素：(i,p_i)，它们的和均相同。

注意到一个方阵是巧妙的当且仅当它的所有 2 阶子方阵都是巧妙的。

证明显然，因为如果有一处不巧妙一定存在两种排列的和不同。

维护二维前缀和即可。

    #include <cmath>
    #include <queue>
    #include <cstdio>
    #include <iomanip>
    #include <cstdlib>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    #define N 510
    #define ll long long
    using namespace std;
    inline int read()
    {
        int x=0,f=1;char ch=getchar();
        while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
        while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
        return x*f;
    }
    int n,m,T;
    int a[N][N],f[N][N],g[N][N];
    int ask_sum(int l,int r,int L,int R)
    {
        return g[L][R]-g[l-1][R]-g[L][r-1]+g[l-1][r-1];
    }
    int main()
    {
        n=read(),m=read(),T=read();
        for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)a[i][j]=read();
        for(int i=1;i<=n-1;i++)
        for(int j=1;j<=m-1;j++)f[i][j]=(a[i][j]+a[i+1][j+1]==a[i+1][j]+a[i][j+1]);
        for(int i=1;i<=n-1;i++)
        for(int j=1;j<=m-1;j++)g[i][j]=g[i-1][j]+g[i][j-1]-g[i-1][j-1]+f[i][j];
        while(T--)
        {
            int x=read(),y=read(),k=read();
            if(k==1)
            {
                puts("Y");
                continue ;
            }
            int sum=ask_sum(x,y,x+k-2,y+k-2);
            if(sum==(k-1)*(k-1))puts("Y");
            else puts("N");
        }
}