CCF計算機軟體能力認證試題練習：202006-2 稀疏向量
稀疏向量
來源：CCF 標簽： 參考資料： 相似題目：
題目
對于一個 n 維整數向量 v ∈ Zn，其在第 index 個維度上的取值記作 vindex，這里我們約定 index 的取值從 1
開始，即 v = (v1, v2, · · · , vn)，下面介紹一種向量的稀疏表示方法，如果 v 僅在少量維度上的取值不為 0，則稱其為稀疏向量，
例如當 n = 10 時，v = (0, 0, 0, 5, 0, 0,; 3, 0, 0, 1) 就是一個稀疏向量，
由于稀疏向量的非零值較少，我們可以通過僅存盤非零值的方式來節省空間，具體來說，每個非零值都可以用一個 (index, value)
對來表示，即該向量在第 index 個維度上的取值 vindex = value ≠ 0，在上面的例子中，v 就可以表示為 [(4, 5),
(7, 3), (10, 1)]，接下來給出這種稀疏表示一般化的定義，
? 對于任意一個 n 維整數向量 v ∈ Zn，如果其在且僅在 a 個維度上取值不為 0，則可以唯一表示為：
[(index1, value1), (index2, value2), · · · , (indexa, valuea)] ? 其中所有的
index 均為整數且滿足：1 ≤ index1 < index2 < · · · < indexa ≤ n
? valuei 表示向量 v 在對應維度 indexi 上的非零值，
給出兩個 n 維整數向量 u, v ∈ Zn 的稀疏表示，試計算它們的內積，
u · v = ∑ ui · vi
輸入
從標準輸入讀入資料，
輸入的第一行包含用空格分隔的三個正整數 n、a 和 b，其中 n 表示向量 u、v 的維數，a 和 b 分別表示兩個向量所含非零值的個數，
第二行到第 a + 1 行輸入向量 u 的稀疏表示，第 i + 1 行（1 ≤ i ≤ a）包含用空格分隔的兩個整數 indexi 和
valuei，表示 uindexi = valuei ≠ 0， 第 a + 2 行到第 a + b + 1 行輸入向量 v 的稀疏表示，第
j + a + 1 行（1 ≤ j ≤ b）包含用空格分隔的兩個整數 indexj 和 valuej，表示 vindex j = value
j ≠ 0
輸出
輸出到標準輸出，
輸出一個整數，表示向量 u 和 v 的內積 u · v，
輸入樣例
10 3 4
4 5
7 -3
10 1
1 10
4 20
5 30
7 40
輸出樣例
-20
樣例解釋
u = (0, 0, 0, 5, 0, 0, 3, 0, 0, 1)
v = (10, 0, 0, 20, 30, 0, 40, 0, 0, 0)
u · v = 5 × 20 + (-3) × 40 = 20
提示
解題思路
因為資料很大，用暴力回圈必然會超時，
但是仔細看輸入樣例不難發現他是按索引從小到大的順序輸入的
如u 是4 7 10
如v 是1 4 5 7
這樣我們很容易相當于佇列的方式存v和u，因為佇列的頭永遠都是索引最小的那一位
至于如何存 索引+值 其實最適合的方式應該是 pair<int,int>了
我們把資料分別存好在u，v的佇列后
只需通過u.front().first和v.front().first來獲得u和v的佇列頭部的索引
如果相等則 res+=（u.front().second*v.front().second），然后兩個同時pop()出列
不等的話，看哪個索引小就哪個出列
代碼部分如下：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,a,b;
queue< pair<int,int> > u,v;
cin>>n>>a>>b;
pair<int,int> temp;
for(int i=0;i<a;i++)
{
cin>>temp.first>>temp.second;
u.push(temp);
}
for(int i=0;i<b;i++)
{
cin>>temp.first>>temp.second;
v.push(temp);
}
long long res=0;
while(!u.empty()&&!v.empty())
{
if(u.front().first==v.front().first)
{
res+=u.front().second*v.front().second;
u.pop();
v.pop();
}
else{
if(u.front().first<v.front().first)
{
u.pop();
}
else
{
v.pop();
}
}
}
cout<<res;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/4425.html
標籤：其他
下一篇：JZ51 構建乘積陣列