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

Tags: c/cpp, 算法
Archives Tip
QR Code for this page
Tipping QR Code
Leave a Comment

已有 6 条评论
  1. Mr.T Mr.T

    您好, 很抱歉我太迟回复了. 的确是这样的, 我在网络上找遍了国内外网站, 但是始终都找不到解决方案... 对于这点我深感纳闷... 你有QQ吗? 希望与您有机会在QQ上聊~

    1. @Mr.T我的邮箱可以在导航栏—About页面中找到。

  2. Mr.T Mr.T

    您好~ 读完了您的博客发现您是高手中的高手啊!
    在这边我想请问一个问题, 我其实来自新加坡, 希望能够把飞行平台做出来提供给新加坡的飞友进行联飞, 目前我采用windows架设了 fsd 联飞服务器, 一切都正常, 但是其余功能我实在不晓得如何解决, 例如建立呼号注册系统, 又如何解决在线联飞地图, 想请问说, 您是否知道在哪里能够查到这一类型的资料吗? 希望您能够给予我帮助~ 感激不尽!!

    1. @Mr.T众所周知地,Google中可以轻易找到FSD的源码,这就给二次开发提供了可能。呼号系统我所能想到的至少有三种不同的实现方法,但无一不是需要Web、网络通信等计算机程序开发基础的。如果完全没有基础,我认为这些东西难度还是比较大;如果有不错的基础,那大概是一码胜千言的时候。

    2. @BokjanBTW,在我所知道的范围内,网络上目前还没有现成的解决方案。都是自己写的。

    3. Mr.T Mr.T

      @Bokjan您认为这样的一个开发需要拥有什么样的技术基础呢?