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