T1:矩阵乘法板子题,练手。

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long inline int gi()
{
bool b=; int r=; char c=getchar();
while(c<'' || c>'') { if(c=='-') b=!b; c=getchar(); }
while(c>='' && c<='') { r=r*+c-''; c=getchar(); }
if(b) return -r; return r;
} const int inf = 1e9+, N = ;
int f[][N][N],I,J,K; int main()
{
int i,j,k;
I=gi(), K=gi();
for (i=; i<=I; i++)
for (k=; k<=K; k++)
f[][i][k]=gi();
K=gi(), J=gi();
for (k=; k<=K; k++)
for (j=; j<=J; j++)
f[][k][j]=gi();
for (i=; i<=I; i++)
for (j=; j<=J; j++)
for (k=; k<=K; k++)
f[][i][j]+=f[][i][k]*f[][k][j];
for (i=; i<=I; i++)
{
for (j=; j<=J; j++)
printf ("%d ",f[][i][j]);
printf ("\n");
}
return ;
}

T2:矩阵乘法的小优化。

因为题目只要求答案矩阵的某一子矩阵所有元素和,根据矩乘定义可知:

C(i,j) =  A(i,1) *  B(1,j) +  A(i,2) *  B(2,j) +  ... + A(i,n) *  B(n,j)    ——①

C(i,j+1) =  A(i,1) *  B(1,j+1) +  A(i,2) *  B(2,j+1) +  ... + A(i,n) *  B(n,j+1)    ——②

C (i+1,j) =  A(i+1,1) *  B(1,j) +  A(i+1,2) *  B(2,j) +  ... + A(i+1,n) *  B(n,j)    ——③

C(i+1,j+1) =  A(i+1,1) *  B(1,j+1) +  A(i+1,2) *  B(2,j+1) +  ... + A(i+1,n) *  B(n,j+1)    ——④

① + ② + ③ + ④ 可得:

子矩阵所有元素和  =   ∑ (A矩阵第 i 列之和  *  B矩阵第 i 行之和)

(建议手玩一个小矩阵帮助理解)

所以可 O (n * m) 解决。

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long inline ll gi()
{
bool b=; ll r=; char c=getchar();
while(c<'' || c>'') { if(c=='-') b=!b; c=getchar(); }
while(c>='' && c<='') { r=r*+c-''; c=getchar(); }
if(b) return -r; return r;
} const int inf = 1e9+, N = ;
int n,m;
ll f[][N][N],sum[N][N]; int main()
{
n=gi(), m=gi();
int i,j,x,y,q,w,a,b,c,d;
ll ans;
for (i=; i<=n; i++)
for (j=; j<=n; j++)
f[][i][j]=gi(), f[][i][j]+=f[][i-][j];
for (i=; i<=n; i++)
for (j=; j<=n; j++)
f[][i][j]=gi(), f[][i][j]+=f[][i][j-];
for (i=; i<m; i++)
{
x=gi(), y=gi(), q=gi(), w=gi(); ans=;
a=max(x,q), b=max(y,w), c=min(x,q), d=min(y,w);
for (j=; j<=n; j++)
ans+=(f[][a][j]-f[][c-][j]) * (f[][j][b]-f[][j][d-]);
printf ("%lld\n",ans);
}
return ;
}

最新文章

  1. [数据科学] 从text, json文件中提取数据
  2. VPS服务商
  3. 基于SignalR的小型IM系统
  4. EJB3 QL查询
  5. Internet信息服务找不到
  6. 4.用文本编辑器输入课堂上练习的Hello.java,并在JDK环境下编译和运行。请将程序编译、运行的结果截图,填入下框中。
  7. HD2025查找最大元素
  8. “发送至Onenote”惹来的小麻烦(转)
  9. IOS uitableviewcell 向左滑动删除编辑等
  10. QtWebkit2.2.0 HTML5.0支持情况
  11. 浅谈V8引擎中的垃圾回收机制
  12. api-gateway实践(05)新网关工作 - 缓存定义
  13. 简单封装Redis做缓存
  14. canvas的使用方法
  15. day28元类与异常查找
  16. 海西 &#183; 云交付 DevOps实践落地方案
  17. oracle的undo表空间
  18. Django中HtttpRequest请求
  19. bzoj 1050 [HAOI2006]旅行comf (并查集)
  20. composer &quot;Failed to decode zlib stream&quot;

热门文章

  1. java面
  2. Python入门--番外--中文目录乱码问题
  3. MySQL的LOOP, LEAVE 和ITERATE语句(类似Continue、Break的写法)
  4. Oracle 12c PDB和CDB全局用户权限问题
  5. Entity Farmework领域建模方式 3种编程方式
  6. Hadoop HDFS 常用命名
  7. Spring中Beans的自动装配概述
  8. js -- 监听窗口的大小变化
  9. 第二讲_图像数据处理Image Data Processing
  10. Mathematica 表达式求值