答案提交题目解题方法

1、By Nettle答案提交题目解题方法什么是答案提交题目在NOIp以上难度的比赛中，我们会遇到这样一类题：题目描述的是一道时间复杂度很高的NP问题或是一道NPC问题，通常情况下这类题目存在多个解，而你的目的是去找出其中的最优解。显然，这样的问题是不可能在短时间内通过程序得到最优解。不过这类题会把输入文件给选手，选手只需要在比赛过程中计算出给定的输入文件的解即可得分，具体的分数需要通过选手的解和最优解进行计算。由于最后提交的是每个输入文件的解，所以我们称这一类的问题为答案提交的题目。答案提交的题目一般包含下面几个东西：题目：和传统题目相同的描述输入文件：若干个in文件Check程序：某些题目中用

2、来检查选手输出文件是否合法的程序 NOI 2004 毕业生(graduate)在一个二维平面上，给定一些积木。要求将积木按照一定的方式摆放，再用一个矩形将其围起来，目的是使矩形的面积最小。graduate1.ingraudate2.inCheck程序的使用Windows系统下：在命令行cmd中，进入存放.in和.out文件的文件夹，此时须保证check程序也在该文件夹，调用命令：check Linux系统下：在终端中，进入存放.in和.out文件的文件夹，同样须保证check程序存放在该文件夹，调用命令：./check 其中表示测试数据的编号。调用命令不一定是上面两种，需要根据题目说明决定。但

3、是调用时当前目录一定要为数据文件夹。答案提交题目常用解题方法借助图画、记事本等工具手算写搜索程序，算可行解(答案提交的题通常提交即可得1分)非完美程序，针对特殊数据写特殊算法启发式搜索借助图画、记事本等工具手算通常情况下，所有提交答案的题目前23个点数据范围都比较小，可以手算。比如说刚刚看过的题目毕业生，此题前5个点均可以通过观察数据进行手动验证，大概花上1个小时能够拿到4050分。在NOI考场上是会发放草稿纸的，不够了应该还是可以继续要。所以多动动笔就能够拿到一定的分数。搜索程序搜索程序可以拿到基本分。对于某些有解即可得分的题目，可以考虑搜索算法，求出任意一个可行解，这样可以至少保证拿到1分

4、。如果Rp比较好，也有可能拿到5分以上。这一类的题目有：NOI 2007 调兵遣将NOI 2006 聪明的导游NOI 2002 新俄罗斯方块非完美程序非完美程序是用处较大的一种方法。由于出题人通常都会弄至少一组特殊数据，所以我们如果能够判断出这些数据，并对其进行分析，写出针对算法，此类数据点基本上能够拿到810分，某些题目点甚至有可能拿到1112分。这里以NOI 2010 成长快乐为例来讲：NOI 2010 成长快乐(Nemo)Nemo是一条无忧无虑的小鱼，它的初始体重为w0。可爱的Nemo希望自己能够尽快地成长，因此需要吃尽量多的食物。Nemo最喜爱的食物是海里的小虾。已知Nemo对食物的情

5、况了解如下：大海里共有n只小虾，从1到n编号，其中编号为i的小虾的重量为wi。将大海看作一个X-Y坐标系，在0时刻编号为i的小虾所在的位置为(xi, yi)。小虾在大海中作匀速直线运动，其中编号为i的小虾的速度向量为(pi, qi)，即在时刻t，它的位置为(xi+pi*t,yi+qi*t)Nemo在0时刻的位置为(x0, y0)，它可以在海中随意移动，但速度不超过V。Nemo希望通过自己的努力，在T个单位时间内(含T时刻)吃到的小虾重量总和尽量大。当Nemo与某只小虾同时移动到同一个位置上，且小虾的重量小于Nemo当时的重量，则Nemo可以将该小虾吃掉。当Nemo吃掉重量为wi的小虾之后，它的

6、体重将增加wi。注意，小虾不会吃Nemo，且小虾之间也不会自相残杀。Nemo希望你来帮助它制定一个成长计划，使得它吃掉的小虾重量总和尽量大。特殊数据分析本题给了下面两类特殊数据：第一类 数字金字塔：在这类数据里，虾米都是不会移动的。而虾米的位置恰好排成一个金字塔形。由于时间上的限制，所以Nemo刚好能够从上到下走一次。这样就完全转化成了一个数字金字塔，只需要用二维动态规划求出最优解即可拿到10分。第二类 接礼物：这类数据中，虾米都以超高的速度从上向下垂直移动，而Nemo处于最底层。在计算中，Nemo只需要左右移动，就能够吃到一定数量的虾。当然Nemo是不可能追上虾米的。同样可以用动态规划在这样

7、的数据上拿到810分。启发式搜索启发式搜索算法有很多种：蚁群算法、遗传算法、模拟退火、禁忌搜索、爬山法、其中较常用的是模拟退火和爬山法。模拟退火的核心思想是随机概率接受爬山法则是极大概率贪心+极小概率无条件接受模拟退火首先引入若干概念：状态：当前解邻接状态：当前解可以通过某中方式达到的其他解评估值：状态的价值，具体函数由题目决定，用来判断解的优劣具体的操作流程为：对于当前状态，计算出其评估值。在一定次数和范围内，对其邻接状态计算评估值，并一定概率接受某邻接状态为当前状态。持续进行，最后达到一个较优的解。伪代码Pos InitializationVal Evaluate(Pos)k 0while

8、 k emax Then_Pos Neighbour(Pos)_Val Evaluate(_Pos)If Random() P(Val, _Val) ThenPos _PosVal _ValEnd Ifk k + 1End WhileReturn Pos爬山法算法流程如下：对于当前状态，搜索它一定数量的邻接状态，取出其中评估值最优的邻接状态Best，若Best的评估值优于当前状态，将Best作为当前状态；否则随机一定的概率，接受Best作为当前状态。此时若仍然无法接受，当前状态为此次爬山的终点。在程序计算过程中多次从不同的起点进行爬山，可以保证得到的解比较优。由于这种算法的感觉像是不断的在爬上

9、坡，所以称之为爬山法。如果改变方向，也可称之为下山法。伪代码Pos Initializationwhile True ThenVal Evaluate(Pos)k 0BestVal 0while k BestVal ThenBest _PosBestVal _ValEnd Ifk k + 1End WhileIf BestVal Val or Random P() ThenPos BestElseBreakEnd IfEnd WhileReturn PosNOI 2008 赛程安排(match)随着奥运的来临，同学们对体育的热情日益高涨。在NOI2008来临之际，小C和小S正策划组织一场乒乓球

10、赛。小Z作为一名狂热的乒乓球爱好者，这正是他大展身手的好机会，于是他摩拳擦掌，积极报名参赛。本次乒乓球赛采取淘汰赛制，获胜者晋级。恰好有n (n是2的整数次幂，不妨设n = 2k)个同学报名参加，因此第一轮后就会有2k-1个同学惨遭淘汰，另外2k-1个同学晋级下一轮；第二轮后有2k-2名同学晋级下一轮， 依次类推，直到k轮后决出冠亚军：具体的，每个人都有一个1n的初始编号，其中小Z编号为1，所有同学的编号都不同，他们将被分配到n个位置中，然后按照类似下图的赛程进行比赛：NOI 2008 赛程安排(match)为了吸引更多的同学参加比赛，本次比赛的奖金非常丰厚。在第i轮被淘汰的选手将得到奖金ai

11、元，而冠军将获得最高奖金ak+1元。显然奖金应满足a1 a2 ak+1.在正式比赛前的热身赛中，小Z连连败北。经过认真分析之后，他发现主要的失败原因不是他的球技问题，而是赢他的这几个同学在球风上刚好对他构成相克的关系，所以一经交手，他自然败阵。小Z思索：如果在正式比赛中能够避开这几位同学，该有多好啊!由于有着良好的人缘，小Z掌握了选手两两之间交手的胜率，即选手A战胜选手B的概率为PA,B (保证PA,B + PB,A=1)。而小Z的伙伴小C和小S作为球赛的组织者，将负责赛程的安排。于是小Z希望能够通过他们的帮助来确定比赛的对阵形势（重新给每个选手进行编号），从而能够使得他获得尽可能多的奖金。你

12、能帮助小Z安排一个方案，使得他这场比赛期望获得的奖金最高么？分析首先此题的状态很明显是一个全排列，要求是第一位是1，那么枚举所有情况的时间复杂度为O(N-1)!)。对于数据范围在20以上的测试点已然无法在短时间内解出，所以我们采用爬上法来解决。定义一个排列为当前状态，随机交换其中任意两个数字的位置作为邻接状态。设定好枚举次数，评估值为当前全排列能够拿到的奖金。这样就算是把爬山法的模型套上了，接下来只需要不断的运行程序，调整爬山次数和寻找邻接状态的次数(kmax)即可。在NOI前我们用了一整天的时间来跑此题，最后基本上都拿到了7090分。赛场上估计能够拿到70分左右，当然这题也有特殊数据，正式比赛上最高分是tan