自动搬运

查看原文

来自洛谷，原作者为

	消失的海岸线 **

搬运于2025-08-24 21:55:45，当前版本为作者最后更新于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");
        }
}