[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之类的到时候会做为一个课题专门写一篇文章

完美通过

本站遵循「CC BY 4.0」创作共享协议,转载请注明出处