注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ2901]矩阵求和  

2015-01-05 20:05:48|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2901: 矩阵求和

Time Limit: 20 Sec  Memory Limit: 256 MB
Submit: 176  Solved: 73
[Submit][Status]

Description

给出两个n*n的矩阵,m次询问它们的积中给定子矩阵的数值和。

Input

第一行两个正整数n,m。
接下来n行,每行n个非负整数,表示第一个矩阵。
接下来n行,每行n个非负整数,表示第二个矩阵。
接下来m行,每行四个正整数a,b,c,d,表示询问第一个矩阵与第二个矩阵的积中,以第a行第b列与第c行第d列为顶点的子矩阵中的元素和。

Output

对每次询问,输出一行一个整数,表示该次询问的答案。

Sample Input

3 2
1 9 8
3 2 0
1 8 3
9 8 4
0 5 15
1 9 6
1 1 3 3
2 3 1 2

Sample Output

661
388
【数据规模和约定】
对30%的数据满足,n <= 100。
对100%的数据满足,n <= 2000,m <= 50000,输入数据中矩阵元素 < 100,a,b,c,d <= n。

Solution

好像直接求个前缀和就好了= =

Code

/**************************************************************
    Problem: 2901
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:13824 ms
    Memory:32368 kb
****************************************************************/
 
#include<cstdio>
int aa;char ch;int F(){
    while(ch=getchar(),ch<'0'||ch>'9');aa=ch-'0';
    while(ch=getchar(),ch>='0'&&ch<='9')aa=aa*10+ch-'0';return aa;
}
#define N 2010
int n,m,a[N][N],b[N][N],i,j,x0,y0,x1,y1;long long ans;
int main(){
    for(n=F(),m=F(),i=1;i<=n;i++)
    for(j=1;j<=n;j++)a[i][j]=a[i-1][j]+F();
    for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)b[i][j]=b[i][j-1]+F();
    for(;m--;printf("%lld\n",ans))
    for(ans=0,x0=F(),y0=F(),x1=F(),y1=F(),x0>x1?i=x0,x0=x1,x1=i:1,y0>y1?i=y0,y0=y1,y1=i:1,
    i=1;i<=n;i++)ans+=1LL*(a[x1][i]-a[x0-1][i])*(b[i][y1]-b[i][y0-1]);
}
  评论这张
 
阅读(86)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018