答案提交题目解题方法

ByNettle答案提交题目解题方法什么是答案提交题目在NOIp以上难度的比赛中，我们会遇到这样一类题：题目描述的是一道时间复杂度很高的NP问题或是一道NPC问题，通常情况下这类题目存在多个解，而你的目的是去找出其中的最优解。显然，这样的问题是不可能在短时间内通过程序得到最优解。不过这类题会把输入文件给选手，选手只需要在比赛过程中计算出给定的输入文件的解即可得分，具体的分数需要通过选手的解和最优解进行计算。由于最后提交的是每个输入文件的解，所以我们称这一类的问题为答案提交的题目。答案提交的题目一般包含下面几个东西：题目：和传统题目相同的描述输入文件：若干个in文件Check程序：某些题目中用来检查选手输出文件是否合法的程序NOI2004毕业生(graduate)在一个二维平面上，给定一些积木。要求将积木按照一定的方式摆放，再用一个矩形将其围起来，目的是使矩形的面积最小。

graduate1.in

graudate2.inCheck程序的使用Windows系统下：在命令行cmd中，进入存放.in和.out文件的文件夹，此时须保证check程序也在该文件夹，调用命令：check<Number>Linux系统下：在终端中，进入存放.in和.out文件的文件夹，同样须保证check程序存放在该文件夹，调用命令：./check<Number>其中<Number>表示测试数据的编号。调用命令不一定是上面两种，需要根据题目说明决定。但是调用时当前目录一定要为数据文件夹。答案提交题目常用解题方法借助图画、记事本等工具手算写搜索程序，算可行解(答案提交的题通常提交即可得1分)非完美程序，针对特殊数据写特殊算法启发式搜索借助图画、记事本等工具手算通常情况下，所有提交答案的题目前2~3个点数据范围都比较小，可以手算。比如说刚刚看过的题目《毕业生》，此题前5个点均可以通过观察数据进行手动验证，大概花上1个小时能够拿到40~50分。在NOI考场上是会发放草稿纸的，不够了应该还是可以继续要。所以多动动笔就能够拿到一定的分数。搜索程序搜索程序可以拿到基本分。对于某些有解即可得分的题目，可以考虑搜索算法，求出任意一个可行解，这样可以至少保证拿到1分。如果Rp比较好，也有可能拿到5分以上。这一类的题目有：NOI2007调兵遣将NOI2006聪明的导游NOI2002新俄罗斯方块非完美程序非完美程序是用处较大的一种方法。由于出题人通常都会弄至少一组特殊数据，所以我们如果能够判断出这些数据，并对其进行分析，写出针对算法，此类数据点基本上能够拿到8~10分，某些题目点甚至有可能拿到11~12分。这里以NOI2010成长快乐为例来讲：NOI2010成长快乐(Nemo)Nemo是一条无忧无虑的小鱼，它的初始体重为w0。可爱的Nemo希望自己能够尽快地成长，因此需要吃尽量多的食物。Nemo最喜爱的食物是海里的小虾。已知Nemo对食物的情况了解如下：大海里共有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的小虾之后，它的体重将增加wi。注意，小虾不会吃Nemo，且小虾之间也不会自相残杀。Nemo希望你来帮助它制定一个成长计划，使得它吃掉的小虾重量总和尽量大。特殊数据分析本题给了下面两类特殊数据：第一类

数字金字塔：在这类数据里，虾米都是不会移动的。而虾米的位置恰好排成一个金字塔形。由于时间上的限制，所以Nemo刚好能够从上到下走一次。这样就完全转化成了一个数字金字塔，只需要用二维动态规划求出最优解即可拿到10分。第二类接礼物：这类数据中，虾米都以超高的速度从上向下垂直移动，而Nemo处于最底层。在计算中，Nemo只需要左右移动，就能够吃到一定数量的虾。当然Nemo是不可能追上虾米的。同样可以用动态规划在这样的数据上拿到8~10