CCF202006-2稀疏向量

CCF202006-2稀疏向量

一看到这么大的范围，不可能开两个数组把稀疏向量全部存进去，只能存有对应值的数据，用pair数组存。

TIPS：虽然a，b没有超过int范围，但是计算的结果sum可能超int范围，把所有的int改为long long int就过了，一开始全用的int始终是60分。

代码如下：

#include 
using namespace std;
const int maxnum=5e5+1;
pair u[maxnum],v[maxnum];
int main(){
	long long int n,a,b;
	cin>>n>>a>>b;
	long long int x,y;
	for(int i=1;i<=a;i++){
		cin>>x>>y;
		u[i]=make_pair(x,y);
	}
	for(int i=1;i<=b;i++){
		cin>>x>>y;
		v[i]=make_pair(x,y);
	}
	long long int i=1,j=1,sum=0;
	while(true){
		if(i>a||j>b) break;
		long long int indexa=u[i].first,indexb=v[j].first;
		if(indexaindexb){
			j++;
			continue;
		}else if(indexa==indexb){
			sum+=u[i].second*v[j].second;
			i++;
			j++;
			continue;
		} 
	}
	cout< 
欢迎分享，转载请注明来源：内存溢出
原文地址:https://54852.com/zaji/5594729.html