大灾变

大灾变是我在2009年末的时候在NOI国家集训队冬令营出的题,题目背景是魔兽世界。当年出题的时候刚好听到魔兽世界第三个资料片「大灾变」的传闻,所以就以此为背景了,之前我还出过三次魔兽世界模拟赛的题。今天回头重新来看,发现题解和数据的质量还是很高的,所以决定发布出来。有趣的是,我还给题解的每个算法起了一个名字,如下表所示:

思路甲 欲窮千里目,更上一層樓 说明“站得越高,看得越远”的道理
算法一 行遠必自邇,登高必自卑 太高了要降低高度,说明二分的原理
思路乙 不識廬山眞面目,祇緣身在此山中 说明可视区域在山脉上方
算法二 表獨立兮山之上,云容容兮而在下 在山脉上空的下凸线上扫描最低点,比喻为云层
算法三 刪繁就簡三秋樹,領異標新二月花 用“删繁就简”概括维护凸线的堆栈(单调队列)
算法四 近水樓臺先得月,向陽花木易逢春 比喻制造单调性的优势
思路丙 會當淩絕頂,一覽眾山小 猜想到山坡交线最高点就能看见山脉
算法五 不畏浮雲遮望眼,自緣身在最高層 在上升线和下降线的最高点,就能一览山脉全貌

资源链接

问题描述

艾泽拉斯世界经历一场亘古未有的地震过后,大地和海洋被完全撕裂,旧大陆残缺不全。联盟和部落各种族的居民们被迫离开了世代居住的家园,来寻找新的生存空间。原本平坦的陆地上现在隆起了一座座山峰,暴风城的人类开始在艾尔文山脉重建家园。他们决定在山脉之中建造一座瞭望塔和一个魔法浮空岛,以便于在瞭望塔和浮空岛上可以俯视艾尔文山脉的全貌。

艾尔文山脉被描述为一个折线,给定每个点的坐标(横纵坐标均不小于0),按照横坐标从小到大顺次连接起来就是就是山脉的折线。折线上所有点的横坐标均不相同。如果一个位置与山脉任何一点的连线均不被挡住(但可以与地面相切),那么就说这一点可以望到整个艾尔文山脉。瞭望塔的塔身不会挡住视线,而且瞭望塔和浮空岛可以建造在同一位置。为节省建筑材料,瞭望塔塔身的高度必须尽量小,即从塔顶到塔底的距离尽量小,瞭望塔可以建在山坡上。由于气候因素,浮空岛应建立在海拔尽量低的位置(甚至可以建在地面上),海平面高度为0。如果有多个位置均满足条件,则选择横坐标最小的那个。瞭望塔和浮空岛横坐标范围应在艾尔文山脉横坐标范围之内。给定艾尔文山脉,请你求出瞭望塔和浮空岛的位置。

输入文件

  • 1行,一个整数N,表示描述艾尔文山脉的折线的顶点数。
  • 2-N+1行,每行两个整数,xi, yi表示折线上点的坐标。

输出文件

  • 第1行,两个保留3位小数的浮点数x1, y1,表示瞭望塔顶端的坐标。
  • 第2行,两个保留3位小数的浮点数x2, y2,表示浮空岛的坐标。

输入样例

6
2 2
6 1
8 6
10 3
16 5
20 2

输出样例

8.00 11.00
9.54 9.85

样例说明

样例中描述的艾尔文山脉各个顶点,按照横坐标顺序顺次连接后的折线如下图所示:

艾尔文山脉

瞭望塔应建造在山峰(8, 6)处,塔顶端为(8, 11),高度为5,此时瞭望塔的高度最小。

瞭望塔

浮空岛建立在(9.54, 9.85)处,海拔高度最低。

浮空岛

问题限制

  • 时间限制2000 ms
  • 内存限制128 MB

数据规模

  • 40%的数据2<=N<=10
  • 100%的数据2<=N<=1 000 000;0<=xi,yi<=5 000 000

评分方式

对于每个测试点,如果输出的结果与答案文件完全相同,得该测试点100%的分数,如果仅有一行与答案文件相同,得该测试点50%的分数,否则得0%的分数。

线性规划与网络流24题-最长递增子序列问题

【问题分析】

第一问时LIS,动态规划求解,第二问和第三问用网络最大流解决。

【建模方法】

首先动态规划求出F[i],表示以第i位为开头的最长上升序列的长度,求出最长上升序列长度K。

1、把序列每位i拆成两个点<i.a>和<i.b>,从<i.a>到<i.b>连接一条容量为1的有向边。 2、建立附加源S和汇T,如果序列第i位有F[i]=K,从S到<i.a>连接一条容量为1的有向边。 3、如果F[i]=1,从<i.b>到T连接一条容量为1的有向边。 4、如果j>i且A[i] < A[j]且F[j]+1=F[i],从<i.b>到<j.a>连接一条容量为1的有向边。

求网络最大流,就是第二问的结果。把边(<1.a>,<1.b>)(<N.a>,<N.b>)(S,<1.a>)(<N.b>,T)这四条边的容量修改为无穷大,再求一次网络最大流,就是第三问结果。

【建模分析】

上述建模方法是应用了一种分层图的思想,把图每个顶点i按照F[i]的不同分为了若干层,这样图中从S出发到T的任何一条路径都是一个满足条件的最长上升子序列。由于序列中每个点要不可重复地取出,需要把每个点拆分成两个点。单位网络的最大流就是增广路的条数,所以最大流量就是第二问结果。第三问特殊地要求x1和xn可以重复使用,只需取消这两个点相关边的流量限制,求网络最大流即可。

最长递增子序列问题 问题描述: 给定正整数序列x1,...,xn 。 (1)计算其最长递增子序列的长度 s。 (2)计算从给定的序列中最多可取出多少个长度为 s 的递增子序列。 (3)如果允许在取出的序列中多次使用 x1 和 xn,则从给定序列中最多可取出多少个长度为 s 的递增子序列。 编程任务: 设计有效算法完成(1)(2)(3)提出的计算任务。 ́数据输入: 由文件 input.txt 提供输入数据。文件第 1 行有 1 个正整数 n,表示给定序列的长度。接 下来的 1 行有 n 个正整数 x1 ,.., xn 。 结果输出: 程序运行结束时,将任务(1)(2)(3)的解答输出到文件 output.txt 中。第 1 行是最长 递增子序列的长度 s。第 2 行是可取出的长度为 s 的递增子序列个数。第 3 行是允许在取出 的序列中多次使用 x1 和 xn 时可取出的长度为 s 的递增子序列个数。 输入文件示例 input.txt 4 3 6 2 5 输出文件示例 output.txt 2 2 3

线性规划与网络流24题-圆桌问题

【问题分析】

二分图多重匹配问题,可以用最大流解决。

【建模方法】

建立二分图,每个单位为X集合中的顶点,每个餐桌为Y集合中的顶点,增设附加源S和汇T。

1、从S向每个Xi顶点连接一条容量为该单位人数的有向边。 2、从每个Yi顶点向T连接一条容量为该餐桌容量的有向边。 3、X集合中每个顶点向Y集合中每个顶点连接一条容量为1的有向边。

求网络最大流,如果最大流量等于所有单位人数之和,则存在解,否则无解。对于每个单位,从X集合对应点出发的所有满流边指向的Y集合的顶点就是该单位人员的安排情况(一个可行解)。

【建模分析】

对于一个二分图,每个顶点可以有多个匹配顶点,称这类问题为二分图多重匹配问题。X,Y集合之间的边容量全部是1,保证两个点只能匹配一次(一个餐桌上只能有一个单位的一个人),源汇的连边限制了每个点匹配的个数。求出网络最大流,如果流量等于X集合所有点与S边容量之和,那么则说明X集合每个点都有完备的多重匹配。

【问题另解】

贪心,更好的方法其实是贪心。首先把所有单位和餐桌按人数从大到小排序,一种适当的贪心策略就是对于每个单位,所有人每次尽量去剩余容量较大的餐桌就坐。按照这种贪心策略,如果某时发现有人已经无法就坐,则无解。具体方法为用线段树维护餐桌的剩余容量,按人数从多到少安排每个单位的人员,每次安排就是把容量餐桌前k大的餐桌人数减1(k为该单位人数)。为保证线段树前k位时刻为前k大,要维护第k与第k+1,k+2,...人数与第k相等的位置,减少第k大时要减少尽量靠后的,这样才能保证单调。

圆桌问题
问题描述: 假设有来自 n 个不同单位的代表参加一次国际会议。每个单位的代表数分别为ri ,i =1,2,...,n。会议餐厅共有 m 张餐桌,每张餐桌可容纳ci (i =1,2,...,m)个代表就餐。为了使代表们充分交流,希望从同一个单位来的代表不在同一个餐桌就餐。试设计一个算法, 给出满足要求的代表就餐方案。
编程任务: 对于给定的代表数和餐桌数以及餐桌容量,编程计算满足要求的代表就餐方案。
́数据输入: 由文件 input.txt 提供输入数据。文件第 1 行有 2 个正整数 m 和 n,m 表示单位数,n 表示餐桌数,1&lt;=m
结果输出:
程序运行结束时,将代表就餐方案输出到文件 output.txt 中。如果问题有解,在文件第 1 行输出 1,否则输出 0。接下来的 m 行给出每个单位代表的就餐桌号。如果有多个满足要求的方案,只要输出 1 个方案。
输入文件示例
input.txt
4 5
4 5 3 5
3 5 2 6 4
输出文件示例
output.txt
1
1 2 4 5
1 2 3 4 5
2 4 5
1 2 3 4 5

线性规划与网络流24题-魔术球问题

【问题分析】

枚举答案转化为判定性问题,然后最小路径覆盖,可以转化成二分图最大匹配,从而用最大流解决。

【建模方法】

枚举答案A,在图中建立节点1..A。如果对于i<j有i+j为一个完全平方数,连接一条有向边(i,j)。该图是有向无环图,求最小路径覆盖。如果刚好满足最小路径覆盖数等于N,那么A是一个可行解,在所有可行解中找到最大的A,即为最优解。

具体方法可以顺序枚举A的值,当最小路径覆盖数刚好大于N时终止,A-1就是最优解。

【建模分析】

由于是顺序放球,每根柱子上的球满足这样的特征,即下面的球编号小于上面球的编号。抽象成图,把每个球看作一个顶点,就是编号较小的顶点向编号较大的顶点连接边,条件是两个球可以相邻,即编号之和为完全平方数。每根柱子看做一条路径,N根柱子要覆盖掉所有点,一个解就是一个路径覆盖。

最小路径覆盖数随球的数量递增不递减,满足单调性,所以可以枚举答案(或二分答案),对于特定的答案求出最小路径覆盖数,一个可行解就是最小路径覆盖数等于N的答案,求出最大的可行解就是最优解。本问题更适合枚举答案而不是二分答案,因为如果顺序枚举答案,每次只需要在残量网络上增加新的节点和边,再增广一次即可。如果二分答案,就需要每次重新建图,大大增加了时间复杂度。

魔术球问题
问题描述: 假设有 n 根柱子,现要按下述规则在这 n 根柱子中依次放入编号为 1,2,3,...的球。
(1)每次只能在某根柱子的最上面放球。
(2)在同一根柱子中,任何 2 个相邻球的编号之和为完全平方数。
试设计一个算法,计算出在 n 根柱子上最多能放多少个球。例如,在 4 根柱子上最多可放 11 个球。
́编程任务:
对于给定的 n,计算在 n 根柱子上最多能放多少个球。
数据输入: 由文件 input.txt 提供输入数据。文件第 1 行有 1 个正整数 n,表示柱子数。
结果输出: 程序运行结束时,将 n 根柱子上最多能放的球数以及相应的放置方案输出到文件output.txt 中。文件的第一行是球数。接下来的 n 行,每行是一根柱子上的球的编号。
输入文件示例
input.txt
4
输出文件示例
output.txt
11
1 8
2 7 9
3 6 10
4 5 11

线性规划与网络流24题-最小路径覆盖问题

【问题分析】

有向无环图最小路径覆盖,可以转化成二分图最大匹配问题,从而用最大流解决。

【建模方法】

构造二分图,把原图每个顶点i拆分成二分图X,Y集合中的两个顶点Xi和Yi。对于原图中存在的每条边(i,j),在二分图中连接边(Xi,Yj)。然后把二分图最大匹配模型转化为网络流模型,求网络最大流。

最小路径覆盖的条数,就是原图顶点数,减去二分图最大匹配数。沿着匹配边查找,就是一个路径上的点,输出所有路径即可。

【建模分析】

对于一个路径覆盖,有如下性质:

1、每个顶点属于且只属于一个路径。 2、路径上除终点外,从每个顶点出发只有一条边指向路径上的另一顶点。

所以我们可以把每个顶点理解成两个顶点,一个是出发,一个是目标,建立二分图模型。该二分图的任何一个匹配方案,都对应了一个路径覆盖方案。如果匹配数为0,那么显然路径数=顶点数。每增加一条匹配边,那么路径覆盖数就减少一个,所以路径数=顶点数 - 匹配数。要想使路径数最少,则应最大化匹配数,所以要求二分图的最大匹配。

注意,此建模方法求最小路径覆盖仅适用于有向无环图,如果有环或是无向图,那么有可能求出的一些环覆盖,而不是路径覆盖。

最小路径覆盖问题
问题描述: 给定有向图 G=(V,E)。设 P 是 G 的一个简单路(顶点不相交)的集合。如果 V 中每个顶点恰好在 P 的一条路上,则称 P 是 G 的一个路径覆盖。P 中路径可以从 V 的任何一个顶 点开始,长度也是任意的,特别地,可以为 0。G 的最小路径覆盖是 G 的所含路径条数最少 的路径覆盖。
设计一个有效算法求一个有向无环图 G 的最小路径覆盖。 提示:设 V={1,2,o ,n},构造网络 G1=(V1,E1)如下:
V1 = {x0 , x1 ,, xn }» {y0 , y1 ,, yn },
E 1 = {( x 0 , x i ) : i Œ V } » {( y i , y 0 ) : i Œ V } » {( x i , y j ) : ( i . j ) Œ E } 每条边的容量均为 1。求网络 G1 的( x0 , y0 )最大流。
 ́编程任务: 对于给定的给定有向无环图 G,编程找出 G 的一个最小路径覆盖。  ́
数据输入: 由文件 input.txt 提供输入数据。文件第 1 行有 2 个正整数 n 和 m。n 是给定有向无环图G 的顶点数,m 是 G 的边数。接下来的 m 行,每行有 2 个正整数 i 和 j,表示一条有向边(i,j)。  ́
结果输出:
程序运行结束时,将最小路径覆盖输出到文件 output.txt 中。从第 1 行开始,每行输出 一条路径。文件的最后一行是最少路径数。
输入文件示例
input.txt
11 12
1 2
1 3
1 4
2 5
3 6
4 7
5 8
6 9
7 10
8 11
9 11
10 11
输出文件示例
output.txt
1 4 7 10 11
2 5 8
3 6 9
3