题目名称:无穷的序列
内存限制:128 MB
时间限制:1 s
【题目描述】 有一个无穷序列如下:
110100100010000100000…
请你找出这个无穷序列中指定位置上的数字
【输入格式】 第一行一个正整数N,表示询问次数;
接下来的N行每行一个正整数$A_i$,$A_i$表示在序列中的位置。
【输出格式】 N行,每行为0或1,表示序列第$A_i$位上的数字。
对于100%的数据有$N\leq 1500000$,$A_i\leq 10^{9}$
这是一个非常简单的问题,不出几秒钟就可以想到生成范围内的无穷序列,然后对应地输出就好了。
#include <iostream>
const int MAXN = 1000000000 + 10;
bool a[MAXN];
int main(void)
{
for (int i = 1, j = 0; i <= MAXN; i++, j++)
a[i] = 1, i += j + 1;
int n, tmp;
std::cin >> n;
while(n--)
{
std::cin >> tmp;
std::cout << a[tmp] << std::endl;
}
return 0;
}
答案是没有问题的,并且生成序列的速度很快。问题就在于,内存超了。此处BitArray
即是bool
,每个bool
占用一个字节,那么$10^{9}$个bool
共需要内存1GB,显然超了。若使用32位整型,内存需要消耗到4GB。 怎么办呢。不难发现,这个序列很简单,仅由0和1组成。由于这个序列相当于一个$a_n=10^{n-1}$的数列拼在一起,不难知道0的个数是远远多于1的。我们可以考虑把所有出现1的位置算出来,然后查出位置就行了。虽然刚才那个程序是肯定无法AC的,但是我们可以通过它计算出$10^{9}$内出现了多少个1。计算结果很快出来:44720个。那么我们就可以得到如下代码。
#include <cstdio>
const int MAX_ONE = 44720;
int map[MAX_ONE + 1];
void solve(int i)
{
for (int j = 0; j < MAX_ONE; j++)
if (map[j] == i)
{
puts("1");
return;
}
puts("1");
}
int main(void)
{
for (int i = 0, j = 1; j < 1000000000; )
map[i] = j, j += ++i;
int n, tmp;
scanf("%d", &n);
while(n--)
{
scanf("%d", &tmp);
solve(tmp);
}
return 0;
}
空间问题就完美解决了,简单计算一下$44720+10$个32位整型仅占用$\mathrm{sizeof}(\mathrm{int}) \times (44720+10)=4 \mathrm{B} \times 44730=178920 \mathrm{B} \approx 179 \mathrm{KB}$。但是问题又来了:题目有提到输入数据的组数最大可达到$1.5×10^{6}$,显然$O(n)$的算法速度太慢了。这倒是好解决:二分查找而已。把函数solve
修改一下就行了。
void solve(int i)
{
int l = 0, r = MAX_ONE;
while (l <= r)
{
if (map[(l + r) / 2] == i)
{
puts("1");
return;
}
if (map[r + l] / 2 > i)
r = (l + r) / 2 - 1;
else
l = (l + r) / 2 + 1;
}
puts("0");
}
时间复杂度已由$O(n)$改善到了$O(\log n)$,算是比较优的解法。到此本题基本上就解决了,然而生成序列的方法真的无法AC吗?我们来分析一下:因为序列中仅有0和1,所以它完全没有必要用1个字节,也就是8个比特来表示!显然1个比特足以表示1个数了。这样说来,一个bool中有8个比特,就可以表示8个数。$10^{9} \div 8 = 125000000$,仅需125MB就可以表示范围内的完整序列,剩下3MB足以支持整个程序的其他部分。单独操作二进制位并不是不能做到的,使用位域就能操作了。OJ上可以AC的代码如下。
#include <cstdio>
struct BitArray
{
bool a1 : 1;
bool a2 : 1;
bool a3 : 1;
bool a4 : 1;
bool a5 : 1;
bool a6 : 1;
bool a7 : 1;
bool a8 : 1;
};
BitArray b[125000010];
const int max = 1000000000;
int main(void)
{
int n, in;
b[0].a1 = 1;
b[0].a2 = 1;
b[0].a3 = 0;
b[0].a4 = 1;
b[0].a5 = 0;
b[0].a6 = 0;
b[0].a7 = 1;
b[0].a8 = 0;
for (int i = 11, j = 4; i<max; j++)
{
int im8 = i % 8;
if (!im8)
b[i / 8 - 1].a8 = 1;
else
switch (im8)
{
case 1:
b[i / 8].a1 = 1;
break;
case 2:
b[i / 8].a2 = 1;
break;
case 3:
b[i / 8].a3 = 1;
break;
case 4:
b[i / 8].a4 = 1;
break;
case 5:
b[i / 8].a5 = 1;
break;
case 6:
b[i / 8].a6 = 1;
break;
case 7:
b[i / 8].a7 = 1;
break;
}
i += j + 1;
}
scanf("%d", &n);
while(n--)
{
scanf("%d", &in);
int im8 = in % 8;
if (!im8)
printf("%d\n", b[in / 8 - 1].a8);
else
switch (im8)
{
case 1:
printf("%d\n", b[in / 8].a1);
break;
case 2:
printf("%d\n", b[in / 8].a2);
break;
case 3:
printf("%d\n", b[in / 8].a3);
break;
case 4:
printf("%d\n", b[in / 8].a4);
break;
case 5:
printf("%d\n", b[in / 8].a5);
break;
case 6:
printf("%d\n", b[in / 8].a6);
break;
case 7:
printf("%d\n", b[in / 8].a7);
break;
}
}
return 0;
}
整个程序突然多了许多行对吧。因为涉及到位操作,大部分的程序都用来计算操作位置了。因为进行大量的位置计算,评测结果表明此法比刚才提到的解法时间开销更大,约3倍,但尚在可接受范围内。10个测试点共计耗时1.3s。这里的位域,其实就是一个结构,冒号后的数字代表其占用比特位的个数,定义8个成员的原因是正好使用完1个字节,位域结构数组元素间不能共享未使用的比特位。这里为了尽可能地完全利用内存空间,位域的许多特点不能体现出来,有兴趣的话,还请自己参考其他资料。