二模 (5) day2

第一题:

有 N 个人顺时针围在一圆桌上开会,他们对身高很敏感。 因此决定想使得任意相邻的两人的身高差距最大值最小。 如果答案不唯一,输出字典序最小的排列,指的是身高的排列。N<=50

解题过程:

1.最大值最小的问题直接想到二分答案。。然后就变成判断环的问题,但是想不到什么好的算法,就直接爆搜了。。事实证明全部超时。。

2.正解:首先有一个贪心原则:即最高的和最矮的人肯定不会排到一起,然后他们之间的人必定是递增或者递减的(最矮的递增到最高的,然后最高的递减到最矮的),可用交换的方法证明。那么先把人按高度从小到大排序,就变成一个双线dp问题。

二模  (5) day2

F[i][j](i<j)表示 一个人在i,一个人在j,且1~j这些点都走过的最优解。

当i+1=j时,F[i][j]=min{max(F[k][i],dist[k][j])}; ( k<i )

当i+1<j时,F[i][j]=max(F[i][j-1],dist[j-1][j]);

ans=min{max(F[i][n],dist[i][n])};

最后输出答案也是个难点,一开始想到记录F[i][j]的转移方式然后递归输出,但是实际上是没法确定两个人的顺序的,也就是没法保证字典序最小。

实际上可以贪心求解。。先模拟从maxH到minH的路径,倒着走,从minH出发,那么每次要走的尽可能远。。剩下的点就是minH到maxH的路径了。

初始得分0分。


第二题:

题目描述:

在直角坐标系上,有 N 个边平行于坐标轴的矩形。你的任务是把其中的 K 个矩形染色,使按次序放下后,可以看见的有色面积最大。可看见的意思就是这一部分没有被后面的矩形覆盖。你的答案是返回 K 个整数,表示你染色的是哪 K 个矩形。如果有多种答案,输出字典序最小的。

算法:(离散化/矩形切割/线段树)

第一次写矩阵切割,记录一下大致思路。

首先有个上浮的思想,假设有N个矩形,(倒序放置矩形)第一个矩形深度为1,第K个矩形深度为K。每放一个矩形,就想象让往上面浮,每次碰到之前放过的矩形,就让他断裂,分成几个矩形,继续上浮(递归实现)。。

算法实现:

1.先判断相离的情况,让矩形一直上浮直到到了顶层或者碰到另外一个不相离的矩形。

2.根据两个矩形的位置关系切割,然后分成多个小矩形继续上浮。


第三题:

神牛 LXX 昨天刚刚满 18 岁,他现在是个成熟的有为男青年。他有 N 个 MM,分别从 1 到 N 标号。这些 MM 有些是互相认识的。现在,LXX 为了处理和 MM 们复杂的关系,想把他们划分成尽量多的集合,要求任意两个属于不同集合的 MM 都必须互相认识。这样方便交流。现在 LXX 想知道最多可以分成多少个集合,每个集合的人数是多少。1≤N≤100000,1≤M≤2000000。

解题过程:

1.首先如果两个元素之间没有边相连,那么他们肯定只能在同一个集合了。这是此题所有算法的基础。。。于是果断地写了个并查集,然后用邻接矩阵存边,能过N<=3000的数据吧。 于是拿到了50分左右。

2.正解:M相对于N来说还是比较小的,那么可以找出边最少的点K,找出和它没有相连的点合并到一个集合(还是并查集实现,O(M)的时间扫一遍所有边)。这样就可以把很多点缩成一个点,最坏的情况也就是N=2000,M=2000000左右的时候,不能缩点,那么点还是2000个,所以缩点后的点就变成了最多2000个,然后用1中的算法实现即可。。

表示被这道题虐爆了。。没有超纲的东东,只有想不到的巧方法。。

上一篇:周赛-Toy Cars 分类: 比赛 2015-08-08 15:41 5人阅读 评论(0) 收藏


下一篇:常见的js 里对数字进行处理的函数方法集合