浙江省某中学训练习题.pdf

1205:HNOI2005星际贸易Time Limit:10 Sec Memory Limit:162 MBSubmit:118 Solved:52SubmitStatusDiscussDescriptionC o k e是一个精明的小商人.这次他想大胆地做一次星际贸易.于是他选定了银河贸易交通局所给定的一条贸易路线，从地球出发，依次经过0，,口 为.贸 易 路 线 在 力 结束（C o k e最 后 要 在 切 上 观 光 旅 游 银河系中各个星球实行计划经济.在一个星球上出售商品，必须获得那个星球的讦可证.C o k e手 中 的 许 可 证 允 讦 他 在 上 出 售 指 定 配 额 鳍4（1 44 41 0吨的商品（而且既不能多也不能少，当 然 他 可 以 不 在 上 出 售 任 何 商 品），出售后能够获得用（0 M 4 5 0 0 0 0）的收入.由 于C o k e的私人飞船载重有限，这个精明的小商人不得不好好计划一下他应该向哪些星球出售商品./飞船采用反物质推进系统行驶，需要反物质燃料.反物质燃料不是用来维持平常飞行的（宇宙间没有阻力），而是用于飞船从星球出发时加速以及飞船到达星球时减速所需的消耗.每次加速和减速各消耗一个单位的反物质燃料.，另外，作如此长距离的飞行，飞船显然要在中途停靠并在某些星球上补充反物质燃料以及对飞船定期进行一些维护（维护只能在星球上进行）.由于各星球之间科技发展水平不等，在各个星球上反物质燃料的售价以及维护飞船的费用是不同的.。

此外，银河贸易交通局正在举办小商人贸易竟寒，对于贸易额（即总贸易收入）得到冠军的商人有丰厚的奖赏，因 此C o k e决定不惜血本，要使自己的更易额达到最大.当然，在贸易额最大的同时,作为一个商人,他还是希望净利润尽可能大（净利润=贸易额-燃料费用-维护费用）一假设从地球出发时飞船刚刚维护过并装满了燃料，并且飞船每次停靠一个星球出售商品或补充反物质燃料或在终点站观光旅游时就会在那里做一次维护.C o k e希望你给他制定一个方Input第1行 为4个 正 整 数 业 凡4.曾（1 W H 4 2 0 0 0）表 示C o k e这次要行经的星球数:，M（l V N V 2 0 0 0）表 示 飞 船 最 大 的 载 重 量2?（0 /?1 09）表示飞船最多能携带的燃料数.4（1 W4工19）表示飞船不做维护所能飞行的最大距离.文件的第2曾+1行是对每个星球的描述.其中第？+1行 有5个非负整数4,用工”月，居.4（1 =4=1 0表示从地球依次经过Star,Star2，,S 环_1最后到达Star,的距离咛（0 W4X1 0 0 0）为星球S Z w,上一个单位反物质的价格，若 月 为0,则说明这个星球还没有制造反物质的技术.居（0 4月4 1 0 0 0 0）表示飞船在我。

6上做维护所需要的费用.假设输入数据满足：对于i /,一定有&Lj t并使得只有一种获得最大贸易额的方法.Output如果可以找到这样的方案，那么输出包含两个整数X 和 丫X 表示贸易额，Y 表示净利润并且两个数字之间用个空格隔开如果不能完成这次星际贸易，那么输出“PoorCoke!”（不包括引号）Sample Input6 3 10 412 1 1 11 2 2 2 11 2 3 9 11 1 4 0 11 1 5 0 11 1 6 11Sample Output6 2HINTSourceDP优化1222:HNOI2001产品加工Time Limit:15 Sec Memory Limit:162 MBSubmit:337 Solved:191SubmitStatusDiscussDescription某加工厂有A、B 两台机器，来加工的产品可以由其中任何一台机器完成，或者两台机器共同完成由于受到机器性能和产品特性的限制，不同的机器加工同一产品所需的时间会不同,若同时由两台机器共同进行加工，所完成任务又会不同某一天，加工厂接到n 个产品加工的任务，每个任务的工作量不尽一样你的任务就是：已知每个任务在A 机器上加工所需的时间t1,B 机器上加工所需的时间t2 及由两台机器共同加工所需的时间t3,请你合理安排任务的调度顺序，使完成所有n 个任务的总时间最少。

Input输入共n+1行 第 1 行 为 no n 是任务总数(1n6000)第 i+1行为3 个 0,5 之间的非负整数t1,t2,t3,分别表示第i 个任务在A 机器上加工、B 机器上加工、两台机器共同加工所需要的时间如果所给的时间t1 或 t2 为表示任务不能在该台机器上加工，如果t3 为 0表示任务不能同时由两台机器加工Output最少完成时间Sample Input52 100 5 02 4 10 0 32 11Sample Output9HINTSourceDp1217:HNOI2003消防局的设立Time Limit:10 Sec Memory Limit:162 MBSubmit:336 Solved:189SubmitStatusDiscussDescription2020年，人类在火星上建立了一个庞大的基地群，总共有n 个基地起初为了节约材料，人类只修建了 n-1条道路来连接这些基地，并且每两个基地都能够通过道路到达，所以所有的基地形成了一个巨大的树状结构如果基地A 到基地B 至少要经过d 条道路的话，我们称基地A 到基地B 的距离为d由于火星上非常干燥，经常引发火灾，人类决定在火星上修建若干个消防局。

消防局只能修建在基地里，每个消防局有能力扑火与它距离不超过2的基地的火灾你的任务是计算至少要修建多少个消防局才能够确保火星上所有的基地在发生火灾时，消防队有能力及时扑火火灾Input输入文件的第一行为n,表示火星上基地的数目接下来的n-1行每行有一个正整数，其中文件第i 行的正整数为a i,表示从编号为i 的基地到编号为ai的基地之间有一条道路，为了更加简洁的描述树状结构的基地群，有 aiOutput输出文件仅有个正整数，表示至少要设立多少个消防局才有能力及时扑灭任何基地发生的火灾Sample Input612345Sample Output2HINTSource贪心1227:SDOI2009虔诚的墓主人Time Limit:5 Sec Memory Limit:259 MBSubmit:674 Solved:301SubmitStatusDiscussDescription小 W 是一片新造公墓的管理人公墓可以看成一块NXM 的矩形，矩形的每个格点，要么种着一棵常青树，要么是一块还没有归属的墓地当地的居民都是非常虔诚的基督徒，他们愿意提前为自己找一块合适墓地为了体现自己对主的真诚，他们希望自己的墓地拥有着较高的虔诚度。

一块墓地的虔诚度是指以这块墓地为中心的卜字架的数目个卜字架可以看成中间是墓地，墓地的正上、正下、正左、正右都有恰好k 棵常青树小 W 希望知道他所管理的这片公墓中所有墓地的虔诚度总和是多少Input第一行包含两个用空格分隔的正整数N 和 M,表示公墓的宽和长，因此这个矩形公墓共有(N+1)x(M+1)个格点，左下角的坐标为(0,0),右上角的坐标为(N,M)第二行包含一个正整数W,表示公墓中常青树的个数第三行起共W 行，每行包含两个用空格分隔的非负整数 x i和 y i,表示一棵常青树的坐标输入保证没有两棵常青树拥有相同的坐标最后一行包含一个正整数k,意义如题目所示Output包含一个非负整数，表示这片公墓中所有墓地的虔诚度总和为了方便起见，答案对2,147,483,648 取模Sample Input5 6130 20 31 21 32 02 12 42 52 63 23 34 35 22Sample Output6HINT图中，以墓地(2,2)和(2,3)为中心的十字架各有3 个，即它们的虔诚度均为3其他墓地的虔诚度为0对于30%的数据，满 足 1 W N,M W 1,000对于60%的数据，满 足 1 W N,M V1,000,000o 对于 100%的数据，满足 1&N,MW 1,000,000,000,0 xiN,0yiM,1W 100,000,1 k 1 0 o 存在50%的数据，满 足 lw k 2。

存在25%的数据，满 足 1W 10000cSource线段树1226:SDOI2009学校食堂 DiningTime Limit:10 Sec Memory Limit:259 MBSubmit:451 Solved:269SubmitStatusDiscussDescription小 F 的学校在城市的个偏僻角落，所有学生都只好在学校吃饭学校有个食堂，虽然简陋，但食堂大厨总能做出让同学们满意的菜肴当然，不同的人口味也不一定相同，但每个人的口味都可以用一个非负整数表示由于人手不够，食堂每次只能为 个人做菜做每道菜所需的时间是和前一道菜有关的，若前一道菜的对应的口味是a,这一道为b,则做这道菜所需的时间为(aorb)-(a and b),而做第一 道菜是不需要计算时间的其中，o r 和a n d 表示整数逐位或运算及逐位与运算，C 语言中对应的运算符为T 和 学 生 数 目 相 对于这个学校还是比较多的，吃饭做菜往往就会花去不少时间因此，学校食堂偶尔会不按照大家的排队顺序做菜，以缩短总的进餐时间虽然同学们能够理解学校食堂的这种做法，不过每个同学还是有定容忍度的也就是说，队伍中的第i 个同学，最多允许紧跟他身后的B i个人先拿到饭菜。

一旦在此之后的任意同学比当前同学先拿到饭，当前同学将会十分愤怒因此，食堂做菜还得照顾到同学们的情绪现在，小F想知道在满足所有人的容忍度这一前提下，自己的学校食堂做完这些菜最少需要多少时间Input第一行包含一个正整数C,表示测试点的数据组数每组数据的第一行包含一个正整数N,表示同学数每组数据的第二行起共N行，每行包含两个用空格分隔的非负整数T i和Bi,表示按队伍顺序从前往后的每个同学所需的菜的口味和这个同学的忍受度每组数据之间没有多余空行Output包含C行，每行一个整数，表示对应数据中食堂完成所有菜所需的最少时间Sample Input255 24 112 03 32 225 04 0Sample Output161HINT对于第一组数据：同学1 允许同学2 或同学3 在他之前拿到菜；同学2 允许同学3 在他之前拿到菜；同学3 比较小气，他必须比他后面的同学先拿菜 一种最优的方案是按同学3、同学2、同学1、同学4、同学5 做菜，每道菜所需的时间分别是0、8、1、6 及 1数据规模和约定】对于30%的数据，满 足 1 4 N 4 20对 于 100%的数据，满 足 1 4 N 1,000,0 T i 1,000,0 B i 7,1 C5o 存在 30%的数据，满足 04 Bi 4 1。

存在 65%的数据，满足0 4 Bi 4 5存在45%的数据，满足0 V T iw l3 0SourceDp1228:SDOI2009E&DTime Limit:10 Sec Memory Limit:162 MBSubmit:420 Solved:224SubmitStatusDiscussDescription小 E 与小W 进行一项名为“E&D”游戏游戏的规则如下:桌子上有2 n 堆石子，编号为1.2n其中，为了方便起见，我们将第2k-1堆与第2 k 堆（is k v n）视为同组第 i 堆的石子个数用一个正整数S i表示一次分割操作指的是，从桌子上任取一堆石子，将其移走然后分割它同一一组的另一堆石子，从中取出若干个石子放在被移走的位置，组成新的一堆操作完成后，所有堆的石子数必须保证大于0显然，被分割的一堆的石子数至少要为2两个人轮流进行分割操作如果轮到某人进行操作时，所有堆的石子数均为1,则此时没有石子可以操作，判此人输掉比赛。