随笔 - 97, 文章 - 22, 评论 - 81, 引用 - 0
数据加载中……

Southeastern Europe 2007 解题报告


A . John

PKU 3480 http://poj.org/problem?id=3480

题意:N堆石子,两人轮流从其中一堆中取任意石子,最后一个取完石子的人输。

题解:博弈。

1) 当所有石子的SG值异或和不等于0时:

a) 个数大于1的堆数=0,必定是奇数个1,所以先手必输;

b) 个数大于1的堆数=1,总能想办法将局面变成奇数个1,所以先手必胜;

c) 个数大于1的堆数>1,总能取掉某些石子,使得所有石子的SG值异或和为0,并且个数大于1的堆数至少还剩两堆;

2) 当所有石子的SG值异或和等于0时:

a) 个数大于1的堆数=0,必定是偶数个1,先手必胜;

b) 个数大于1的堆数=1(不存在);

c) 个数大于1的堆数>1,无论怎么取,SG值异或和都不可能为0。并且无论先手怎么移,后手可以要么进入偶数个1的状态,要么保持SG值和为0并且非全1的状态(该状态先手必输),所以这种情况,先手必败。

由于1) 的c)情况可以到达2的c)情况,所以1的c)情况为先手必胜点。

 

B . Double Queue

PKU 3481 http://poj.org/problem?id=3481

题意:给定一些数据(K,P)和一些询问,K为数据值,P为优先级,每次询问输出当前优先级最高或者最低的数据的K的值,询问完删除这个数据。

题解:平衡树。

可以用SLT的set(内部也是平衡树的实现)水过去。

 

C . JBC

PKU 3482 http://poj.org/problem?id=3482

题意:进制转换,数字位可以是任何的可见ASCII码,求所有可能进制下的串转换成十进制后的和。

题解:模拟进制转换,模拟大数运算。

 

D . Loan Scheduling

PKU 3483 http://poj.org/problem?id=3483

题意:给定N(N <= 10000)个任务,每个任务是一个二元组(Pi, Di),表示如果在[0, Di]的某个时刻内完成则可以得到Pi的利润,每个时间点最多只能有L(L <= 100)个任务,求取一个任务子集来完成的的最大利润总和。

题解:贪心。

初始化每个时间点的可用任务数为L,初始化任务利润和S。

将所有任务按Pi从大到小排序,对于每个任务,从Di到0枚举它的完成时间t,如果t这个时间点还有可用任务,累加Pi到S,并且将t这个时间点的可用任务数减1,枚举完所有任务后S即为所求。

 

E . Showstopper

PKU 3484 http://poj.org/problem?id=3484

题意:给定一些三元组(X, Y, Z),一个三元组表示满足X + K*Z <= Y (K = 0, 1, 2, 3 ... ) 的所有正整数 X + K*Z出现了一次。对于多个三元组,保证所有数中至多只有一个数出现奇数次,求这个数以及它出现的次数。

题解:二分答案。

对于出现奇数次的那个数T,那么如果小于T的所有数的和必定是偶数,大于等于T的所有数的和必定是奇数,利用这一点可以二分枚举这个T,然后利用所有小于等于T的数的个数的奇偶性进行二分判定。

对于某个三元组(X, Y, Z),小于等于T的个数分几种情况讨论:

1) 当T >= Y,个数为 (Y-X)/Z + 1;

2) 当T < X,个数为0;

3) 当 X <= T < Y,个数为 (T-X)/Z + 1;

每次枚举T,将所有区间的数相加判断奇偶性即可。

 

F . Highway

PKU 3485 http://poj.org/problem?id=3485

题意:给定一条高速公路的长度L(范围为0到L)和N个村庄,要求在高速公路上建一些出口,使得每个村庄到高速公路至少有一个出口的距离不大于D,并且出口总数最少。

题解:贪心。

计算出每个村庄到高速公路距离D范围内的左右区间[Li, Ri],对这些区间进行排序,排序规则为如果左端点一致则按照右端点递增排序,否则按照左端点递增排序。然后按左端点递增枚举每个区间(每个区间对应一个村庄),对于尚未有高速公路可达的村庄,在其右端点建立一个出口(贪心所在,因为是从左往右扫描,所以在右端点建出口肯定比左端点建更优),然后将它之后的左端点坐标小于这个出口的区间全部hash掉(因为那些村庄可以用这个出口,无须建立新的出口),直到所有区间枚举完毕,出口数也就得出了。

 

G . Computers

PKU 3486 http://poj.org/problem?id=3486

题意:故事背景是每年都要更换电脑或者进行一次维修,如果换电脑需要c的花费,如果不换电脑,那么第y年到第z年( 1 <= y <= z <= n)的总维修费用为m[y][z],求经过n年的最小花费。

题解:动态规划。

DP[i]表示经过i年的总开销,假设从第j年开始买了一台新的电脑,一直用到了第i年,那么前j年的总开销为DP[j],从第j+1年到第i年的维修开销加上购买花费c,即DP[j] + m[j+1][i] + c,DP[i]就是这些开销中的最小值,即。

DP[i] = min{ DP[j] + m[j+1][i] + c, 0 <= j < i };

 

H . The Stable Marriage Problem

PKU 3487 http://poj.org/problem?id=3487

题意:n(n < 27)对男女,每个男人有对所有女人的好感度,每个女人也有对所有男人的好感度,A对B的好感度记为G(A, B), 求找出一种稳定的婚配关系,使得对于任意一对夫妇X(M, W),不存在 G(XM, YW) > G(XM, XW) 并且 G(XW, ZM) > G(XW, XM),并且要求男士优先考虑(即男方如果能找到好的一定不会更差的)。通俗的讲,就是XM更加喜欢别人的老婆,Xw更加喜欢别人的老公,这样的婚姻是不稳定的,双方都有可能出现外遇。

题解:稳定婚姻经典算法。

由于是男士最优,所以需要模拟男士求爱的方式。

用L[i][j]表示i号男子喜欢的第j个女子的编号;

用R[i][j]表示i号女子对j号男子的评分(越大评分越高,且对于确定的i肯定互不相同);

算法如下:

1) 将所有的男子以及他们向多少个女人求过婚的信息入队,每次弹出一个男子M,找到他下一个要求婚的对象(求婚顺序按照对女生的好感度顺序进行)。

a) 如果当前求婚对象W没有配偶,直接配对,记Match[ W ] = M;

b) 如果当前求婚对象有老公,即Match[ W ],那么检查M 和 Match[ W ]在W的评分,如果M的评分大于W的老公,则迫使其改嫁,前夫入队,Match[ W ] = M;否则,该男子M继续入队;

2) 反复进行1)直到所有人都找到的对象。

 

I . Arne Saknussemm

PKU 3488 http://poj.org/problem?id=3488

题意:简单字符串模拟。

题解:根据题意做就行了。

 

 

 

 

posted on 2014-06-01 00:03 英雄哪里出来 阅读(805) 评论(0)  编辑 收藏 引用 所属分类: 区域赛 解题报告


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理