浙江省镇海中学训练习题..docx

《浙江省镇海中学训练习题..docx》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1205:[HNOI2005]星际贸易TimeLimit: 10Sec  MemoryLimit: 162MBSubmit: 118  Solved: 52[Submit][Status][Discuss]DescriptionInputOutput如果可以找到这样的方案，那么输出包含两个整数X和Y。X表示贸易额，Y表示净利润并且两个数字之间用一个空格隔开。如果不能完成这次星际贸易，那么输出“PoorCoke!”（不包括引号）。SampleInput63104121111222112391114011150111611SampleOu

2、tput62HINTSourceDP优化1222:[HNOI2001]产品加工TimeLimit: 15Sec  MemoryLimit: 162MBSubmit: 337  Solved: 191[Submit][Status][Discuss]Description某加工厂有A、B两台机器，来加工的产品可以由其中任何一台机器完成，或者两台机器共同完成。由于受到机器性能和产品特性的限制，不同的机器加工同一产品所需的时间会不同，若同时由两台机器共同进行加工，所完成任务又会不同。某一天，加工厂接到n个产品加工的任务，每个任务的工作量不尽

3、一样。你的任务就是：已知每个任务在A机器上加工所需的时间t1,B机器上加工所需的时间t2及由两台机器共同加工所需的时间t3，请你合理安排任务的调度顺序，使完成所有n个任务的总时间最少。Input输入共n+1行第1行为n。n是任务总数（1≤n≤6000）第i+1行为3个[0，5]之间的非负整数t1,t2,t3，分别表示第i个任务在A机器上加工、B机器上加工、两台机器共同加工所需要的时间。如果所给的时间t1或t2为0表示任务不能在该台机器上加工，如果t3为0表示任务不能同时由两台机器加工。Output最少完成时间SampleInput52

4、10050241003211SampleOutput9HINTSourceDp1217:[HNOI2003]消防局的设立TimeLimit: 10Sec  MemoryLimit: 162MBSubmit: 336  Solved: 189[Submit][Status][Discuss]Description2020年，人类在火星上建立了一个庞大的基地群，总共有n个基地。起初为了节约材料，人类只修建了n-1条道路来连接这些基地，并且每两个基地都能够通过道路到达，所以所有的基地形成了一个巨大的树状结构。如果基地A到基地B至少要经过d条

5、道路的话，我们称基地A到基地B的距离为d。由于火星上非常干燥，经常引发火灾，人类决定在火星上修建若干个消防局。消防局只能修建在基地里，每个消防局有能力扑灭与它距离不超过2的基地的火灾。你的任务是计算至少要修建多少个消防局才能够确保火星上所有的基地在发生火灾时，消防队有能力及时扑灭火灾。Input输入文件的第一行为n，表示火星上基地的数目。接下来的n-1行每行有一个正整数，其中文件第i行的正整数为a[i]，表示从编号为i的基地到编号为a[i]的基地之间有一条道路，为了更加简洁的描述树状结构的基地群，有a[i]Output输出文件仅有一个

6、正整数，表示至少要设立多少个消防局才有能力及时扑灭任何基地发生的火灾。SampleInput612345SampleOutput2HINTSource贪心1227:[SDOI2009]虔诚的墓主人TimeLimit: 5Sec  MemoryLimit: 259MBSubmit: 674  Solved: 301[Submit][Status][Discuss]Description小W是一片新造公墓的管理人。公墓可以看成一块N×M的矩形，矩形的每个格点，要么种着一棵常青树，要么是一块还没有归属的墓地。当地的居民都是非常虔诚的基督徒，

7、他们愿意提前为自己找一块合适墓地。为了体现自己对主的真诚，他们希望自己的墓地拥有着较高的虔诚度。一块墓地的虔诚度是指以这块墓地为中心的十字架的数目。一个十字架可以看成中间是墓地，墓地的正上、正下、正左、正右都有恰好k棵常青树。小W希望知道他所管理的这片公墓中所有墓地的虔诚度总和是多少Input第一行包含两个用空格分隔的正整数N和M，表示公墓的宽和长，因此这个矩形公墓共有(N+1)×(M+1)个格点，左下角的坐标为(0,0)，右上角的坐标为(N,M)。第二行包含一个正整数W，表示公墓中常青树的个数。第三行起共W行，每行包含两个用空格分隔

8、的非负整数xi和yi，表示一棵常青树的坐标。输入保证没有两棵常青树拥有相同的坐标。最后一行包含一个正整数k，意义如题目所示。Output包含一个非负整数，表示这片公墓中所有墓地的虔诚度总和。为了方便起见，答案对2,147