CSU-ACM Home Page

2017年中南大学校队选拔题解

Update Time: 2017-08-28 13:50:03     Recent Editor: Scanf     Create Time: 2017-08-28 13:47:24     Creator: Scanf    


Problem A 小M的移动硬盘

题目大意

有一个长度为n的序列,每次把一个元素挪到序列首部,或者挪到序列尾部,或者移动到某个元素后方

问题分析

链表能完成这里全部的工作,所以用链表模拟一下就好了。时空复杂度O(n)。

Problem B 绚丽的手链

题目大意

给出N个长度不超过L的01串,从中选出若干,使得它们的最长公共前缀长度与所选数目的乘积最大。

问题分析

对所有01串创建字典树,这样具有相同前缀的01串就在同一子树内。创建的同时记录每棵子树的大小,那么答案就是max {size[u]*depth[u]}。

时间复杂度O(NL)

Problem C 驱R符

题目大意

   一个圆上又n个点,两两之间连线,问在圆上最多有多少个交点

问题分析

方法一:交点和四边形存在一一对应关系,因此答案就是Cn4 O(∩_∩)O!

方法二:

   数学推算公式

   首先1,2,3个点的时候单独列出,不存在交点。

   我们枚举每一个圆上的点,再枚举其另一个点,两边的点数相乘,就是这个线上能够得到的最多的交点数,我先设m = n − 2,这是除了这个线两端的点数,然后我们很容易有如下的式子


$$ \sum\limits_{k=1}^{m-1}k*(m-k)$$

   然后对这个式子进行如下的推导:


$$ \sum\limits_{k=1}^{m-1}k(m-k)= \sum\limits_{k=1}^{m-1}(km-k^2)= \sum\limits_{k=1}^{m-1}km+\sum\limits_{k=1}^{m-1}k^2= m\sum\limits_{k=1}^{m-1}k+\sum\limits_{k=1}^{m-1}k^2$$

   我们都知道,$1+2+...+n=\frac{(n+1)n}{2}$$1^2+2^2+...+n^n=\frac{n(n+1)(2n+1)}{6}$

   所以之前的式子我们能推导为:


$$m\sum\limits_{k=1}^{m-1}k+\sum\limits_{k=1}^{m-1}k^2= m\frac{(m-1)m}{2}+\frac{m(m-1)(2m-1)}{6}= \frac{m(m-1)(m+1)}{6}$$

   然后,枚举了n个点,同时记住,一个直线会被算两次,因为两个端点都枚举了一次,同时一个交点也被枚举了两次,因为两个直线分别计算了一回,所以最后的结果要除以4。

   综上,结果如下:


$$\frac{n(n-1)(n-2)(n-3)}{24}$$

Problem D 赶路的小X

题目大意

  • 一个无向图,N个点,M条边,N为10000,M为50000。
  • 每个点有一个点权,一条路径的花费就是途经点中的点权最大值。
  • 现在要找一条从S到T的长度不超过给定的L的路径,并且使这条路径的花费尽可能小。
  • 输出这个花费的最小值。无解输出-1。
  • 10组数据。

问题分析

先二分一个答案。
点权超过当前二分的答案的点,就是不能够经过的点。
跑一遍从S到T的最短路。
如果最短路存在且小于等于L,则答案合法,否则答案非法。

关键字:二分答案、最短路。
注意,这个题的最短路必须使用迪杰斯特拉算法,如果使用spfa算法应该会超时。
PS:迪杰斯特拉算法复杂度稳定,尤其是求到给定目的地的最短路时,剪枝明显,因此强烈推荐大家使用!!
时间复杂度:O(M * logM * logF),这里的F指最大的点权——如果要加点优化,也可以认为是logN。

Problem E 小M的魔术表演

题目大意

有一个长度为n的序列,每次询问一个区间中比x小的数字有多少个

问题分析

首先很容易想到这题肯定跟线段树相关。我们可以这样去思考:如果询问有多少个数比x小的时候,只有比x小的数字加进了线段树中,那问题不就非常简单了?所以我们可以想到把询问离线,然后把原序列的元素从小到大加入线段树中就行了

注意一下这里数字范围很大,所以我们离散化一下就好了。时空复杂度O( nlogn + qlogn) q为询问数

Problem F LXX的能力值

题目大意

有n个数字围成一个环,每次能把连续l个数字增加到任意大小,最多能操作m次,问最后最小的数字的最大值为多少。

问题分析

二分答案;二分的上界为所有数字中的最大值,下界为所有数字中的最小值。(题意表明M * L < N)。然后检查次数是否小于m。枚举起点即可。时间复杂度: O(n2log(max(Ai)))

Problem G 画矩形

题目大意

  • 在平面上依次点N个不同的点,每次点完一个新的点后,求此时由这些点可构成的矩形的数目。
  • N为1000,点的坐标不超过30000。
  • 10组数据。

问题分析

我们可以认为,一个矩形由两条对角线确定。
也就是,如果存在两条等长共中点的线段,那么它们可以组成一个矩形。
我们把所有已知线段的中点坐标以及它的长度打包成一个整体,当作是一条线段的信息,存起来;
因为N为1000,因此最多也就106级别的线段,可以接受。
具体做法是:

  • 每次新得到一个点,我们枚举之前存在的点,这样就有了一条新的线段。
  • 统计在已经存储的线段里,有多少线段的中点及长度与当前新线段的相同,这个数值就是当前可以新产生的矩形数。
  • 把当前线段的中点及长度信息打包加入集合。


把三个值打包之后进行统计,可以使用STL的set或者map。在这种做法下,时间复杂度为O(N2log(NN))。
另外,map的本质是做一个映射,我们如果使用哈希算法,可以把因为map而多出的log给去掉。
如果使用哈希算法的话,时间复杂度为O(N2),不过,这里因为判断是否相等简单方便,因此强烈建议大家使用带冲突检测的哈希算法,而非字符串哈希那种。
也就是,建议使用向下探测法或者挂链法来实现哈希。

Problem H 玄学

题目大意

   两个矩形,如果相交,则输出并的面积,如果没有,则输出Invalid!

问题分析

   分类讨论找一致的地方。

   首先判断是否相交,不相交分两种情况,一是互不包含,用快速排斥实验的那种方法就可以解决了,说白了就是矩形的横纵坐标互相

   对于很多的情况慢慢分析,发现我们可以把坐标缩放到相交的矩形中间的那个矩形,其实就是选择两个矩形左下角的横纵坐标选择最大的那个构成个新点,右上角选最小的,因为肯定相交,所以保证合法,构成的新矩形就是两个矩形交的面积,再把总的面积减去这个就可以了。

   其它的方法的话,可以模拟扫描线的方法去做一下,不过比较麻烦,就是把这个并分成三个矩形去算,中间细节比较多。

   然后吧,其实我一开始打算分类讨论的目的出的这个题,然后做着做着发现好难,不小心就想到了正解,分类讨论要讨论太多,估计会挂,如果我数据太水的话还请见谅。。。

   当然,还有一个更暴力的方法,就是直接套几何模板,如果有准备的话,直接套就好,不过不知道你们知道那个模板怎么用不是个问题,以及代码量巨多,很容易出问题,敲错个变量之类的。

Problem I 集训数据分析

题目大意

给出N个数,要求选择最少的数使得计算出来的误差小于给定值。

问题分析

普通动态规划

f(i, j):前i组数据选j个结果,且第j个为第i组数据时的最小误差;

dev(i, j):区间[i,j]选取i,j的误差;

那么有状态转移方程:f(i,j)=min{f(k,j-1)+dev(k,i) | j-1<=k<i}

其中dev可以用O(n3)的复杂度预处理出来,dp复杂度O(n3),因此总的复杂度O(n^3)

Problem J LXX去旅行

题目大意

题意可简化为有一个有根的n叉树,且这个树一棵深度无限的完全n叉树。问到根节点的距离小于等于l的节点数目。

问题分析

设cnt[i]为满足d[j]=i的数量,f[i]为与根距离恰好为i的节点数。f[i]=f[i-j]*cnt[j],有了这个也还是难以解决,但是注意到d[j]只在100以内,那么前面的式子最多也就是100项的递推式,利用矩阵快速幂可以很快的解决这个问题。关于矩阵的构造请自己认真琢磨。时间复杂度: O(1003logl)