**以下解答主要来自出题者提供的解题报告（可能略有改动）。由于本人能力的限制，可能对于很多数据结构和算法的理解存在偏差（如果发现什么问题，十之八九不是出题者的问题，而是我自己的理解有问题，因此写得不对），欢迎大家指正。:)

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

简单题。