注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

NOIP2010  

2010-11-20 20:33:53|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
今天刚考完NOIP2010,赶紧和大家分享一下吧。
先是题目(我按照记忆写的题目大意):
1.translate
一个机器有M单位的内存。它要翻译一段N个单词的文本,方法是用字典中的解释依次替换原文本的单词。
初始时内存中没有数据。每次要翻译一个单词,如果这个单词在内存中,就直接输出解释;否则,要
从外存中查找这个单词的解释,之后把它加入到内存中,消耗一个单位的内存。如果内存的空间已满,
就把最早进入内存的那个单词删掉,腾出空间。
给这段文本(方便起见,用数字代替单词),求一共要查询多少次外存。
N≤1000,M≤100
2.tortoise
一只乌龟在数轴上跳跃。它从0开始,要跳到N-1。每个整数点上有一个分数,如果它在那个点上待过,就
可以获得相应的分数。不过,这只乌龟需要用“跳跃卡”来完成跳跃,每张跳跃卡上有一个数字(1或2或3或4),
使用一张跳跃卡可以让乌龟向前跳跃卡上指定的距离。每张卡只能用一次,并且数据保证所有卡片上的数字之和为N-1
问乌龟最多能得多少分。
N≤350,卡片数≤120,每种卡片的数量≤40
3.prison
有一些囚犯,他们之间有一些怨恨值。一个城市有两个监狱,如果一对有怨恨值的囚犯关押在一起,会产生
等于怨恨值的不和谐值。求最大不和谐值的最小值。
囚犯数≤20000,有怨恨值的囚犯不超过100000对
4.flow
有一个N*M的网格,每个格子有一个高度,第一行是湿润格,最后一行是干旱格。
蓄水池只能建在湿润格上。一个格子有水当且仅当它是蓄水池或它相邻(4相邻)的比它高度低的格子有水。
要求所有的干旱格子都有水。问是否可以满足要求,如果可以输出最少蓄水池个数,否则输出最少有多少个
干旱格没有水。

说一下我的算法吧:
第一题:裸模拟,不用任何数据结构(数组除外)。
其实这题有线性算法,但数据规模太小,多暴力都能过。
一个思考题:如果内存满的时候可以任意指定清空哪个单位的单词,那么最少外存查询次数该怎么算呢?
第二题:dp
注意到所有的卡片都要用。设f[i][j][k][l]表示走到第i个格子,用了j个4,k个3,l个2的情况下的最大收益。
注意要滚动数组
第三题:各种算法
第一种算法:二分答案,之后看有没有奇环。可以用并查集或dfs。
我用的是并查集,结果。。。被第一组数据干掉了:
2 1 1 2 28315,我二分答案的时候用的是最小怨恨值-1作为不可能下界,但是忘记了图可二分这种情况...
鄙视一下自己。
另一种算法:从小到大依次填边,用并查集动态判是否有奇环。
还有一种:跑一个最大生成树(用kruscal,图不连通就得到一个最大生成森林),之后按这个最大生成树来计算。不过
我不清楚这个算法的细节和正确性,但听起来好像是对的。
第四题:
朴素(时间复杂度三次方):我们可以把干旱格子划成若干段,在每个段里只考虑来自一个蓄水池的水。
这样,进行M次bfs,之后用一个三次方的dp来计算就行了。
我就是用这个算法,结果tle了一个点(悲哀)
好算法(NM):先bfs一趟,看看是否能把所有干旱格子搞定,解决不能满足要求的情况。
之后,计算每个格子的”流域“,即,从它开始水可以到达哪些干旱格子。可以证明这个流域一定是一个区间。
计算流域的时候可以用按高度排序从小到大依次计算,但需要排序;而更优雅地方法是拓扑排序,可以保证线性,或者bfs也行。
之后,用贪心或者比较华丽的dp来计算最小蓄水池的数量。

380分我知足了,虽然比zf低了10分,不过,都是一等奖啦。不知道zf是哪题出问题了。
  评论这张
 
阅读(1235)| 评论(1)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017