首页 > 代码库 > codevs矩阵乘法系列

codevs矩阵乘法系列

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=0; int r=0; char c=getchar();
    while(c<0 || c>9) { if(c==-) b=!b; c=getchar(); }
    while(c>=0 && c<=9) { r=r*10+c-0; c=getchar(); }
    if(b) return -r; return r;
}

const int inf = 1e9+7, N = 407;
int f[3][N][N],I,J,K;

int main()
{
    int i,j,k;
    I=gi(), K=gi();
    for (i=1; i<=I; i++)
        for (k=1; k<=K; k++)
            f[0][i][k]=gi();
    K=gi(), J=gi();
    for (k=1; k<=K; k++)
        for (j=1; j<=J; j++)
            f[1][k][j]=gi();
    for (i=1; i<=I; i++)
        for (j=1; j<=J; j++)
            for (k=1; k<=K; k++)
                f[2][i][j]+=f[0][i][k]*f[1][k][j];
    for (i=1; i<=I; i++)
        {
            for (j=1; j<=J; j++)
                printf ("%d ",f[2][i][j]);
            printf ("\n");
        }
    return 0;
}

 

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=0; ll r=0; char c=getchar();
  while(c<0 || c>9) { if(c==-) b=!b; c=getchar(); }
  while(c>=0 && c<=9) { r=r*10+c-0; c=getchar(); }
  if(b) return -r; return r;
}

const int inf = 1e9+7, N = 807;
int n,m;
ll f[3][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=1; i<=n; i++)
    for (j=1; j<=n; j++)
      f[0][i][j]=gi(), f[0][i][j]+=f[0][i-1][j];
  for (i=1; i<=n; i++)
    for (j=1; j<=n; j++)
      f[1][i][j]=gi(), f[1][i][j]+=f[1][i][j-1];
  for (i=0; i<m; i++)
    {
      x=gi(), y=gi(), q=gi(), w=gi(); ans=0;
      a=max(x,q), b=max(y,w), c=min(x,q), d=min(y,w);
      for (j=1; j<=n; j++)
    ans+=(f[0][a][j]-f[0][c-1][j]) * (f[1][j][b]-f[1][j][d-1]);
      printf ("%lld\n",ans);
    }  
  return 0;
}

 

codevs矩阵乘法系列