福建省长乐一中 冲刺Noip2011
冲刺NOIP2011长乐一中day2
题目名称 存盘文件名 输入文件名 输出文件名 时限 内存限制 内存管理 ram ram.in ram.out 1s 128M 买礼物 gift gift.in gift.out 1s 128M 防贼道路 road road.in road.out 1s 128M 【注意事项】： 请自行完成题目，切勿讨论。
题1 内存管理
【问题描述】
Windows的内存管理系统是十分复杂的，我们要求你编写一个程序，来模拟内存管理操作。
计算机的内存被分割成30000个相同大小的连续区域，每个区域被称作一个内存块（Block），这些内存块被依次编号为1,2,3,...,29998,29999,30000。内存管理的基本单位是块，即某个应用程序申请或访问的内存必须是块的整数倍。
当某应用程序申请或访问内存时，该应用程序会向Windows发送一条消息(Message)： 1、
2、
其中，
对于申请内存的消息，Windows系统会将当前空闲内存块中编号最小的那一块分配给相应的应用程序，并且相应内存块转变为被占用状态。对于访问内存的消息，若当前内存块处于被占用状态，则Windows系统会反馈一个“+”表示该内存块可以被访问，否则反馈一个“-”表示程序无法访问该内存块。对于任何被占用的内存块，若在600秒内无任何操作，则该内存块会被系统释放掉，重新变为空闲状态。
【输入格式】
输入文件包含若干行，每行描述一条消息，消息共有两种： 1、
2、
消息含义见问题描述。+前有一个空格,.的前后都有一个空格,其他地方无多于空格。 保证Time按照非递减顺序出现，对于在同一时刻发出的消息，按照输入顺序处理。
【输出格式】
对于每条申请内存的消息，输出Windows分配给该应用程序的内存块编号。
对于每条访问内存的消息，输出“+”或“-”表示该内存块是否可以被成功访问。
第 1 页 共 4 页
福建省长乐一中 冲刺Noip2011
【输入输出样例】 ram.in 1 + 1 + 1 + 2 . 2 2 . 3 3 . 30000 601 . 1 601 . 2 602 . 3 602 + 602 + 1202 . 2 ram.out 1 2 3 + + - - + - 1 3 - 【样例说明】 对于前3条申请内存的消息，Windows系统依次将1、2、3号内存块分配给应用程序，若在接下来600秒内没有对这些内存块进行任何操作，这些内存块将在第601秒时被系统释放掉；
对于接下来3条访问内存的消息，2号和3号内存块在占用，返回“+”，同时它们的释放时间被推迟到第602秒。30000号内存块未被占用，于是返回“-”；
再接下来3条访问内存的消息，由于在第601秒时1号内存块被释放，在第602秒时2号和3号内存块被释放，所以依次返回“-”、“+”和“-”，同时2号内存块的释放时间被推迟到第1201秒；
下面2条申请内存的消息，由于目前1号和3号是空闲内存块，2号在被占用，所以Windows分别将1号和3号内存块分配给应用程序，并且1号和3号内存块的释放时间为第1202秒。
最后一条访问内存的消息，由于2号内存块已在第1201秒时被释放掉，因此返回“-”。
【数据规模和约定】
对于20%的数据，消息数不大于500；
对于100%的数据，消息数不大于100000，每次申请内存操作时，至少会有一个内存块处于空闲状态，0≤Time<86400，保证数据合法。
题2 买礼物
【问题描述】
圣诞节要到了，WZK想要为女朋友购买一些礼物。商店里总共有n个礼物，编号分别为1到n。假设Pi、Vi分别表示第i件物品的价格和WZK女朋友的喜爱程度。有一些礼品是有特殊含义的，WZK必须给他的女朋友买。
WZK现在手上有两张信用卡，而且这两张信用卡只能分开使用。即假设当第一张卡中有3元，第二张卡中有2元时，WZK不能用这两张卡购买5元的礼物。
因为WZK是神犇，又这么痴情，所以商店老板准备免费赠送WZK一个礼物。现在，WZK经过分析后想知道，如何购买礼物才能使他女朋友对礼物的喜爱值之和最大。
第 2 页 共 4 页
福建省长乐一中 冲刺Noip2011
【输入格式】
第一行包含三个整数，V1、V2和n（1≤V1≤500,1≤V2≤50,1≤n≤300），分别表示两张信用卡的额度和礼物的个数。
接下来n行，每行三个整数，Pi、Vi、Si（1≤Pi，Vi≤1000）分别表示礼物的价格、喜爱程度以及是否必须购买，Si=1表示该礼物必须购买，Si=0表示不一定要购买。 【输出格式】
一行一个整数，表示WZK女朋友对礼物的喜爱程度。
若WZK不能将所有必须购买的礼物购买到，那么就输出-1。 【输入样例1】 3 2 4 3 10 1 2 10 0 5 100 0 5 80 0 【输出样例1】 120
【输入样例2】 3 2 4 3 10 1 2 10 0 5 100 0 5 80 1 【输出样例2】 100
【数据规模和约定】
对于20%的数据，1≤n≤50；
对于100%的数据，1≤V1≤500,1≤V2≤50,1≤n≤300。
题3 防贼道路
【问题描述】
A国有N个城市，M条双向道路(所有城市都是连通的)，每条道路都有相应的价值，由于A国盗贼出没比较频繁，所以国王决定只保留一些道路，使得任意两座城市只有一条简单路径连通。
假设T是其中一种合法的方案，那么P(T)代表的是合法方案中所有道路价值的最大公约数。国王想借此机会了解一下你的数学能力，所以你需要在一秒内回答他所有P(T)的最小公倍数的大小。 【输入文件】
第一行N M，表示城市数量，道路数量。
接下来M行s t d 表示城市s与城市t间存在一条价值为d的道路，保证s不等于t。 【输出文件】
所求的最小公倍数ans
第 3 页 共 4 页
福建省长乐一中 冲刺Noip2011
【输入样例】 3 3 1 2 2 2 3 3 1 3 6 【输出样例】 6
【样例解释】
有3个合法的方案，P(T)分别为1,2,3,它们的最小公倍数为6 【数据规模】 20%：M=N-1 另外20%：M=N
另外30%：所有道路的价值都是2 的整数次幂
100%：N<=1000，M<=100000，Di<=2^15-1，ans<=2^64-1
第 4 页 共 4 页