题目作者：朱允刚

单位：吉林大学

特殊说明：由于考试要求等原因，题解只有思路，没有附带代码

目录

A题：冬奥村网络布线方案 (40 分)

题目背景：

 输入格式：

输出格式：

输入样例：

输出样例：

方法一：[贪心]Prim算法

方法二：[贪心]Kruscal算法

设置一个虚原点，并建立与n个房间的虚边，采用边贪心kruscal算法，同时用并查集控制连通性，时间复杂度为O((E+N)*logE)

B&C题：冬奥会网站功能提升 (40 分)

输入格式:

输出格式:

输入样例:

输出样例:

方法一：二叉查找

方法二：TRIE树（字典树）

---

A题：冬奥村网络布线方案 (40 分)

题目背景：

冬奥会的奥运村是各国运动员在冬奥会期间的住宿公寓，冬奥会期间需要保证奥运村网络畅通，以使运动员都能正常上网。

假定奥运村有n个房间，编号为0…n−1，每个房间都需要网络连接。房间 i 有网络，当且仅当满足如下2个条件之一：

（1）房间 i 安装了路由器（成本为 ri​>0）

（2）房间 i 和房间 j 有网线连接且房间 j 有网络（在房间 i 和房间 j 之间布置网线的成本为 fij​>0）

假定你是奥组委的网络工程师，请编写程序为奥组委设计一个网络布线方案（哪些房间安装路由器，哪些房间之间布置网线），使得所有房间都有网络，且总成本最小。

例如下图包含7个房间和10个可能的连接，安装路由器的成本为括号内数字，房间之间布置网线的成本为边的权值。其解决方案为右下图，即在房间1和4安装路由器，并进行图中的网线布置。总成本为120。

 输入格式：

输入第一行为两个正整数n和e；n为房间数，不超过600；e为可能的连接数，不超过2×105。接下来一行为n个空格间隔的正整数，第i个整数(i≥0)表示在房间i安装路由器的成本。接下来e行，每行为3个非负整数i、j、f，表示在房间i和房间j之间布置网线的成本为f。

输出格式：

输出为一个整数，表示最优网络布线方案的成本。

输入样例：

7 10
60 10 35 55 40 70 70
0 1 20
0 4 75
0 3 45
1 3 50
1 2 15
2 6 5
5 6 45
4 5 5
3 5 25
3 6 65

输出样例：

120

该题为在所有房间里寻找一个类似最小支撑树样的结构

方法一：[贪心]Prim算法

采用堆优化的prim算法，时间复杂度为O(E*logN)

注意点：连通性问题

方法二：[贪心]Kruscal算法

设置一个虚原点，并建立与n个房间的虚边，采用边贪心kruscal算法，同时用并查集控制连通性，时间复杂度为O((E+N)*logE)

B&C题：冬奥会网站功能提升 (40 分)

百度、谷歌等搜索引擎，以及输入法等各种软件通常包含这样一个功能，当用户在输入框输入信息时，软件会提供一种“智能提示”。对用户所输入的信息，自动补全、列出可能的完整单词，提示给用户，以方便用户输入，提升用户体验。

 

这个功能是如何实现的呢？一种典型的实现方式是，在系统后台维护一个字典，当用户输入字符时，在字典中查找以用户当前输入的字符串为前缀的全部单词，选取其中历史使用率最高的若干单词作为候选词，建议给用户。

但遗憾的是，目前北京冬奥会官网的搜索引擎还未实现这一功能。

假定你是奥组委的软件开发工程师，请编写程序，帮助奥组委实现上述功能。

备注：这里约定一个字符串不能称为自己的前缀。若用户输入的字符串恰好是字典中的一个单词，则该单词不必向用户建议。

输入格式:

输入第一行为3个正整数n、m、k。n为字典中单词个数。m为用户查询数，即用户输入的单词个数。对于用户输入的每个字符串，程序需要返回字典中以该字符串为前缀的、历史使用频率最高的k个单词。接下来n行，表示字典信息，每行为1个整数和1个字符串，整数表示单词的历史使用频率，字符串表示单词，请注意，单词包含的每个字符为a-z的小写字母或0-9的数字，即数字也可能构成字典中的单词。字典内的单词并非按使用频率有序存放。接下来m行，表示用户的查询，每行为一个a-z的小写字母或0-9的数字组成的字符串，表示用户的查询。另外请注意，由于字典往往是在用户历史数据的基础上加工而得，所以字典中可能出现重复单词，若某个单词在字典中出现多次，则其历史使用频率以最高者为准。 (n ≤ 10000, m ≤ 20000, k ≤ 10, 每个单词长度不超过20，单词历史使用频率小于231)

输出格式:

对于用户输入的每个字符串，按使用频率降序输出字典中以该字符串为前缀的、历史使用频率最高的k个单词，每个占1行。若多个单词历史使用频率相同，则字典序靠前的单词排名靠前。若单词中包含数字，则字典序以ACSII码判定，即0<1<2<…<9

输入样例:

20 3 4
1827187200	the
1595609600	to
1107331800	that
401542500	this
334039800	they
282026500	their
250991700	them
196118888	these
150877900	than
144968100	time
125563600	then
109336600	two
196120000	there
87862100	those
79292500	through
75885600	the
71578000	think
67462300	2
65648600	tx356
57087700	though
th
xxx
the

输出样例:

the
that
this
they

no suggestion

they
their
them
there

方法一：二叉查找

①：以字典序为第一关键字，词频为第二关键字改装快排， 以合适的方法去重；O(n*logn)

②：在排好序的数组中分别查询前缀的上界与下界（下界需要将前缀词的最后一个字母的ASCII码+1，如the -> thf，th->ti），从而准确的获取到所有具有前缀的单词；O(m*logn)

③：在所有具有前缀的单词中，采取选择排序，选取前K个(或者单词数个)单词，依次输出

方法评价：总体时间复杂度：O((N+M)*logN)，查询单词时的复杂度：O(logN)，空间复杂度：O(N)，时空复杂度较为优秀，代码容易维护与迭代，比如当字符集支持大小写、其他字符时依然能够完美匹配。缺点是查询单词时复杂度仍然较高，在单词非常多的情况下时间不是非常迅速，需要采取更快的算法。

方法二：TRIE树（字典树）

思路：排序（以词频为第一关键词，字典序为第二关键词）——建树——查询

方法评价：总体时间复杂度：O(N*logN + M)，查询单词时时间复杂度：O(M)，空间复杂度：O(N)，优点是速度快