MENU

无穷的序列与位域

May 10, 2014 • 程序阅读设置

题目名称:无穷的序列
内存限制: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个字节,位域结构数组元素间不能共享未使用的比特位。这里为了尽可能地完全利用内存空间,位域的许多特点不能体现出来,有兴趣的话,还请自己参考其他资料。

Archives Tip
QR Code for this page
Tipping QR Code