P2222 [HNOI2001]矩阵乘积

· · 题解

前言：

实际上我写这篇题解就是为了纪念这个时刻。

2022.2.22-22:22:22

此外，这道题为 P2222，今天是星期二，廿二。

朴素的算法的空间是 3nm 在此题的空间下是肯定不够的，所以我们便不能使用二维数组。

显然：

P_{x,y}=\sum_{i=1}^{n}a_{x,i}\times b_{i,y} D_{x,y}=\sum_{i = 1}^{n}\sum_{j=1}^{o}a_{x,i}\times b_{i,j}\times c_{j,y}

所以 P_{x,y} 只关系到 A 矩阵的 x 行和 B 矩阵 的 y 列。

并且 D_{x,y} 只关系到 A 矩阵的 x 行和 C 矩阵 的 y 列。

可是前文说明了不可以使用二维数组，那么我们就将其优化成一维。

我们推出的答案包括因式 b_{i,j}，由于 B 矩阵中的所有元素都会参与运算，又因为矩阵为稀疏矩阵，所以我们可以直接用一维数组将 B 矩阵的数存储起来。

再将二维形式中的剩余部分转换为一维。

最后可以得到答案的一维形式：

D_{x,y}=\sum_{i=1}^{cnt}A_{cx_i}\times ck_i\times C_{cy_i}

注：cnt 为矩阵 B 中的给定的元素个数。

代码：

#include<bits/stdc++.h>

using namespace std;

const int NR=6010;
int x,y,m,n,o,p,ans,cnt;
int i,j,k,ti,tj,tk;
int A[NR],C[NR];
int cx[NR],cy[NR],ck[NR];

int main()
{
    cin>>x>>y>>m>>n>>o>>p;
    cin>>i>>j>>k;
    do{ //试了几次，发现 while 不行
        if(i==x) A[j]=k;
        ti=i,tj=j,tk=k; //存储行、列、值
        cin>>i>>j>>k;
    }while(i>=ti&&(i!=ti||j>tj));
    do{
        ++cnt;
        cx[cnt]=i,cy[cnt]=j,ck[cnt]=k;
        ti=i,tj=j,tk=k;
        cin>>i>>j>>k;
    }while(i>=ti&&(i!=ti||j>tj));
    do{ if(j==y) C[i]=k; }while(cin>>i>>j>>k); 
    for(int i=1;i<=cnt;i++) ans+=A[cx[i]]*ck[i]*C[cy[i]];
    cout<<ans;
    return 0;
}