文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 高等教育 > 理学 > 冲刺NOIP2011长乐一中day2解题报告
侵权投诉

冲刺NOIP2011长乐一中day2解题报告

解题报告

题1、内存管理

题目大意:

对于每次申请,使用最小的内存块,对于每次访问,给出是否允许。 朴素算法:

每次扫描一遍,找出没被占用的内存块,一找到就BREAK。

理论时间复杂度O(nm) n=30000;m为操作次数。

(实际上要快的多)

完美算法:

算法1:优化朴素;

通过仔细分析不难发现,由于释放要等待的时间只有总时间的1/144之一,而指令数又是有限的。所以如果要让我们的朴素超时,出数据的人会出在短时间内有多个申请的数据。既然在短时间内有多个申请,那时间必然会有重复,这样的话。我们只需判断现在的时间与上一次申请的时间做比较,如果一样,我们就沿着上次的答案接着寻找,避免多次无用功的出现。这样就可以在规定时间内出正解了。

Ps:指令是有限的,想让朴素找2w次必然要先使用2w条指令,而这2w条指令又得在600s内发出或者用2w条访问维护,想想如果用访问维护前面被占有,那得在这上面浪费多少指令啊,最后还能卡朴素吗?所以只能在短时间内多个申请,这样之前的优化就非常合适了。

算法2:用堆来实现快速查找

用小根堆记录tr_n哪些点可以用(编号做为关键字),这样可以在logn的时间内查找出使用哪个内存块。

再拿一个小根堆_tr_t记录每个点被释放的时间的次序,自然tr_t中的结点要知道自己是对应哪个内存块。并记录实际的内存块的具体释放时间,以及内存块对应的树中的结点编号。

具体操作为:

每次读入,查看当前时间是否有内存块可以释放,有则释放。

如果读入为申请内存块,使用堆tr_n中第一个就好,然后将它放入tr_t中,释放时间为当前时间+600s,调整堆tr_t和堆tr_n。

如果是访问则比较访问时间与释放时间大小,如果释放时间大于访问时间则未被释放,释放时间调整为访问时间+600s,调整tr_t中的元素。如果释放时间小于或等于访问时间则禁止访问。

这样时间复杂度就降为O(Mlogn) M为操作次数 ,n为内存块数量就是30000。

题2、买礼物

这题很明显是二维费用背包,但是有诸多限制,需要一个一个解决。 首先解决可以免费送一个礼物的问题。

有一个很暴力的方法就是枚举送哪个礼物,再做背包,但这样时间复杂度是O(n²v1v2),

第1页

你可能喜欢

热门文档

相关文档

  • 冲刺NOIP2011长乐一中day2

    福建省长乐一中 冲刺 Noip2011 冲刺 NOIP2011 长乐一中 day2 题目名称 存盘文件名 输入文件名 输出文件名 时限 内存限制 内存管理 ram ram.in ram.out 1s 128...

  • 冲刺NOIP2011长乐一中day1

    NOIP2011提高组试题-day1 6页 2财富值 NOIP2011提高组解题报告da... 15页... 福建省长乐一中 冲刺 Noip2011 冲刺 NOIP2011 长乐一中 day1 题目名称 存盘...

  • NOIP2011提高组解题报告day2

    NOIP2011提高组解题报告day2_理学_高等教育_教育专区。noip历届复赛试题及解析... Noip 2013 提高组 Day2 ... 14页 免费 冲刺NOIP2011长乐一中da... 暂无...

  • NOIP2011复赛模拟题Day2

    noip2011模拟day2 4页 1下载券 NOIP2011提高组解题报告... 9页 2下载券 NOIP2011 提高组 Day2 4页 免费 冲刺NOIP2011长乐一中da... 暂无评价 4页 免费 ...

  • Noip 2013 提高组 Day2 解题报告

    Noip 2013 提高组 Day2 解题报告_学科竞赛_高中教育_教育专区。Noip 2013 提高组 Day2 解题报告Noip 2013 Day2 解题报告 --By GreenCloudS 第一题:积木大赛 ...

  • noip2011第二题选择客栈解题报告

    noip2011第二题选择客栈解题报告_人文社科_专业资料。 今日推荐 ... 2页 免费 冲刺NOIP2011长乐一中da... 1页 免费喜欢此文档的还喜欢...

  • NOIP2011提高组复赛DAY1解题报告

    NOIP2011提高组复赛DAY1解题报告_初一数学_数学_初中教育_教育专区。NOIP2011... 冲刺NOIP2011长乐一中da... 1页 免费 NOIp2011提高组复赛题解 4页 2下载券...

  • NOIP2011普及组解题报告

    NOIP2011普及组解题报告_学科竞赛_初中教育_教育专区。NOIP2011 普及组解题报告一、数字反转 没得满分只能说明一个问题,你的程序写的太少了。 program reverse; ...

  • 冲刺NOIP2011模拟试题(二)

    冲刺noip2011模拟试题冲刺noip2011模拟试题隐藏>> 模拟试题( 冲刺 NOIP 2011 模拟试题(二) 题目 源程序名 输入文件 输出文件 时间限制 空间限制 区间运算 拯救小...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email