冲刺NOIP2011长乐一中day2

1、福建省长乐一中冲刺 Noip2011冲刺NOIP2011长乐一中day2题目名称内存管理买礼物防贼道路存盘文件名ramgiftroad输入文件名ram.ingift.inroad.in输出文件名ram.outgift.outroad.out时限1s1s1s内存限制128M128M128M【注意事项】请自行完成题目，切勿讨论。题1内存管理【问题描述】Windows的内存管理系统是十分复杂的，我们要求你编写一个程序，来模拟内存管理操 作。计算机的内存被分割成30000个相同大小的连续区域，每个区域被称作一个内存块(Block),这些内存块被依次编号为1,2,3，,29998,29999,30000

2、。内存管理的基本单位是块，即某个应用程序申请或访问的内存必须是块的整数倍。当某应用程序申请或访问内存时，该应用程序会向Windows发送一条消息(Message):1 、<Time> +表示应用程序在第 Time秒向Windows发送一条申请内存的消息；2 、<Time> . <Label>表示应用程序在第 Time秒向 Windows发送一条访问第 Label块内存的消息。其中，<Time>和<Label>会在真正的消息中被替换为相应数字。程序开始时，所有内存块均处于空闲状态。对于申请内存的消息，Windows系统会将当前空闲内存块

3、中编号最小的那一块分配给相应的应用程序，并且相应内存块转变为被占用状态。对于访问内存的消息，若当前内存块处于被占用状态，则 Windows系统会反馈一个“ +”表示该内存块可以被访问，否则反馈一个 “-”表示程序无法访问该内存块。对于任何被占用的内存块，若在 600秒内无任何操作， 则该内存块会被系统释放掉，重新变为空闲状态。【输入格式】输入文件包含若干行，每行描述一条消息，消息共有两种：1 、<Time> +2 、<Time> . <Label>消息含义见问题描述。+前有一个空格,.的前后都有一个空格，其他地方无多于空格。保证Time按照非递减顺序出现，对

4、于在同一时刻发出的消息，按照输入顺序处理。【输出格式】对于每条申请内存的消息，输出Windows分配给该应用程序的内存块编号。对于每条访问内存的消息，输出“+”或“-”表示该内存块是否可以被成功访问。【输入输出样例】ram.inram.out1 +11 +21 +32.2+2.3+3.30000-601 . 1-601 . 2+602.3-602 +1602 +31202.2-【样例说明】对于前3条申请内存的消息，Windows系统依次将1、2、3号内存块分配给应用程序，若在接下来600秒内没有对这些内存块进行任何操作，这些内存块将在第 601秒时被系统释放掉；对于接下来3条访问内存的消息，2

5、号和3号内存块在占用，返回“ +”，同时它们的释 放时间被推迟到第 602秒。30000号内存块未被占用，于是返回“-”；再接下来3条访问内存的消息，由于在第601秒时1号内存块被释放，在第 602秒时2号和3号内存块被释放，所以依次返回“-”、“+”和“-”，同时2号内存块的释放时间被推迟到第1201秒；下面2条申请内存的消息，由于目前 1号和3号是空闲内存块，2号在被占用，所以 Windows分别将1号和3号内存块分配给应用程序， 并且1号和3号内存块的释放时间为第 1202 秒。最后一条访问内存的消息，由于2号内存块已在第1201秒时被释放掉，因此返回“-”。【数据规模和约定】对于20%

6、勺数据，消息数不大于 500;对于100%勺数据，消息数不大于100000,每次申请内存操作时，至少会有一个内存块处于空闲状态，0WTime<86400,保证数据合法。题2买礼物【问题描述】圣诞节要到了， WZ圈要为女朋友购买一些礼物。商店里总共有n个礼物，编号分别为1到no假设Pi、Vi分别表示第i件物品的价格和 WZ敏朋友的喜爱程度。 有一些礼品是有 特殊含义的，WZK必须给他的女朋友买。WZK现在手上有两张信用卡，而且这两张信用卡只能分开使用。即假设当第一张卡中有3元，第二张卡中有 2元时，WZK能用这两弓卡购买 5元的礼物。因为WZa神奇，又这么痴情，所以商店老板准备免费赠送WZ

7、K-个礼物。现在， WZK经过分析后想知道，如何购买礼物才能使他女朋友对礼物的喜爱值之和最大。【输入格式】第一行包含三个整数，VI、V2和n (KV1< 500,1 < V2!< 50,1 w nW 300),分别表示两张信用卡的额度和礼物的个数。接下来n行，每行三个整数，Pi、Vi、Si (iwpi, Vi < 1000)分别表示礼物的价格、喜爱程度以及是否必须购买，Si=1表示该礼物必须购买，Si=0表示不一定要购买。【输出格式】一行一个整数，表示 WZ故朋友对礼物的喜爱程度。若WZK能将所有必须购买的礼物购买到，那么就输出 -1。【输入样例1】3 2 43 10

8、12 10 05 100 05 80 0【输出样例1】120【输入样例2】3 2 43 10 12 10 05 100 05 80 1【输出样例2】100【数据规模和约定】对于20%勺数据，1WnW50；对于 100%勺数据，1WV1W 500,1 WV2W 50,1 w nW 300。题3防贼道路【问题描述】A国有N城市，M条双向道路(所有城市都是连通的)，每条道路都有相应的价值，由于A国盗贼出没比较频繁，所以国王决定只保留一些道路，使得任意两座城市只有一条简单路径 连通。假设,其中一种合法白方案，那么 P(T)代表的是合法方案中所有道路价值的最大公约 数。国王想借此机会了解一下你的数学能力，所以你需要在一秒内回答他所有P(T)的最小公倍数的大小。【输入文件】第一行N M,表示城市数量，道路数量。接下来Mts t d 表示城市s与城市t间存在一条价值为d的道路，保证s不等于t。【输出文件】所求的最小公倍数ans【输入样例】3 31 2 22 3 31 3 6【输出样例】6【样例解释】有3个合法的方案，P(T)