CCF稀疏向量100分代码(利用输入的顺序,使用队列巧解)

   日期:2020-09-10     浏览:113    评论:0    
核心提示: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

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;
}
 
打赏
 本文转载自:网络 
所有权利归属于原作者,如文章来源标示错误或侵犯了您的权利请联系微信13520258486
更多>最近资讯中心
更多>最新资讯中心
0相关评论

推荐图文
推荐资讯中心
点击排行
最新信息
新手指南
采购商服务
供应商服务
交易安全
关注我们
手机网站:
新浪微博:
微信关注:

13520258486

周一至周五 9:00-18:00
(其他时间联系在线客服)

24小时在线客服