【数据结构与算法】- 期末考试

课程链接: 清华大学驭风计划

代码仓库：Victor94-king/MachineLearning: MachineLearning basic introduction (github.com)

驭风计划是由清华大学老师教授的，其分为四门课，包括: 机器学习(张敏教授) ， 深度学习(胡晓林教授), 计算机语言(刘知远教授) 以及数据结构与算法(邓俊辉教授)。本人是综合成绩第一名，除了数据结构与算法其他单科均为第一名。代码和报告均为本人自己实现，由于篇幅限制，只展示任务布置以及关键代码，如果需要报告或者代码可以私聊博主

数据结构与算法部分授课老师为邓俊辉教授，主要通过从贪心，分治，图搜索，动态规划 ， 散列表， 计算几何入门数据结构与算法

有任何疑问或者问题，也欢迎私信博主，大家可以相互讨论交流哟~~

任务一

题目描述

输入格式

从标准输入读入数据。

第一行为两个正整数 n,m，分别表示 |V|,|E||。

接下来 m 行，每行三个整数 u,v,w，表示 u,v 之间存在一条无向边，其权值为 w。

对于所有输入数据，都满足 1≤n≤105 ,1≤m≤3×105,0≤w<108, 1≤u,v≤**n1≤105,1≤3×105,0≤�<108,1。

输出格式

输出到标准输出。

输出一行一个整数，表示所求的最小值。

任务二

题目描述

输入格式

输出格式

输出到标准输出。

输出一行一个非负整数，表示所求值。

任务三

题目描述

输入格式

从标准输入读入数据。

第一行为两个正整数n,k，分别表示给定的点的数目以及要寻找的点的数目。

接下来一行为 n 个整数，第 i 个数为xi 的值。

对于所有输入数据，都满足 1≤5,000,1≤2,000,|≤1041≤n≤5,000,1≤k≤2,000,|xi|≤104。

输出格式

输出到标准输出。

输出一行一个数（保留四位小数），表示题目给出的算式的最小值。

任务四

题目描述

给定两个字符串 t,p，求 t 的与 p 长度相同且至多有 k 处不匹配的子串数目。

输入格式

从标准输入读入数据。

输入第一行为一个整数 k。

接下来两行分别为两个字符串，表示 t,p。

对于所有输入数据，设任意字符串的长度为 l，都有 1≤l≤2×106,1≤k≤**101≤≤2×106,1≤10，且字符串仅包含小写英文字母。

输出格式

输出到标准输出。

输出一行一个整数，表示所求子串数目。

任务五

题目描述

输入格式

从标准输入读入数据。

输入第一行为一个整数 n，表示直线数量。

接下来 n 行依次描述每条直线，其中第 i 行为两个整数 ki,bi **含义同题目描述。

输出格式

输出到标准输出。

输出一行，从小到大输出满足条件的所有直线编号，并以空格分隔。