自动搬运

查看原文

来自洛谷，原作者为

	Fearliciz _I°Fear

搬运于2025-08-24 21:35:19，当前版本为作者最后更新于2022-02-22 22:22:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

前言：

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

$$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;
}