问题标题: 酷町堂：2195 Blah-数集

题目描述 Description

集合的前N个元素：编一个程序，按递增次序生成集合M的最小的N个数，M的定义如下：
(1)数1属于M；
(2)如果X属于M，则Y=2*x+1也属于M；
(3)此外再没有别的数属于M。

输入描述 Input Description

所求元素序号n(1<=n<=500000)

输出描述 Output Description

对于每个输入，输出集合的第n个元素值

 

不用高精，输入500000，输出-1；

用了高精，输入500000，超时。

#include<bits/stdc++.h>
#include<iostream>
#include<cstring>
using namespace std;
int n,a[1000005],b[1000005],c[2000005];
string Plus(string x,string y){
	memset(a,0,sizeof(a));
	memset(b,0,sizeof(b));
	memset(c,0,sizeof(c));
	a[0]=x.length(),b[0]=y.length();
	c[0]=max(a[0],b[0]);
	for(int i=1;i<=a[0];i++){
		a[i]=x[a[0]-i]-'0';
	}
	for(int i=1;i<=b[0];i++){
		b[i]=y[b[0]-i]-'0';
	}
	int jw=0;
	for(int i=1;i<=c[0];i++){
		c[i]=a[i]+b[i]+jw;
		jw=c[i]/10;
		c[i]%=10;
	}
	if(jw!=0){
		c[0]++;
		c[c[0]]=jw;
	}
	string ans="";
	for(int i=c[0];i>=1;i--){
		ans+=char(c[i]+'0');
	}
	return ans;
}
string x="1";
int main(){
	cin>>n;
	for(int i=1;i<n;i++){
		x=Plus(x,Plus(x,"1"));
	}
	cout<<x;
	return 0;
} 

 

汪恺恒在2021-01-25 13:07:17追加了内容

队列写法，输入500000还是超时

#include<iostream>
#include<cmath>
#include<bits/stdc++.h>
using namespace std;
long long n,q[500005];
void work(){
	int r=2,t=1;
	q[1]=1;
	while(r<=n){
		long long t1=q[t]*2+1;
		t++;
		if(t1==q[r-1]) continue;
		q[r++]=t1;
	}
}
int main(){
	cin>>n;
	work();
	cout<<q[n];
	return 0;
}