洛谷4030(Codeplus11月月赛)可做题1

时间:2022-06-29 02:00:42

题目:https://www.luogu.org/problemnew/show/P4030

原来一个方阵巧妙的充要条件是该方阵的每个2*2子方阵都是巧妙的!!!

可以把每一行选的列视为一个排列,需要任意交换排列中两个数而代表的和不变。

比如第1个和第2个能交换,即前两列巧妙;前两列巧妙就是前两列的每个2*2子方阵巧妙。

  比如两行中第1个和第2个能交换即左边第一个2*2巧妙,第2个和第3个能交换即左边第二个2*2巧妙;满足这两条而这样第1个和第3个也能交换了!

1.可以把“以该点为右下角的2*2巧妙”记作这个点为1,然后求最大连续1的方阵;

2.可以记录“以该点为右下角的矩形中有几个不巧妙的2*2”,然后判断,如代码。

#include<iostream>
#include<cstdio>
using namespace std;
int n,m,t,f[][],a[][],x,y,k;
int main()
{
scanf("%d%d%d",&n,&m,&t);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
scanf("%d",&a[i][j]);
if(i>=&&j>=)f[i][j]=f[i][j-]+(a[i][j]+a[i-][j-]!=a[i-][j]+a[i][j-]);
}
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
f[i][j]+=f[i-][j];
while(t--)
{
scanf("%d%d%d",&x,&y,&k);
if(f[x+k-][y+k-]-f[x][y+k-]-f[x+k-][y]+f[x][y])printf("N\n");
else printf("Y\n");
}
return ;
}