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

Greater New York Regional 2009 解题报告

A.Nth Largest Value
       PKU 3781 
http://poj.org/problem?id=3781

水题,求10个数中第3大的数。

 

B.Equal Sum Partitions
       
PKU 3782 http://poj.org/problem?id=3782

       题意:给定一个M(M <= 10000)个元素的序列,将它切割成K块,每块的和相等,求最大的K

       题解:枚举。

       首先,切成K块,每块和相等,那么这个和必定是M个元素总和的一个因子,那么可以枚举第一个块的长度(M种),判断当前块的和是否能被所有数的总和整除,如果可以,顺序判断可行性,看似复杂度是O(M^2),但是能否整除这个剪枝可以筛选掉绝大部分情况。

 

C.Balls
       
PKU 3783 http://poj.org/problem?id=3783

题意:给定B (B <= 50) 个一样的球,从 M (M <= 1000) 层楼上一个一个往下扔,存在某个楼层K,使得低于它的楼层往下扔球,球不会碎,在第K层扔下去会碎。求最坏情况下,需要扔几次才能确定这个K

题解:动态规划。

DP[i][j]表示总楼层为i,持有j个球时,最坏情况需要的次数;

那么如果从k ( 1 <= k <= i) 层进行扔球,有两种情况:

1) 如果球不碎,则还需要进行DP[i-k][j]次测试(向更高的楼层进发);

2) 如果球碎,那么还可以进行的次数为DP[k-1][j-1] (损失了一个球);

由于要考虑最坏情况,所以每次测试必须取(1) (2)中的大者+1,每次选定一个楼层,使得这个楼层往下扔球的结果的最大值最小,也即状态转移方程为:

DP[i][j] = Min( DP[i][j],  Max(DP[i-k][j], DP[k-1][j-1]) + 1 );

Pku上有道和这题想法类似的题:http://poj.org/problem?id=1243

 

D.Running Median
       
PKU 3784 http://poj.org/problem?id=3784

       题意:一个长度为M(M <= 9999)的序列,每次奇数位的数读入的时候计算前面整个序列的中位数。

       题解:二分 + 树状数组。

       由于数字是int32范围,所以首先需要将所有数离散到下标,枚举每一个数字读入,将对应位的数字下标插入到树状数组中,每当读到奇数个的时候,利用树状数组的成端求和的性质,如果要找第K大的数,那么就二分一个答案,然后查询树状数组,如果求和大于等于K,表示是一个候选解(因为要保证大于等于K的数最小,才是第K大的数),反复二分,直到找到最小的值V满足sum(V) >= K,时间复杂度O(2 *M * log(M) )

 

E.The Next Permutation
      
PKU 3785 http://poj.org/problem?id=3785

题意:给定一个可重复元素的排列A[i],求下一个排列。

题解:从后往前扫描,对于第i个元素A[i],如果能够找到一个j,使得A[j] > A[i],并且满足A[j]是继第i位之后最小的数,那么将A[i]A[j]进行交换,然后将A[i+1]到末尾的元素进行一次不降序排序,最后得到的串就是解。

 

F.Adjacent Bit Counts
      
PKU 3786 http://poj.org/problem?id=3786

题意:求长度为n的二进制整数中,相邻两个1的对数有k对(可重复使用)的整数个数。

题解:动态规划。

令长度为n,相邻1的对数为k的数的个数为DP[n][k],其中以0结尾的为DP[n][k][0],以1结尾的为DP[n][k][1],那么 DP[n][k] = DP[n][k][0] + DP[n][k][1]

并且有如下状态转移方程:

1) 长度为n-1的二进制数在末尾加上一个0,相邻1的对数不变,所以有:

DP[n][k][0] = DP[n-1][k][0] + DP[n-1][k][1];

2) 长度为n-1的二进制数在末尾加上一个1,相邻1的对数取决于,第n-1位是0还是1,当第n-1位是1,相邻1的对数+1;当第n-1位是0,相邻1的对数不变,所以有:

DP[n][k][1] = DP[n-1][k][0] + DP[n-1][k-1][1];

并且初始状态下DP[0][0][0] = 1,  DP[0][0][1] = 0

 

G.Convex Hull of Lattice Points

PKU 3787 http://poj.org/problem?id=3787
     题意:凸包。

题解:Graham扫描法求解即可。

 

 

H.Interior Points of Lattice Polygons

PKU 3788 http://poj.org/problem?id=3788
     题意:给定一个凸多边形,求它内部所有的水平线段。

题解:从多边形第一个点的y坐标开始,递减枚举水平线段的y坐标,分别和多边形的n条边进行求交点;

1) 如果水平线段和多边形某条边共线,说明正好到了多边形的边缘,无须往下枚举,跳出循环。

2) 如果水平线段和多边形小于一个交点,那么当y轴再次减小的时候,必然没有交点,也无须继续枚举。

3) 否则,将左端点坐标取上整x1,右端点取下整x2,如果x1 <= x2 将它插入到解集中。

 

 

posted on 2014-05-28 08:25 英雄哪里出来 阅读(996) 评论(1)  编辑 收藏 引用 所属分类: 区域赛 解题报告

评论

# re: Greater New York Regional 2009 解题报告  回复  更多评论   

超赞
2014-05-28 11:06 | 鸟哥

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