答案提交题目解题方法

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,By Nettle,答案提交题目解题方法,什么是答案提交题目,在NOIp以上难度的比赛中，我们会遇到这样一类题：题目描述的是一道时间复杂度很高的NP问题或是一道NPC问题，通常情况下这类题目存在多个解，而你的目的是去找出其中的最优解。显然，这样的问题是不可能在短时间内通过程序得到最优解。不过这类题会把输入文件给选手，选手只需要在比赛过程中计算出给定的输入文件的解即可得分，具体的分数需要通过选手的解和最优解进行计算。,由于最后提交的是每个输入文件的解，所以我们称这一类的问题为答案提交的题目。,答案提交的题目一般包含下面几个东西：,题目：和传统题目相同的描述,输入文件：假设干个in文件,Check程序：某些题目中用来检查选手输出文件是否合法的程序,NOI 2004,毕业生,(graduate),在一个二维平面上，给定一些积木。要求将积木按照一定的方式摆放，再用一个矩形将其围起来，目的是使矩形的面积最小。,graduate1.ingraudate2.in,Check,程序的使用,Windows,系统下：在命令行,cmd,中，进入存放,.in,和,.out,文件的文件夹，此时须保证,check,程序也在该文件夹，调用命令：,check,Linux,系统下：在终端中，进入存放,.in,和,.out,文件的文件夹，同样须保证,check,程序存放在该文件夹，调用命令：,./check,其中,表示测试数据的编号。,调用命令不一定是上面两种，需要根据题目说明决定。但是调用时当前目录一定要为数据文件夹。,答案提交题目常用解题方法,借助图画、记事本等工具手算,写搜索程序，算可行解,(,答案提交的题通常提交即可得,1,分,),非完美程序，针对特殊数据写特殊算法,启发式搜索,借助图画、记事本等工具手算,通常情况下，所有提交答案的题目前23个点数据范围都比较小，可以手算。,比方说刚刚看过的题目?毕业生?，此题前5个点均可以通过观察数据进行手动验证，大概花上1个小时能够拿到4050分。,在NOI考场上是会发放草稿纸的，不够了应该还是可以继续要。所以多动动笔就能够拿到一定的分数。,搜索程序,搜索程序可以拿到根本分。,对于某些有解即可得分的题目，可以考虑搜索算法，求出任意一个可行解，这样可以至少保证拿到1分。如果Rp比较好，也有可能拿到5分以上。,这一类的题目有：,NOI 2007 调兵遣将,NOI 2006 聪明的导游,NOI 2002 新俄罗斯方块,非完美程序,非完美程序是用处较大的一种方法。,由于出题人通常都会弄至少一组特殊数据，所以我们如果能够判断出这些数据，并对其进行分析，写出针对算法，此类数据点根本上能够拿到810分，某些题目点甚至有可能拿到1112分。,这里以NOI 2021 成长快乐为例来讲：,NOI 2021 成长快乐(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是不可能追上虾米的。同样可以用动态规划在这样的数据上拿到810分。,启发式搜索,启发式搜索算法有很多种：,蚁群算法、遗传算法、模拟退火、禁忌搜索、爬山法、,其中较常用的是模拟退火和爬山法。,模拟退火的核心思想是随机概率接受,爬山法那么是极大概率贪心+极小概率无条件接受,模拟退火,首先引入假设干概念：,状态：当前解,邻接状态：当前解可以通过某中方式到达的其他解,评估值：状态的价值，具体函数由题目决定，用来判断解的优劣,具体的操作流程为：对于当前状态，计算出其评估值。在一定次数和范围内，对其邻接状态计算评估值，并一定概率接受某邻接状态为当前状态。持续进行，最后到达一个较优的解。,伪代码,Pos Initialization,Val Evaluate(Pos),k 0,while k emax Then,_Pos Neighbour(Pos),_Val Evaluate(_Pos),If Random()P(Val,_Val)Then,Pos _Pos,Val _Val,End If,k k+1,End While,Return Pos,爬山法,算法流程如下：对于当前状态，搜索它一定数量的邻接状态，取出其中评估值最优的邻接状态Best，假设Best的评估值优于当前状态，将Best作为当前状态；否那么随机一定的概率，接受Best作为当前状态。此时假设仍然无法接受，当前状态为此次爬山的终点。在程序计算过程中屡次从不同的起点进行爬山，可以保证得到的解比较优。,由于这种算法的感觉像是不断的在爬上坡，所以称之为爬山法。如果改变方向，也可称之为下山法。,伪代码,Pos Initialization,while True Then,Val Evaluate(Pos),k 0,BestVal 0,while k BestVal Then,Best _Pos,BestVal _Val,End If,k k+1,End While,If BestVal Val or Random P()Then,Pos Best,Else,Break,End If,End While,Return Pos,NOI 2021 赛程安排(match),随着奥运的来临，同学们对体育的热情日益高涨。在NOI2021来临之际，小C和小S正筹划组织一场乒乓球赛。小Z作为一名狂热的乒乓球爱好者，这正是他大展身手的好时机，于是他摩拳擦掌，积极报名参赛。,本次乒乓球赛采取淘汰赛制，获胜者晋级。恰好有n(n是2的整数次幂，不妨设n=2k)个同学报名参加，因此第一轮后就会有2k-1个同学惨遭淘汰，另外2k-1个同学晋级下一轮；第二轮后有2k-2名同学晋级下一轮，依次类推，直到k轮后决出冠亚军：具体的，每个人都有一个1n的初始编号，其中小Z编号为1，所有同学的编号都不同，他们将被分配到n个位置中，然后按照类似以下图的赛程进行比赛：,NOI 2021 赛程安排(match),为了吸引更多的同学参加比赛，本次比赛的奖金非常丰厚。在第i轮被淘汰的选手将得到奖金ai元，而冠军将获得最高奖金ak+1元。显然奖金应满足a1 a2 ak+1.,在正式比赛前的热身赛中，小Z连连败北。经过认真分析之后，他发现主要的失败原因不是他的球技问题，而是赢他的这几个同学在球风上刚好对他构成相克的关系，所以一经交手，他自然败阵。小Z思索：如果在正式比赛中能够避开这几位同学，该有多好啊!,由于有着良好的人缘，小Z掌握了选手两两之间交手的胜率，即选手A战胜选手B的概率为PA,B(保证PA,B+PB,A=1)。而小Z的伙伴小C和小S作为球赛的组织者，将负责赛程的安排。于是小Z希望能够通过他们的帮助来确定比赛的对阵形势重新给每个选手进行编号，从而能够使得他获得尽可能多的奖金。你能帮助小Z安排一个方案，使得他这场比赛期望获得的奖金最高么？,分析,首先此题的状态很明显是一个全排列，要求是第一位是1，那么枚举所有情况的时间复杂度为O(N-1)!)。对于数据范围在20以上的测试点已然无法在短时间内解出，所以我们采用爬上法来解决。,定义一个排列为当前状态，随机交换其中任意两个数字的位置作为邻接状态。设定好枚举次数，评估值为当前全排列能够拿到的奖金。,这样就算是把爬山法的模型套上了，接下来只需要不断的运行程序，调整爬山次数和寻找邻接状态的次数(kmax)即可。,在NOI前我们用了一整天的时间来跑此题，最后根本上都拿到了7090分。赛场上估计能够拿到70分左右，当然这题也有特殊数据，正式比赛上最高分是tanky，90+分。,总结,拿到答案提交的题目一般做题步骤：,审题,浏览一遍数据，尝试找出特殊数据,思考并写出通用程序,让程序开始计算大数据，同时手动计算小数据，并开始设计特殊数据的特殊程序,计算出特殊数据，并在剩下的时间里，不断跑非特殊数据。这个时候你可以做其他题目。,提醒：,善用check程序，最好能够熟练使用bat和cmd。,最多花23个小时(NOI)在答案提交题目上根本可以拿到50分以上。,