CSDN 编程竞赛十五期题解

竞赛总览

CSDN编程竞赛十五期：比赛详情 (csdn.net)

竞赛题解

题目1、求并集 

由小到大输出两个单向有序链表的并集。如链表A[1,2,5,7]、链表B[3,5,7,8]，输出[1,2,3,5,7,8] 。

这道题本质上是一个数据排序去重的问题。除了输入数据之外，还包含两个主要步骤：排序、去重。

然而，如果真的写一个链表操作的代码，会消耗很多时间，这是非常不划算的。

可以用集合来实现排序去重功能，集合本身就是无重复元素的，利用这个特性可以巧妙地完成此题。

代码框架如下：

int main () {int x, y;scanf ("%d %d", &x, &y);std::set data;for (int i = 0; i < x + y; i++) {int n;scanf ("%d", &n);data.insert (n);}// 输出集合中的元素return 0;
}

在C++ STL模板库中，集合的优化做得很好，效率非常高，因此不需要担心算法超时的问题（除非算法本身写得就有问题）。

逐个输入数据，边输入边将其添加到集合中。

输入完成之后，输出集合中的元素，此时得到的就是排序去重之后的列表了。

题目2、小T找糖豆

已知连续序列A，包含1e8个元素，分别是[1,1e8]。现在去除序列中的n个元素。得到新的连续序列[X,1e8]，该序列中最小元素是多少？

只要好好读题，就会发现这道题真的很简单，初学者也可以做出来。

旧的序列是连续的，去除n个元素之后，需要新序列也连续。

并且，已经给出了新序列的范围。

所以直接取被切除序列右侧的部分（即新序列的左侧）即可。

题目3、争风吃醋的豚鼠

N个节点两两建边。不存在3个节点相互之间全部相连（3个节点连接成环）。最多能建立多少条边？

这个题在纸上画一下就可以找到规律啦。

如果是全连接的话，根据节点编号从小往大连，用过的节点就不能重复使用了。

不过这道题规定，不可以连接成三角形，因此如果节点连接的不是和它相邻的节点，必须要跨过一个才行，例如1不能连接3，只能连接4。

然后4和5相邻，1如果再向后连接，不能连接5，只能连接6。

静下心来推理一遍，推理完成之后，会发现代码也就两三行。

题目4、选择客栈

丽江河边有n家很有特色的客栈，客栈按照其位置顺序从1到n编号。每家客栈都按照某一种色调进行装饰（总共k种，用整数0~k-1表示），且每家客栈都设有一家咖啡店，每家咖啡店均有各自的最低消费。两位游客一起去丽江旅游，他们喜欢相同的色调，又想尝试两个不同的客栈，因此决定分别住在色调相同的两家客栈中。晚上，他们打算选择一 家咖啡店喝咖啡，要求咖啡店位于两人住的两家客栈之间（包括他们住的客栈），且咖啡店的最低消费不超过p。他们想知道总共有多少种选择住宿的方案，保证晚上可以找到一家最低消费不超过p元的咖啡店小聚。

NOIP原题。可以用动态规划算法解决此题。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！