荔园在线
荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀
[回到开始]
[上一篇][下一篇]
发信人: icylord (Dragon Quest ::}::::::::>), 信区: ACMICPC
标 题: 2007年广东省赛GDCPC2007题目总结(zz)
发信站: 荔园晨风BBS站 (Wed Apr 25 21:15:17 2007), 站内
发信人: Merlin (Merlin), 信区: ACMICPC
标 题: 2007年广东省赛GDCPC2007题目总结
发信站: 逸仙时空 Yat-sen Channel (Wed Apr 25 20:40:10 2007), 站内信件
本次广东省赛一共有10道题，从整体来说，总体难度上要比上年低，但简单题相比去年
要有所加难，但没有严格意义上的在比赛其间不可做的难题。在10题中，只有一题（E题
）没有队伍做出来。
第一题（A）是一道计算几何题，求两个互相不相交的两个点集的最远点对。由于点数多
（100,000点），因此不能直接用两重循环来做。这题题目中没有明确表示两个点集是不
相交的，需要从数据范围可看出是不相交。当能发现这点以后，就可在求凸包基础上通
过绕圈的方式求最远点对。因此这题实际上是考察选手的分析能力及灵活运用几何知识
的能力。这题限时5秒，但不超时都能在3s内出结果，而超时的都在10s以上，这题一共
虽然有179个提交，46队提交，但是大部分都是超时，只有5队AC。
第二题(B)是本次比赛最简单的题目，考察的就是选手最基本的编程能力，当能够灵活运
用数组这一基本数据结构的话，那么这题就非常简单了。这题在比赛中所有队伍都做出
来。
第三题（C）是一道基于操作系统扇区访问的题目。首先，考虑是n个磁头去访问n个扇区
时，那么就是把这两者位置排序，然后按照从小到大安排即可。现在题目要求n+1个磁头
访问n个扇区，多出来的磁头最简单的办法就是枚举了。因此这题实际考察的算法就是枚
举和贪心算法。本题时限要求是1s，这题一共有69支队伍243次提交，共42支队通过。
第四题（D）是求一个矩阵中每个从左上角开始的子矩阵一共有多少个不同的元素。这题
矩阵大，矩阵的元素相应就多，使该题的难度非常大。因此需要非常好的方法去减少复
杂度。首先是要对矩阵内的所有元素进行排序，然后逐行扫描矩阵，记录每种数字出现
的最小列数，并用树状数组统计前k列出现了多少种数。当然，这题也可以用哈希的办法
实现。这题考察的是选手对高级数据结构的掌握及设计算法能力。这题数据就有12兆，
因此限时15秒，通过的队伍最长时间为11秒，这题一共有30支队伍89个提交，这题也是
与第一题类似，大部分都是超时，只有3队通过。
第五题(E)的理论背景是图论中的哈林图中的最优哈密尔顿圈问题，为了降低难度，做了
一些简化。经典的哈密尔顿圈是NP-难问题，不可能在多项式时间内解决，但是这题的图
比较特殊，因此可以使用树状动态规划来解决。通过从最左子结点到最右子结点行走路
径的不同情况进行考虑，得出一个可符合最优化原理的树形DP方案。这题也是考察选手
的综合分析能力，是一道非常有意思的题目。3个提交，没队伍通过。
第六题(F)是计算当一棵树有n个结点，k个叶子时的数量。由于该题提供了Prufer编码方
式，因此实际上就是求Prufer编码的个数。这道题是考察选手发掘题目信息能力，同时
也考察选手组合数学功底。22支队伍55个提交，2队通过。
第七题(G)乍看起来是一道在树上进行的博弈题目，但是只要深入去考虑，并且多点尝试
，就不难看出这道题本质就是求每个人对应结点的深度之和的差值。因此这题本质是一
道简单的树的遍历问题。94支队伍243个提交，87队通过。这题由于题目描写不够清晰，
理解存在分歧，导致在比赛过程中judge有误差，现在我们已经对所有提交都进行重测，
两种理解都认为是正确的。
第八题(H)是猴子分香蕉问题。本题给定了一组规则与猴子数的上限，要求符合要求的第
K小的香蕉数，其数学模型是一个求生成集合的第K小数，设计适当的生成过程使生成出
来的数量是递增的，然后使用堆这一数据结构对结果进行保存。考察选手数学建模及问
题转化能力。5支队伍28个提交，1队通过。
第九题(I)是求一个连通图上，当把某些边删掉以后，要恢复多少条边才可让ab连通。这
题可简单的转化为最短路来做，把删掉的边的权值设为1，没有删掉的即为0，然后求一
个从a到b的最短路即可。考察选手的图论知识及最短路算法的掌握。94支队伍215个提交
，79队通过。
第十题(J)是求一个图上一共有多少条从a到b的路径。当然，本题的图与一般的图是很不
一样的，是通过水管来定义的。分析这题知范围很小，因此可以直接使用深度优先搜索
的方法来求解，但是这题的操作比较多，因此程序相对繁琐，而这题就是考察选手对简
单搜索的掌握和编程能力。7支队伍28个提交，1队通过。
这次比赛冠军队伍做了8道题，亚军（1支队）6道题，4支队5道题，38支4道题，34支队
3道题，10支队2道题，12支队1道题。
--
有3个ACMER去一个闹鬼的教室自习。
鬼先变了恐龙，没吓着他们；
鬼又变了贞子,没吓着他们；
鬼变了强盗,没吓着他们；
鬼变了LTC，他们吓跑了...
※ 来源:·荔园晨风BBS站 http://bbs.szu.edu.cn·[FROM: 192.168.32.54]
[回到开始]
[上一篇][下一篇]
荔园在线首页 友情链接：深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店