0%

[codevs1670] 无穷序列

题目描述

有一个无穷序列如下:110100100010000100000…,请你找出这个无穷序列中指定位置上的数字

输入格式

第一行一个正整数 N,表示询问次数;接下来的 N 行每行一个正整数 Ai,Ai 表示在序列中的位置

输出格式

N 行,每行为 0 或 1,表示序列第 Ai 位上的数字

输入样例

4
3
14
7
6

输出样例

0
0
1
0

数据规模

对于 100% 的数据有 N≤1500000;Ai≤10^9

解题思路

刚开始看到这道题目时,第一眼想到的就是把这个数生成出来,储存到数组里,然后问一个就寻找对应数组中的值,然后发现当输入数据达到 10^9 时就不行了

数组开不到这么大

(map、hash 没有试过,不知道行不行)

那我们换一种思路:既然这个数就只有 1、0,而且这个1也是有规律的:1,2,4,7…,这个数列相差 1,2,3…,那我们就把 1 的位置保存下来

#include <cstdio>
#include <cstdlib>
#include <tr1/unordered_map>
using namespace std;
using namespace tr1;

unordered_map<int, bool>f;
const size_t fmax = 20000000;
char buf[fmax], *bpos, puf[fmax];
size_t ppos;

long now = 1, t = 1, n;
inline void read(long &x)
{
    if (bpos == NULL)
    {
        fread(buf, 1, fmax, stdin);
        bpos = buf;
    }
    x = strtol(bpos,&bpos,10);
    return;
}
inline void _putchar(char c)
{
    puf[ppos++] = c;
    return;
}

int main()
{
    freopen("seq.in", "r", stdin);
    freopen("seq.out", "w", stdout);

    for (int i = 1; i <= 44721; i++)
    {
        f[now] = true;
        now += t++;
    }

    read(n);
    for (int i = 1; i <= n; i++)
    {
        long x;
        read(x);
        _putchar(f[x] == true ? '1' : '0');
        _putchar('\n');
    }

    fwrite(puf, 1, ppos, stdout);
    return 0;
}

unordered_map 和 fread、fwrite 都解决不了即将超时间内存

虽然这个代码可以过,但是时间和空间利用的很不好,处于超时间、内存的边缘

主要原因就出在 unordered_map 太慢(map 更不用说了)

好,那我就不用 stl/tr1,自己手打一个 hash

#include <cstdio>
#include <cstdlib>
#define p 100003
#define hash(a) a%p
using namespace std;

const size_t fmax = 20000000;
char buf[fmax], *bpos, puf[fmax];
size_t ppos;

long now = 1, t = 1, n, h[p];
inline void read(long &x)
{
    if (bpos == NULL)
    {
        fread(buf, 1, fmax, stdin);
        bpos = buf;
    }
    x = strtol(bpos,&bpos,10);
    return;
}
inline void _putchar(char c)
{
    puf[ppos++] = c;
    return;
}

int find(int x)
{
    int y = hash(x);
    while (h[y] && h[y] != x)
        y = hash(++y);
    return y;
}

void push(int x)
{
    h[find(x)] = x;
}
bool check(int x)
{
    return h[find(x)] == x;
}

int main()
{
    freopen("seq.in", "r", stdin);
    freopen("seq.out", "w", stdout);

    for (int i = 1; i <= 44721; i++)
    {
        push(now);
        now += t++;
    }

    read(n);
    for (int i = 1; i <= n; i++)
    {
        long x;
        read(x);
        _putchar(check(x) == true ? '1' : '0');
        _putchar('\n');
    }

    fwrite(puf, 1, ppos, stdout);
    return 0;
}

至于手写 hash 之类的到时候会做为一个课题专门写一篇文章

完美通过

  • 本文作者: rcxzsc
  • 本文链接: https://rcxzsc.com/archives/401/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY 许可协议。转载请注明出处!