URAL题解二

URAL题解二

URAL 1082

题目描述：输出程序的输入数据，使得程序输出"Beutiful Vasilisa"

solution
一开始只看程序的核心部分，发现是求快排的比较次数，要使比较次数等于它所要求的才能输出"Beutiful Vasilisa"。这也太难了吧。看一下样例，再看一下它所要求的数，发现如果输入数据早就排好序，比较次数就是它所要求的数。所以只要输出(n)个从小到大的数即可。
时间复杂度：(O(n))

URAL 1083

题目描述：定义一种计算(n!!!...!=n(n-k)(n-2k)...(n mod k))(如果(k mid n))
(n!!!...!=n(n-k)(n-2k)...k)(如果(k mid n))，其中(k)为感叹号的个数。给定一个这样的表达式，输出答案。

solution
模拟。。。
时间复杂度：(O(n/k))

URAL 1084

题目描述：有一个边长为(a)正方形，一正方形的中间为圆心做一个半径为(r)的圆，求两个重叠部分的面积。

solution
先特判包含的两种情况，剩下一种情况：

三角形和圆弧的面积都很好求，而且精度要求不高，反三角可以随便用。
时间复杂度：(O(1))

URAL 1085

题目描述：有(n)个城市，有(m)条公交线路(双向)，有(p)个人需要集中在某一个城市，他们只通过公交来出行，每次坐车都要给(4)元，如果有月票则不用给钱，给出每个人所在的城市，拥有的金钱，是否有月票，求在哪一个城市集中所有人都能到，且花费最少。注意：可以换乘，但换乘后依然要给钱。

solution
用链表的话边太多，所以用邻接矩阵。因为点比较少，所以可以用Floyd求出两点之间的最短距离，然后就是枚举判断。
时间复杂度：(O(n^3))

URAL 1086

题目描述：输出第(n)个质数。

solution
线性筛素数。(1000000)就非常够了。
时间复杂度：(O(1000000))

URAL 1087

题目描述：有(n)颗石子，两个人轮流拿石子，每次拿石子的个数在(k)数组里选，拿到最后一颗石子的输，问先手胜，还是后手胜。

solution
记忆化搜索。
时间复杂度：(O(n))

URAL 1088

题目描述：有一棵满二叉树，树上有两个节点(p, q)，叶子节点从左到右编号（从1开始）。给出(p, q)的高度，树的高度，离(p)最近的叶子节点，离(q)最近的叶子节点，以及一个数(D)，判断(p, q)的距离是否不超过(D)。

solution
求出那两个叶子节点的LCA((A))，如果(A)的高度比(p, q)的高度都高，说明(A)就是(p, q)的LCA，否则说明(p)在(q)的子树中，或者(q)在(p)的子树中。知道这些就可以求(p, q)两点的距离。
时间复杂度：(O(logn))

URAL 1089

题目描述：有一些单词和一些句子，句子中的一些单词有错，而且只是写错一个字母，找到正确的单词进行替换，并输出正确的句子，以及错误总数。

solution
模拟
时间复杂度：(O(单词数*句子数*句子长度))