hoi2009.doc

标题 HOI 2009 第一届HAPPY信息学奥林匹克竞赛 主办 漳平一中T团队 负责 支持 /t_hoi 概览 时限 : 3小时题量 : 4总分: 400难度 : NOIP 简介 NOIP2009即将举办，我们（T团队）特举办了第一届HOI（Happy Olympiad in Informatics），来给大家练练手。我们特参考了近几年的NOIP试题来确定试题的难度，大家应该放心了吧：试题难度不会大，但一定要注意细节，细节是此次比赛的关键。当然，也有压轴题存在。参加本次比赛的算法要求不高，和NOIP完全一致。无论是普及组还是提高组都适合参加本次比赛，只要你认真去做，每个人都可以拿到不错的分数，但如果你做的时候很马虎，就不敢给你保证了。您可以把这次比赛当作去年或前年的NOIP对待。同时，在NOIP中看完所有的题目是一个好习惯，你可能会有意外的收获。 HOI的全称是：Happy Olympiad in Informatics，您也可以理解为：Humorous Olympiad in Informatics。（别说这是山寨NOIP，我们有自己的理念。） 正如我们HOI的全称一样，我们的目的是开心OI，快乐OI，我们爱OI，因为我们乐于OI。 HOI版权说明 原创题的版权归出题人所有，但不保证所有HOI的试题都是原创题，非原创题会在题中特别说明，并且版权归原作者所有。 HOI最终解释权归漳平一中T团队所有。 最后祝大家和我们在NOIP 2009中取得好成绩！ 同时做个预告：HOI2010将于2010年8月的倒数第二个星期日下午同一时间举行，比赛地点择期通知（一般是VIJOS）！ 漳平一中T团队首次举办比赛，大家去捧捧场啊报名地址：/Test_Show.asp?id=1045VIJOS上不去的请在这里看题目：1.文件查找(filesearch.pas/c/cpp)【问题描述】WINDOWS是一个很庞大的操作系统（当然啦，看占的硬盘空间就知道了），比如说，它的文件查找系统。现在，请你用PASCAL或者C或者C+模拟一下这个操作过程。为了降低难度，所有的文件夹名和文件名都是小写和数字，且不考虑盘符，而且也不会有WINDOWS禁止出现在文件名中的字符。同时，为了增加难度，每个文件夹内可能有重名的文件（夹）。当然，不能让用户等太久，你的程序要在1秒内找到用户要的文件。【输入】(filesearch.in)输入文件filesearch.in包含多行，第一行是用户查找的文件名，该文件名不会含WINDOWS禁止出现在文件名中的字符，一定带符号”.”；第二行开始输入一个或多个文件夹的相关信息。文件夹的相关信息用以下格式输入：文件夹名（中间无空格，且无符号“.”（小数点）+ 一个空格+文件夹内的文件数（包括文件夹），如果文件夹内还有子文件夹，换行后先输入该子文件夹内容再输入父文件夹内的其他文件夹或文件。但文件夹内的文件（文件夹）是乱序的。每个文件名都带符号“.”。具体请看样例。【输出】(filesearch.out)输出所查找文件的路径，一定在至少一个文件夹的目录下。以WINDOWS地址的表示方法表示（“”），如果有多个文件，按输入时的顺序输出。每输出一个文件的路径换一行。【样例输入1】（符号“|”在每行的开头和结尾，表示此行开始和结束，以便选手确定前后是否有空格，您只需关注|间的内容，实际测评时无此符号，之后各题均如此。）|hoi.pas|hoi 2|hoi 0|hoi.pas|hoi.pas|【样例输出1】|hoihoi.pas|hoi.pas|【样例输入2】|chroi.pas|chroi 2|hoi 1|chroi.pas|chroi 1|hoi.pas|【样例输出2】|chroihoichroi.pas|【数据范围】对于50%的数据，输入文件的行数小于100。对于100%的数据，输入文件的行数小于3000，且每行均少于25个字符。2.开心农场(happyfarm.pas/c/cpp)【问题描述】这个夏天，与众不同。QQ空间也引入了最近流行的社区交互类游戏开心农场。自然而然地，Chroi也成为了众多农场主的一员。可是Chroi整个暑假忙于OI，没什么时间照顾农场，这就需要你的帮助了。他可以告诉你他每天那些时间可以上线，你要做的就是告诉他该天最多可赚多少钱（为了降低难度，假设腾讯每天晚上0:00清空还没收获的作物，而且由于Chroi的农场等级比较低，所以只能种单季作物（就是只能收获一次的）。在开心农场中，每个用户都有一定数目的土地，每次上线可以做的事是在土地上摘果实、卖果实、种下种子，每块土地上只能种一种作物，每块土地各自独立。假设Chroi每次只能上线1秒，他能在瞬间做完所有他想做的事，所以你的程序要在一秒内得出结果。而且如果Chroi在一天的最后时刻上线，那他此刻做的事算第二天的。（比如时间为24，那他在24时刻做的事算第二天的0时刻做的。）【输入】(happyfarm.in)输入文件包含多行，第一行有三个正整数n,m,t,k，分别表示Chroi的农场中有n块地，共有m种作物可以选择，一天的时间t，有k个时刻Chroi可以上线。接下来的m行每行输入三个正整数，第一个数字表示种子价格，第二个数字表示种子成熟时间（小于t），第三个数字表示成熟后果实的售价。再次提示，这些都是整数。再接下来的一行有k个自然数，保证该整数为0,1,2.t-1中的一个，为Chroi可以上线的时间。这k个自然数不会重复。输入文件到此结束。【输出】(happyfarm.out)输出文件只有一个整数，表示Chroi每天可以获得的最大金钱数。【样例输入1】|6 3 24 4|10 6 20|15 3 18|11 3 19|0 6 12 18|【样例输出1】|180|（共种了3次第一种作物，每次种6块土地，收获了3次，每次收获6块土地，最后一次上线18的时候只收获，不种植（之后不能再收获，再种植没时间收获，只能亏钱）【样例输入2】|1 1 24 2|10 6 5|0 6|【样例输出2】|0|（种第一种作物还亏钱，不如不种）【数据范围】对于30%的数据，0n=10,0m=50,0k=t=50。对于50%的数据，0n=20,0m=500,0k=t=500。对于100%的数据，0n=50,0m=3000,0k=t=3000，最后输出的数maxlongint。3.发电站(power.pas/c/cpp)【版权说明】本题为改编题。【问题描述】我国仍有许多贫困地区，解决这些地区的贫困问题，首先要从修路开始，接着是架设电网。现有某贫困县借助中央拨款已建设了公路，该县电力部门在该县的某位置建起了一个发电站，准备从这个发电站开始建立该县的电网。已知架设电线的时候，只能从已经通电的地方架设电线到它相邻的地方（对角线不叫相邻），每个地方都有一个价值，为此处通电的价值，各个地方的价值不同，比如居民区的价值就比较高。由于经费紧张，第一期工程中发电站只能让包括其本身所在区域的n个区域通电。同时，发电站还有一幅该县的地图，经过专家分析后得到了该县各个地方通电的价值。专家们把这幅地图划分成了x*y的方格，每个方格代表一个地方，其中发电站所在的方格的通电价值为1000，其他地方的通电价值为0到999之间的一个整数。你作为富有爱心的新一代，愿意支持该项目，那么请你帮发电站计算一下，架设电线使n个区域通电后可以得到的最大价值是多少，并告诉发电站有多少种架设方法可以得到最大价值。由于该县人民都急切地盼望着通电，所以你的程序不能运行太久浪费时间，它的运行时间不能超过一秒。【输入】输入文件的第一行是3个正整数：x,y,n。第二行到第x+1行是一个x*y的矩阵，对应地图上各个地方的通电价值，其中通电价值为1000的是发电站。矩阵中每行的每两个相邻的数之间有一个空格。【输出】输出文件包括两行：第一行是一个整数，为n个区域通电后的最大价值；第二行是一个整数，为得到最大价值的架设电线的不同方法数（如果架设的终点是同一个地方并有多种方法且其中有不止一种方法可以得到最大价值，则算多种方法。如下图）。（友情提示：请复制到记事本中查看）地图：1 231 1000 21 11n=3，则有两种方法可以得到最大值：一种是发电站先往上扩展再往右扩展；第二种是先往右再往上，两种方法的终点都是最右上角价值为3的地区，但这是两种不同的方法，所以这样的地图应该输出1005和2。【样例输入】|3 3 5|8 3 8|5 1000 5|6 3 6|【样例输出】|1026|1|【数据范围】对于20%的数据，1=x,y=50;1=n=5。对于50%的数据，1=x,y=100;1=n=10。对于100%的数据，1=x,y=500;1=n=20。4.精卫填海(sea.pas/c/cpp)【版权说明】本题为改编题。【问题描述】发鸠之山，其上多柘木。有鸟焉，其状如乌，文首，白喙，赤足，名曰精卫，其名自詨。是炎帝之少女，名曰女娃。女娃游于东海，溺而不返，故为精卫。常衔西山之木石，以堙于东海。山海经精卫终于快把东海填平了！只剩下了最后的一小片区域了。同时，西山上的木石也已经不多了。精卫能把东海填平吗？事实上，东海未填平的区域还需要体积为v的木石才可以填平，而西山上的木石还剩下n块，每块的体积和把它衔到东海需要的体力分别为k和m。精卫已经填海填了这么长时间了，她也很累了，她还剩下的体力为c。【输入】输入文件的第一行是三个整数：v、n、c。从第二行到第n+1行分别为每块木石的体积和把它衔到东海需要的体力。【输出】输出文件只有一行，如果精卫能把东海填平，则输出她把东海填