CSP 202006-2 稀疏向量 C++ 100

2023-01-01

题目

【题目描述】对于一个n维整数向量v∈Z”，其在第index个维度上的取值记作Vindex。这里我们约定index的取值从1开始，即v=(v1,v2…,vn)。下面介绍一种向量的稀疏表示方法。如果v仅在少量维度上的取值不为0，则称其为稀疏向量。例如当=10时，v=(0,0,0,5,0,0,-3,0,0,1)就是一个稀疏向量。由于稀疏向量的非零值较少，我们可以通过仅存储非零值的方式来节省空间。具体来说，每个非零值都可以用一个(index,value)对来表示，即该向量在第index个维度上的取值Vindex=value。在上面的例子中，v就可以表示为[(4,5)，(7，-3)，(10,1)]。接下来给出这种稀疏表示一般化的定义。 ·对于任意一个n维整数向量v∈Z”，如果其在且仅在a个维度上取值不为0，则可以唯一表示为：[(index1,valve1),(index2,valve2),···(indexa,valuea)] ·其中所有的index均为整数且满足： 1≤index1<indew2<···<indexa≤n ·valuei:表示问量v在对应维度indexi上的非零值。给出两个n维整数问量u,v∈Z”的稀疏表示，试计算它们的内积。

【输入格式】从标准输入读入数据。输入的第一行包含用空格分隔的三个正整数n、a和b，其中n表示向量u、v的维数，a和b分别表示两个向量所含非零值的个数。第二行到第a+1行输入向量的稀疏表示。第i+1行(1≤i≤a)包含用空格分隔的两个整数indexi和valuei,表示Vindexj=valuej 第a+2行到第a+b+1行输入向量v的稀疏表示。第j+a+1行(1≤j≤b) 包含用空格分隔的两个整数indexj;和valuej,表示Vindexj=valuej

【输出格式】输出到标准输出。输出一个整数，表示向量u和v的内积u·v。

【样例输入】

【样例输出】

-20

代码

#include<bits/stdc++.h>
using namespace std;

using ll = long long;
const ll N=5e5+5;

struct vec
{
    int index;
    int value;
}A[N],B[N];

int main()
{
    ll n,a,b;
    ll i,j;
    ll sum=0;
//    ifstream cin("test.in");
//    ofstream cout("test.out");
    cin>>n>>a>>b;
    for(ll i=0;i<a;i++)
    {
        cin>>A[i].index>>A[i].value;
    }
    for(ll i=0;i<b;i++)
    {
        cin>>B[i].index>>B[i].value;
    }
    i=j=0;
    while(i<a&&j<b)
    {
        if(A[i].index==B[j].index)
        {
            sum+=A[i].value*B[j].value;
            i++;
            j++;
        }
        else if(A[i].index<B[j].index)
            i++;
        else
            j++;
    }
    cout<<sum<<endl;
    return 0;
}