锐客网

  1. 首页 > 睿知 > it技术 > >

NJU|NJU 2019 计算机拔尖（算法）测试 解题报告

算法题解计拔NJU

NJU 2019 计算机拔尖（算法）测试 解题报告 题目来源：仲盛老师提供的公开资料。
要准备 2022 计拔所以也自行做了一下！
感觉如果有 OI 省一水平的话，难度并不大。
1 题目 输入两个数列X = < x 1 , x 2 , ? ? , x n > X= X= 和Y = < y 1 , y 2 , ? ? , y n > Y= Y=，从所有n 2 n^2 n2 个数x i + y j ( 1 ≤ i , j ≤ n ) x_i+y_j(1\le i, j\le n) xi?+yj?(1≤i,j≤n) 中 找出最大的m ( m ≤ n ) m(m\le \sqrt n) m(m≤n ?) 个，并从小到大输出。要求算法最坏时间复杂度为o ( n log ? n ) o(n\log n) o(nlogn)（注意是o o o，也就是渐近严格小于）
解答
算法流程：
（1）先用 nth_element 的方法（一种基于快速排序的方法）分别得到X , Y X, Y X,Y 前m m m 大的项，再对这m m m 个数分别进行归并排序后，得到从大到小排列的X ′ , Y ′ X', Y' X′,Y′ 数列（项数均为m m m）。
（2）对于X ′ X' X′ 中每个数x i ′ x'_i xi′?，维护一个指针p i p_i pi?（一开始p i = 1 p_i=1 pi?=1），说明下一个可以与x i ′ x'_i xi′? 匹配的是y p i ′ y'_{p_i} ypi?′?。然后将x i ′ + y p i ′ , ( i = 1 , 2 ? n ) x'_i+y'_{p_i},(i=1, 2\cdots n) xi′?+ypi?′?,(i=1,2?n) 全部放入一个大根堆。
（3）每次从堆顶取出一个元素记录，并弹出。将堆顶对应的x i ′ x'_i xi′? 对应的p i p_i pi? 自增 1，再放入x i ′ + y p i ′ x'_i+y'_{p_i} xi′?+ypi?′?。如此循环往复步骤（3）m m m 次。
（4）将记录下来的m m m 个数倒着输出。
时间复杂度分析：
第（1）步中 nth_element 最坏时间复杂度为O ( n ) O(n) O(n)，排序时间复杂度为O ( m log ? m ) O(m\log m) O(mlogm)；（注意这里用归并排序是因为快速排序最坏时间复杂度是O ( m 2 ) O(m^2) O(m2) 的，不过好像也可以过）
第（2）步中，将m m m 个元素放入堆的时间复杂度为O ( m log ? m ) O(m\log m) O(mlogm)；
第（3）步中，各m m m 次将元素弹出堆和放入堆，时间复杂度为O ( m log ? m ) O(m\log m) O(mlogm)
第（4）步中，输出复杂度为O ( m ) O(m) O(m)
故最坏时间复杂度为O ( n + m log ? m + m ) O(n+m\log m+m) O(n+mlogm+m)，由于m ≤ n m\le \sqrt n m≤n ?，所以最坏时间复杂度为O ( n + n log ? n + n ) = O ( n ) = o ( n log ? n ) O(n+\sqrt n\log n+\sqrt n)=O(n)=o(n\log n) O(n+n ?logn+n ?)=O(n)=o(nlogn)，满足题意。
思路 注意到m ≤ n m\le \sqrt n m≤n ? 这个限制条件，然后发现只有前m m m 大的数值得被考虑。这样自然而然用 nth_element 找出前m m m 大，就变成一个经典题了。
2 题目 假设A A A 是一个n n n 元数组，其中每个元素都是不小于1 1 1、不大于n n n 的整数。假设k k k 是一个小于n n n 但大于n 2 \dfrac{n}{2} 2n? 的整数，而I I I 则是一个k k k 元数组。我们用A ( I ) A(I) A(I) 来表示一个k k k 元数组，它的第 j 个元素是A [ I [ j ] ] A[I[j]] A[I[j]]。
回忆“递增”的定义：我们说I I I 是递增的，如果对于任何i , j ∈ I i,j\in I i,j∈I，只要i < j i 我们定义I I I 的递增度为使得I I I 是r r r-递增的最大的整数r r r；倘若I I I 是无穷大-递增的，那么它的递增度就是无穷大；而一个非递增数列的递增度则为0 0 0。
请设计一个尽可能高效的算法，对于输入A A A 和I I I，求出递增度。你的算法在最坏情况下的时间复杂度必须为O ( n 4 ) O(n^4) O(n4)。请给出简要的复杂度分析。
【NJU|NJU 2019 计算机拔尖（算法）测试 解题报告】解答1 一个比较好想的思路：
算法流程
（1）将I I I 从小到大排序，如果I I I 存在相等元素，则递增度为0 0 0；否则进入步骤（2）。
（2）不妨设I I I 的元素依次为I 1 , I 2 , ? ? , I k I_1, I_2, \cdots, I_k I1?,I2?,?,Ik? 且依次增大。对于所有的( I i , I i + 1 ) , 1 ≤ i < k (I_i, I_{i+1}), 1\le i （3）从（2）处得到两个数x , y x, y x,y。一开始x ← I i , y ← I i + 1 x\gets I_i, y\gets I_{i+1} x←Ii?,y←Ii+1?。
i. 判断是否满足A [ x ] < A [ y ] A[x]A[x] ii. 由 i. 的判断分为两种情况
如果满足，判断( x , y ) (x,y) (x,y) 在之前的循环过程中是否出现过：若出现过，则返回深度为+ ∞ +\infin +∞；否则让x ← A [ x ] , y ← A [ y ] x\gets A[x], y\gets A[y] x←A[x],y←A[y]，并计数器增 1，继续循环（3）i. 的判断。
如果不满足，返回计数器的值。
（4）得到k ? 1 k-1 k?1 个d i d_i di?，取所有d i d_i di? 中的最小值，即为答案。
时间复杂度分析：
（1）排序复杂度为O ( n log ? n ) O(n\log n) O(nlogn)
（2）中调用了k ? 1 k-1 k?1 次（3）
（3）单次复杂度至多O ( n 2 ) O(n^2) O(n2)（因为不同的( x , y ) (x,y) (x,y) 有O ( n 2 ) O(n^2) O(n2) 种）
（4）复杂度为O ( k ) O(k) O(k)
综上，本算法复杂度为O ( n log ? n + k ? n 2 + k ) = O ( n 3 ) O(n\log n+k\cdot n^2+k)=O(n^3) O(nlogn+k?n2+k)=O(n3)，符合题意。
思路1 仔细读题，这种“ r r r-递增”是一种迭代的过程。但是我们注意到，没有必要对整个l l l 进行迭代，只要对l l l 大小相邻元素进行迭代即可，取深度的最小值。
解答2 看到 解答1 的算法，明显可以优化（但是优化也没有分多qwq）
以所有的二元对( x , y ) , 1 ≤ x , y ≤ n (x,y),1\le x,y\le n (x,y),1≤x,y≤n 为点建图。如果x < y x 然后我们再向 解答1 一样k ? 1 k-1 k?1 项判断即可。总时间复杂度为O ( n 2 ) O(n^2) O(n2)。甚至可以对I I I 多测，单次复杂度O ( n ) O(n) O(n)。
但没有分多为啥要写这种无聊的玩意啊！！！

    推荐阅读


    上一篇：android|Kotlin Sealed Class

    下一篇：java|你不知道的 java 对象序列化的秘密