2009年ACM选拔赛解题报告

PAGEPAGE32009年ACM选拔赛解题报告A.ArithmeticOperationsB.ChickensandRabbitsintheSameCage鸡兔同笼问题是一个经典的问题，也是我国古代数学的代表成就之一。用解方程的手段很容易解决这个问题。但在求解过程中要注意：脚的数量不能小于头的数量的两倍；脚的数量必须是偶数；求得的鸡的数量不能是负数；求得的兔的数量也不能是负数；等等。总之，做好这道题，可以锻炼用计算机解决问题时对问题的全面考虑，编写健壮性强的程序。C.SelectingTeamMembers这是一个选择问题，只要把在n个元素中选择k个元素的情况全部列出，然后在其中挑选出最大者，就可以解决这个问题。请参看下面的CCombination类/*使用方式：CCombinationc;c.init(5,3);while(c.next()){ //取出c.data[]中的数据操作}*/classCCombination{public: inttotal; intelite; int*data; voidinit(intgivenTotal,intgivenElite); BOOLnext(); ~CCombination();};CCombination::~CCombination(){ if(data!=NULL) delete[]data;}voidCCombination::init(intgivenTotal,intgivenElite){ total=givenTotal; elite=givenElite; data=newint[total]; data[0]=-1;//表示下一个才是开始，是第一个}BOOLCCombination::next(){ inti=0; if(data[0]==-1){ for(i=0;i<elite;i++) data[i]=i; returnTRUE; } intpos=-1; for(i=elite-1;i>=0;i--){ if(data[i]<total-elite+i){ pos=i; break; } } if(pos==-1) returnFALSE; data[pos]++; for(i=pos+1;i<elite;i++) data[i]=data[pos]+(i-pos); returnTRUE;}D.SpecialRelayRace解决这个问题可以考虑使用贪心思想。跑得最慢的人所花费的时间一定要记入总是间的，所以他要和那些最耗时的人一组，争取用自己的时间把跑得最慢的学生尽可能多地“带”出去。因此，最慢的k个人一组，除此之外最慢的另外k个人一组，一直到所有的人被分组。每组所耗时间就是该组中跑的最慢的人的耗时。解决技巧是把所有的学生耗时由多到少排序，这样便于分组操作。注意处理两种特殊情况：（1）最后一组不够k个人。（2）k大于学生总数。E.FactorMillionaire任何大于1的正整数n都可以表示成素因子幂次乘积的以下形式：正整数n的因子数量是：要把n进行因子分解需要一个素数表。1亿以内的数据的因子大小不会超过1万。因此，只需要1万以内的素数表，共有1229个，当然，如果代码量有限制，可以只输入1到100以内的素数，而用程序搜索100到1万之内的素数。F.SchedulingComputerLaboratories这是一个地道的实际问题，计算中心老师曾经咨询过我这个问题，我把题目要求原封不动地展示给了大家。此题可以用CCombination类解决，具体请参考前面另一个题目C.SelectingTeamMembersG.RegularBus用Dijkstra算法求解图中某节点到其它所有节点之间的最短路径，然后根据各个节点的人数，就可以知道所有人每天早晨行走的总路程。遍历所有的节点，就可以找出最优的节点。H.PugnaciousAnts这个问题最关键的一点就是判断平面上的两个三角形是否有重叠的部分。可以转换成两个三角形的三边是否有规范相交的边。如果知道了哪些三角形有重叠的部分，就可以用并查算法把这些三角形归类，能连通的归为一类。最后统计类的总数即可。两个三角形是否部分重叠的解决可以参考计算几何的有关文献，但要注意一个三角形中包含另一个三角形的情况。I.Right-AngledIsoscelesTriangles判断三个点构成的三角形是否是等腰直角三角形是容易的，但如果穷举所有的可能，将是O(n3)的运算量，肯定超时。可以用两个点构成一条线段，计算包含该线段的等腰直角三角形的另外一点的位置，然后查找这个点在所给的点列中是否存