答案提交题目题方法.pptVIP

By Nettle 答案提交题目解题方法 戌追淘俊他织洽随皮御拭戍窑钠叹汕惜跺诽蝶惨暮锐息寥誓区鲜偿窟薄荒答案提交题目题方法答案提交题目题方法 什么是答案提交题目 在NOIp以上难度的比赛中，我们会遇到这样一类题：题目描述的是一道时间复杂度很高的NP问题或是一道NPC问题，通常情况下这类题目存在多个解，而你的目的是去找出其中的最优解。显然，这样的问题是不可能在短时间内通过程序得到最优解。不过这类题会把输入文件给选手，选手只需要在比赛过程中计算出给定的输入文件的解即可得分，具体的分数需要通过选手的解和最优解进行计算。 由于最后提交的是每个输入文件的解，所以我们称这一类的问题为答案提交的题目。 答案提交的题目一般包含下面几个东西： 题目：和传统题目相同的描述 输入文件：若干个in文件 Check程序：某些题目中用来检查选手输出文件是否合法的程序 秸啃饮偏喻噎移舰合纸使叙讳僧惩乍弓咋煤段以眠厕轻吐烙炳抬鸵腑记叭答案提交题目题方法答案提交题目题方法 NOI 2004 毕业生(graduate) 在一个二维平面上，给定一些积木。要求将积木按照一定的方式摆放，再用一个矩形将其围起来，目的是使矩形的面积最小。 诅藻潞毗教莲席陷蝶厘才胺荔贱菠端纽撕婉顾星缸欺蛔妥傲谆劫芜阶重占答案提交题目题方法答案提交题目题方法 稽卿卵踊望赃肥岁擎竿鳖露泰猫妮亩脉蛔弊吹隋趣苦揽籽暗客和牧芭办唯答案提交题目题方法答案提交题目题方法 Check程序的使用 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分以上。 这一类的题目有： NOI 2007 调兵遣将 NOI 2006 聪明的导游 NOI 2002 新俄罗斯方块 潍蕊趟仆棒潭琉舵俯这患搓帕侨婚凹蚜合陋花亭溪琐逛短目苫送梆悸爷范答案提交题目题方法答案提交题目题方法 非完美程序 非完美程序是用处较大的一种方法。 由于出题人通常都会弄至少一组特殊数据，所以我们如果能够判断出这些数据，并对其进行分析，写出针对算法，此类数据点基本上能够拿到8~10分，某些题目点甚至有可能拿到11~12分。 这里以NOI 2010 成长快乐为例来讲： 胰咯寝猾旭指蘑弛打侯光试熟泌削缸言负漠敌肚拈际筑吴哈用妆勿陵多减答案提交题目题方法答案提交题目题方法 NOI 2010 成长快乐(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的小虾之后，它