Home PageWeb BoardProblemsStandingStatusStatisticsAward Contest
北京大学ACM/ICPC竞赛训练暑期课面向全球招生!

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:  2016-05-26 12:43:05.702  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算法中已知公钥对EN,我们就可以对N强行进行分解,得到PQ。显然,对于所给数据,必须采用pollard分解,这是一个难点。然后求出T (P-1)*(Q-1). 于是私钥对DN中的D则是ET的乘法逆元,即(D*E)mod(T)=1D是小于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类,维护整个消息队列的最高优先值。这一步貌似可以将所有的消息一股脑地插入本类中,但是有一个无法避免的问题,就是我们可以不断地CreateClose进程,那么每一次必须要将所有的PID消息都删除(改变优先权也是一样),需要扫描整个消息队列,而且无法使用Hash表预先标记,因为我们ClosePID标号回收,以后可以用相同的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)分别使用xy个。

适当的枚举xy(比如首先取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[lowup],先求出最大数的下标maxIndex和最小数的下标minIndex

1. 如果minIndex < maxIndex,很容易由此将此数列分成三部分,A[lowminIndex-1], A[minIndexmaxIndex], A[maxIndex+1up].显然中间部分minIndex, maxIndex满足条件,做如下跟新maxDifference = max(maxDifference, maxIndex-minIndex)。然后递归处理第一部分和第三部分。

2. 如果minIndex > maxIndex,此数列依然可以分成三部A[lowmaxIndex], A[maxIndex+1minIndex-1], A[minIndexup].依然可以对此三部分进行递归处理。

如果对于一般的数据,以上的分治可以达到O(nlogn)的复杂度,但是对于数列为递减的极端情况,以上算法依然高达平方的复杂度!考虑到连续递减序列的中间部分均不满足要求,我们可以做如下改进:对于最小的元素,我们从数列中去掉以其为结束的连续递减的一部分,对于最大的元素,去掉以其为开始的连续递减的一部分。可以达到优化的目的。

本题主要考虑由数据量估计出算法复杂度,然后采用分治的策略,同时采用基本的观察对算法进行合理的优化。

An Easy Problem

简单题。

Home Page Go Back To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator