Home Page | Web Board | Problems | Standing | Status | Statistics | Award Contest |
Contest - POJ Monthly--2005.06.26
Start time: 2005-06-26 12:00:00 End time: 2005-06-26 17:00:00
Current System Time: 2024-09-08 07:35:21.040 Contest Status:
Ended
Problem ID | Title |
2446 Problem A | Chessboard |
2447 Problem B | RSA |
2448 Problem C | A New Operating System |
2449 Problem D | Remmarguts' Date |
2450 Problem E | A New Kind of Chess |
2451 Problem F | Uyuw's Concert |
2452 Problem G | Sticks Problem |
2453 Problem H | An Easy Problem |
[Standings] [Status] [Statistics]
Contest Report |
**以下解答主要来自出题者提供的解题报告(可能略有改动)。由于本人能力的限制,可能对于很多数据结构和算法的理解存在偏差(如果发现什么问题,十之八九不是出题者的问题,而是我自己的理解有问题,因此写得不对),欢迎大家指正。:) Chessboard二分图匹配,按照国际象棋的方式染色。一个1*2的牌只能覆盖一个黑格和一个白格。 所以转化为二分图的完美匹配的判断问题。 RSA这是一道取材于RSA加密算法的题目。题目首先介绍加密解密的过程,然后,在较小数值(64位整数)的范围内让解题者进行破解。本题难点有三:
1. 读懂RSA的加密解密的过程。 2. 大整数的分解。 3. 解线性模方程。
RSA算法中已知公钥对E,N,我们就可以对N强行进行分解,得到P,Q。显然,对于所给数据,必须采用pollard分解,这是一个难点。然后求出T = (P-1)*(Q-1). 于是私钥对D,N中的D则是E模T的乘法逆元,即(D*E)mod(T)=1且D是小于T的正整数。我们求解E*X=1mod(T) ,即可得到D,这是另一个难点。求出D之后,则很容易根据密文解密出明文(对于密文C,(C^D)mod(N)即是对应的明文)。 A New Operating System模拟题的代码实现没有固定的格式,总的来说,本题就是模拟+数据结构优化。 以下是出题者的实现思路:
PID是本题的一个重要参数,就像化学中的NA一样,联系了各个类。
TPID类,用Treap实现,工作为离散化PID。因为题目所给的数据范围为10^9,我们希望快速地将一个PID重新标号,以便完成以后的工作。 1.Add(PID) 插入一个PID 2.Delete(PID) 删除一个PID 3.Index(PID) 得到此PID的新标号 4.Exist(PID) 判定一个PID是否存在
TMemory类,用二叉堆实现,完成插入,找最大Memory Program。 1.Add(PID,Memory) 将进程PID,内存Memory插入 2.DeleteMax; 删除最大内存进程 3.Change(PID,V),将PID进程内存加上V,并且维护堆性质
TProcessQueue类,维护单个Process的消息队列。因为Process的个数可能很多(10^5),又可能很少(only one),所以其中消息的数量难以确定,用普通的二叉堆静态数组维护难以达到要求,所以使用Lefist Tree维护(用Treap也可以,不过代码量要大一些)。 1.Add(PID,Priority) 消息队列中添加优先权为Priority的消息。 2.Delete(PID) 删除PID队列 3.Dequeue(PID) 删除PID队列最高消息元素 4.NewProcess(PID) 建立新的消息队列进程
TSystemQueue类,维护整个消息队列的最高优先值。这一步貌似可以将所有的消息一股脑地插入本类中,但是有一个无法避免的问题,就是我们可以不断地Create和Close进程,那么每一次必须要将所有的PID消息都删除(改变优先权也是一样),需要扫描整个消息队列,而且无法使用Hash表预先标记,因为我们Close后PID标号回收,以后可以用相同的PID再创建程序,那么原来的消息就与后来的消息重复了。所以我们使用一个更聪明的方法来维护:虽然优先权可以改变,但那只是一个程序的Outer Priority,其内部的Inner Priority是不变的,所以我们只维护一个进程的最大Prioity,使用二叉堆维护。 堆中的元素的优先权为OuterPriority*Prioirty 1.Add(PID,Prioirty) 在创建新进程中使用,加入一个PID,优先权为-1(没有Message)。 2.Delete(PID) ; 删除进程 3.ChangePriority(PID,NP) 改变PID的外部优先权
TPID建立PIDList实例 TMemory建立Memory实例 TProcessQueue建立ProcessQueue实例 TSystemQueue建立SystemQueue实例
对于题目所给的命令: 1.CreateProcess(PID,Memory,Priority) 检查PID是否使用,是否需要添加 PIDList加入PID 加入Memory 加入ProcessQueue 加入SystemQueue
2.AddMessage(PID,Priority) 检查PID是否使用 加入ProcessQueue 查看SystemQueue是否需要更新
3.Run 查看队列是否为空 SystemQueue得到并更新优先权最高的Message ProcessQueue删去该Message
4.ChangePriority(PID,Priority) 检查PID SystemQueue.ChangePriority
5.GetMemory(PID,Memory) 检查PID Memory.Change
6.FreeMemory(PID,Memory) 检查PID 当改变后的Memory>0 Memory.Change 否则 PIDList删去该PID Memory删去该PID SystemQueue中删去该PID ProcessQueue中删去该PID
7.RunProcess(PID) 检查PID,查看队列是否非空 ProcessQueue中删去最大优先权Message SystemQueue更新
8.CloseMaxMemory 查看队列是否非空 PIDList删去该PID Memory删去该PID SystemQueue中删去该PID ProcessQueue中删去该PID
9.CloseProcess(PID) 检查PID PIDList删去该PID Memory删去该PID SystemQueue中删去该PID ProcessQueue中删去该PID Remmarguts' Date出题者的算法是首先计算任意一点到终点的最短距离,使用这个距离作为A*算法中H函数(从当前点到终点的估计函数)使用A*算法。跟一般的A*算法不同的是,一个结点可以被多次扩展到(A*算法中只保留到达一个结点的最短路径)。使用这个算法就可以得到起点到终点的最短路径,第二短路径,第三短路径…… 复杂度很难算清楚,但是非常低。 A New Kind of Chess出题者的算法是假设(a, b)和(c, d)分别使用x和y个。
适当的枚举x和y(比如首先取x最大,y最小,当x逐渐变小时,y逐渐变大),找到初始位置在(p+1)*(q+1)的格子里面,第一步就可以跳出(p+1)*(q+1)的格子的情况。枚举一下它第一步由哪一种移动方式走出(p+1)*(q+1),然后就是计算C(x+y-1,x)或者C(x+y-1,x-1)来求出这时的可能性总数。 Uyuw's concert可以使用半平面的交,但是出题者实现了一种新算法,实现很简单nlogn。 首先考虑atan2斜率[-pi/2,pi/2]的椅子(方向朝上和严格面向右边的椅子),另外的椅子做翻转以后可以同样考虑。 将这些椅子按斜率从小到大排序,斜率相同的所有椅子中,只有最靠上的是有用的。然后类似凸包的维护(当前直线和上一条直线的交点,必须在上一个交点的右侧),计算能看到这些椅子的区域边界(是开口朝上的半个凸多边形)。 另一部分的点,也可以找到一个开口朝下的半个凸多边形,将它们线性合并(直接判断左右边界即可) Sticks Problem本题要求对于给定的正整数序列Ak ( 1 <= k <= n),求最大的下标差j-i,使得位于位置i 和 j 之间的所有整数值大于Ai小于Aj。 一般的算法很容易达到O(N^2)的复杂度,但是对于这里的数据量,显然是不合适的。我们如下考虑:
对于给定的序列A[low…up],先求出最大数的下标maxIndex和最小数的下标minIndex。 1. 如果minIndex < maxIndex,很容易由此将此数列分成三部分,A[low…minIndex-1], A[minIndex…maxIndex], A[maxIndex+1…up].显然中间部分minIndex, maxIndex满足条件,做如下跟新maxDifference = max(maxDifference, maxIndex-minIndex)。然后递归处理第一部分和第三部分。 2. 如果minIndex > maxIndex,此数列依然可以分成三部A[low…maxIndex], A[maxIndex+1…minIndex-1], A[minIndex…up].依然可以对此三部分进行递归处理。
如果对于一般的数据,以上的分治可以达到O(nlogn)的复杂度,但是对于数列为递减的极端情况,以上算法依然高达平方的复杂度!考虑到连续递减序列的中间部分均不满足要求,我们可以做如下改进:对于最小的元素,我们从数列中去掉以其为结束的连续递减的一部分,对于最大的元素,去掉以其为开始的连续递减的一部分。可以达到优化的目的。 本题主要考虑由数据量估计出算法复杂度,然后采用分治的策略,同时采用基本的观察对算法进行合理的优化。 An Easy Problem简单题。 |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator