【DPOJ1018】一中天文台

题目链接:https://dpoj.ghyer.com/problem/1018

这是一题卡内存限制的题目,内存限制5MB,但是数据却可以达到20,000,000,自然开一个20,000,000的bool数组是不能解决问题的,因为一个bool是一个字节,20000000/1024/1024 = 19MB,显然MLE。

由bool的1个字节却只表示1个bit的状态这个事情,让我联想到其实我们在写程序的时候经常对浪费的空间不屑一顾,比如一个数字最大值不超过128,但我们依旧选择开一个int而不会用更小的数据类型来替代。而本题里,一个数字只有两个状态,要么先前出现过,要么先前没有出现过,很自然可以联想是一个0或1的二进制数就能表示的。因此当然可以像c语言那样用一些bit类型的变量来代替。

我在这题选择使用int类型来存储状态,每个int变量用来存储32个数字的状态,那么20000000个数字,只需要开一个20000000/32 = 625000的int数组就能存储每个数字的状态。而空间大小可以计算:625000 * 4 / 1024 / 1024 = 2.38MB,这样就把19MB的bool所存储的状态压缩到了2.38MB的存储空间中。

而每个数字存储状态的位置被计算为:数组下标为 x/32的第x%32位。

查询时只要查询status[x/32] & (1 << x % 32)是否为true即可知道该数字先前是否出现过。

如果先前未出现过,则通过status[x/32] |= (1 << x % 32)来进行状态存储。

代码:https://dpoj.ghyer.com/judge/308

-- 热度:32 ℃
-- 于 共写了671个字
-- 文内使用到的标签:

评论已关闭。