GOCC18:2020年Google在线编码挑战赛-新毕业生(印度)

2021年4月26日16:36:11 发表评论 915 次浏览

面向2021年新毕业生的Google 2020年在线挑战赛(GOCC++18)于2020年9月26日举行。

这是一个60分钟的在线测试, 需要解决2个编码问题。考试是在HackerEarth平台上进行的。

该过程是首先应将你的简历入围考试。

考试时间– 1小时

第一个问题:查询范围

你将得到一个包含N个整数的数组A。你需要回答以下类型的Q查询:

L R

确定将所有数组值从索引L划分为R的不同质数的计数。

注意:考虑基于1的索引

输入格式:

  • 第一行包含一个整数T, 表示测试用例的数量。
  • 每个测试用例的第一行包含一个整数N。
  • 每个测试用例的第二行包含N个以A分隔的空格。
  • 第三行包含整数Q。
  • 接下来, Q行包含两个以空格分隔的整数, 表示查询。

输出格式;

打印将所有数组值从索引L划分为R的不同质数的计数。

经验:我已经使用段树解决了这个问题https://www.lsbin.org/segment-tree-set-1-range-minimum-query/请参阅有关范围最小查询的本文, 它与此问题类似。

第二个问题–加权树的价值

你将获得一个具有N个节点的加权无向树。每个边都有权重。

你需要找到∑(i = 1至N-1)∑(j = i + 1至N)F(i, j)函数的值, 其中F(i, j)表示边缘上权重的总和节点i和j之间的简单路径。

输入格式:

  • 第一行包含一个整数T, 表示测试用例的数量。
  • 每个测试用例的第一行包含一个整数N, 表示树中的节点数。
  • 接下来的N-1行包含三个以空格分隔的整数u v w, 表示u和v之间权重为w的边。

输出格式:

对于每个测试用例, 在新行中打印函数模10 ^ 9 + 7的值。


木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: