荔园在线
荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀
[回到开始]
[上一篇][下一篇]
发信人: kaman (天外飞仙), 信区: ACMICPC
标 题: [解题分析]Warming Up for GDCPC2005(zz From STU)
发信站: 荔园晨风BBS站 (2005年05月09日08:33:19 星期一), 站内信件
解题分析
Warming Up for GDCPC'2005 (STU May. Monthly Contest)
1001 Divide Apples
数论问题，考查大素数筛选算法，以及偶完全数产生理论。M= 2^(n-1) * (2^n-1)
，当(2^n-1)是素数，则M是一个偶完全数，基于目前为止尚未发现奇完全数的存在，
因此不需加以考虑。分别当n=2, 3, 5, 7, 13, 17, 19, 31时，所产生的M都是小于
2^63的偶完全数。
难度，中等。视情况而定，知道偶完全数理论，则是简单题，可以直接交表。
1002 Planning My Corporation
图论问题，考查最短路内容的服务中心算法，可以在Dijstra算法的基础上加以枚举
N个点，选取运输量最少的，作为服务中心。算法复杂度O(N^3)。要注意考虑1个点，
2个点的边缘数据。
难度，中等。
1003 Date 2 Months Later
数论问题，考查对时间日期的计算，注意闰年和平年的二月份的日数，以及年份要
逢12进一，则问题容易解决。
难度，简单。
1004 Rotating Rectangle
数论问题，考查优化矩阵元素求和，必须先根据给出的M×N的矩阵，分别求出所有
主副对角先以上以下的元素之和，再根据给出的旋转矩形的x, y, w, h，通过预先算
好的部分元素和，矩阵的元素总和，减去四个角的三角块的元素和，再加上旋转矩形
的边界上元素和，即可。算法复杂度要求O(M*N+Q)。凡是简单的直接枚举或者优化的
枚举，都过不了。直接枚举复杂度O(w*h*Q)；优化的枚举也要O(M*N+Q*(w+h))。
难度，较难。
1005 Gain All the Diamonds
几何问题，考查求多边形质心，求凸包，求面积，求两点距离的算法。关键要有扎
实的计算几何的问题求解的基础，否则不知从何入手求质、凸包、面积等。同时，要
注意题目规定使用的精度1E-10，结果保留小数后两位。要注意边缘数据，diamond的
数目为1，2时的输出，以及diamond的质心发生重叠的情况。
难度，较难，处理比较麻烦。
1006 The Puzzling Twelve Pieces
图论内容，考查深度搜索算法。必须根据给定的十二块积木，每块有8种不同的状态
，可以翻转或者旋转，搜索所有可能拼成棋盘的方案。必须注意数据无解的情况，如
1×60, 2×30, 13×3……这些都是无解的，必须列或行数都大于等于3,而且棋盘格
数必须是60。而且，要注意深度搜索的复杂度，从行或者列中选取较小者展开深度搜
索，以提高效率。
难度，难。
1007 Reverse Points
几何问题，考查分治法。找出所有满足 x1<x2, y1>y2 的所有点的对数。由于规模
较大，必须使用O(NlogN)的算法，先对N个点，按x坐标从小到大排序；然后再对已经
按x有序的N个点，采用分治的思想，按y坐标进行归并统计。
难度，较难。
1008 Game 24
数论问题，考查24点的计算，由于运算符只有加、减、乘、除、括号5种运算，规模
较小，可以直接枚举求解。
难度，中等。
1009 Hold a Party
推理杂题，考查组合、枚举、标记、奇偶关系等内容，需要全面考虑coins的up, down
两种不同状态的标记，以及枚举四个人的不同操作的组合，最后把可能存在的状态排
序并输出。注意问题的规模，不能直接搜索，需要通过标记状态进行限定剪枝。
难度，较难。
汕头大学ACM/ICPC集训队
2005年5月8日星期日
--
最近正在研究怎样把时间锁住......
※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.52.93]
[回到开始]
[上一篇][下一篇]
荔园在线首页 友情链接：深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店