冲刺NOIP2011长乐一中day2

福建省长乐一中

冲刺 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、<Time> + 表示应用程序在第 Time 秒向 Windows 发送一条申请内存的消息; 2、<Time> . <Label> 表示应用程序在第 Time 秒向 Windows 发送一条访问第 Label 块 内存的消息。 其中,<Time>和<Label>会在真正的消息中被替换为相应数字。 程序开始时,所有内存块均处于空闲状态。 对于申请内存的消息,Windows 系统会将当前空闲内存块中编号最小的那一块分配给相 应的应用程序,并且相应内存块转变为被占用状态。对于访问内存的消息,若当前内存块处 于被占用状态,则 Windows 系统会反馈一个“+”表示该内存块可以被访问,否则反馈一个 “-”表示程序无法访问该内存块。对于任何被占用的内存块,若在 600 秒内无任何操作, 则该内存块会被系统释放掉,重新变为空闲状态。 【输入格式】 输入文件包含若干行,每行描述一条消息,消息共有两种: 1、<Time> + 2、<Time> . <Label> 消息含义见问题描述。+前有一个空格,.的前后都有一个空格,其他地方无多于空格。 保证 Time 按照非递减顺序出现,对于在同一时刻发出的消息,按照输入顺序处理。 【输出格式】 对于每条申请内存的消息,输出 Windows 分配给该应用程序的内存块编号。 对于每条访问内存的消息,输出“+”或“-”表示该内存块是否可以被成功访问。

第 1 页 共 4 页

福建省长乐一中
【输入输出样例】 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 -

冲刺 Noip2011

【样例说明】 对于前 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 页

福建省长乐一中
【输入样例】 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

冲刺 Noip2011

第 4 页 共 4 页


相关文档

冲刺NOIP2011长乐一中day2解题报告
冲刺NOIP2011长乐一中day1
冲刺NOIP2011长乐一中day1解题报告
noip2011模拟day2
NOIP2011 提高组 Day2
NOIP2011 提高组 试题 Day2
杭州学军中学NOIP2011模拟赛DAY2-2011-10-5
NOIP2011复赛模拟题Day2
noip2011提高组day2题解转载
NOIP2011提高组解题报告day2
电脑版