【LIbreOJ】#6256. 「CodePlus 2017 12 月赛」可做题1
2024-08-25 13:49:48
【题意】定义一个n阶正方形矩阵为“巧妙的”当且仅当:任意选择其中n个不同行列的数字之和相同。
给定n*m的矩阵,T次询问以(x,y)为左上角的k阶矩阵是否巧妙。n,m<=500,T<=10^5。
【算法】数学
【题解】
可以证明每个矩阵是巧妙的当且仅当其每个2阶子矩阵均是巧妙的:
必要性:若该矩阵有一个不巧妙的2阶子矩阵,则其他部分选择相同的情况下(不涉及此两行列),这两行列的和不同,所以该矩阵不是巧妙的。
观察一个巧妙的2阶子矩阵
a1 a2
b1 b2
由a1+b2=a2+b1,可得
a2-a1=b2-b1(列间差分相等)
b1-a1=b2-a2(行间差分相等)
充分性:若该矩阵每个2阶子矩阵都是巧妙的,则其行差分的列差分均为0(行差分相等和列差分相等)。
重定义每个数字为Mij=ai+bj,表示A(i,j)和A(i-1,j-1)的列差分和行差分分别为ai和bj,这样的矩阵不论如何选择排列,和均为Σai+Σbj,1<=i,j<=k,所以该矩阵是巧妙的。
维护二维前缀和即可。
#include<cstdio>
#define rep(i,j,k) for(int i=j;i<=k;i++)
int a[][],f[][],n,m,T,x,y,k;
int main(){
scanf("%d%d%d",&n,&m,&T);
rep(i,,n)rep(j,,m)scanf("%d",&a[i][j]);
rep(i,,n-)rep(j,,m-)f[i][j]=f[i][j-]+(a[i][j]+a[i+][j+]!=a[i+][j]+a[i][j+]);
rep(i,,n-)rep(j,,m-)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-]>)puts("N");else puts("Y");
}
}
最新文章
- MailKit---获取邮件
- Mvc中Session导致action不异步的问题
- SpringBoot Schedule 配置
- Java(一)
- 如何理解JS回调函数
- 如何给zencart安装image handler插件?
- Windows2000安装Winform Clickonce提示升级系统版本的解决方案
- SparkSQL基础应用(1.3.1)
- Android手机分辨率基础知识(DPI,DIP计算)
- vi/vim使用指北 ---- Sample Editing
- gitignre
- java设计模式--结构型模式--装饰模式
- Linux 内核无线子系统
- C#,ASP.NET简单的MD5加密,解密
- jq常用功能操作
- docker-ce-17.09 数据卷和数据卷容器
- 开源项目管理工具KanBoard
- (字典树)How many--hdu--2609
- 批处理bat一键安装APK
- 【BZOJ3470】Freda’s Walk 概率与期望