0
已解决
初级启示者
2195 Blah-数集
经验值：2400 时间限制：1000毫秒 内存限制：128MB
题目描述 De**ion
集合的前N个元素：编一个程序，按递增次序生成集合M的最小的N个数，M的定义如下：
(1)数1属于M；
(2)如果X属于M，则Y=2*x+1也属于M；
(3)此外再没有别的数属于M。
输入描述 Input De**ion
所求元素序号n(1<=n<=70000)
输出描述 Output De**ion
对于每个输入，输出集合的第n个元素值
样例输入 Sample Input
3
样例输出 Sample Output
7
错误代码 TLE 80分：
#include<bits/stdc++.h>
using namespace std;
int n,t[1000005];
string f[70005];
string check(string a){
int x=0;
memset(t,0,sizeof(t));
for(int i=a.size()-1;i>=0;i--){
t[i]=(a[i]-'0')*2+x;
x=t[i]/10;
t[i]%=10;
}
string c="";
for(int i=0;i<a.size();i++){
char o=t[i]+'0';
c+=o;
}
if(x>0){
char o=x+'0';
c=o+c;
}
c=' '+c;
c[c.size()-1]++;
int k=c.size()-1;
while(c[k]-'0'>=10){
c[k]-=10;
k++;
c[k]++;
}
if(c[0]==' '){
c.erase(0,1);
}
return c;
}
int main(){
cin>>n;
f[1]="1";
for(int i=2;i<=n;i++){
f[i]=check(f[i-1]);
// cout<<f[i]<<endl;
}
cout<<f[n];
return 0;
}
大佬快来啊！怎么优化？多少豆子都行！！！
熊潇然在2022-11-19 11:36:14追加了内容
qwq
熊潇然在2022-11-20 11:29:02追加了内容
@汪宇航 教教我咋做啊
0
已采纳
新手启示者
没学过快速幂装什么这个md我都不敢写
0
高级启示者
我忘了你洛谷用户名是什么了
0
新手天翼
shui
0
新手天翼
shui
0
新手天翼
shui
0
新手启示者
我要豆子！
0
中级守护
用高精度，求2^（n-1）（不用快速幂也行）
再加上n-1就ok（应该吧。。。我没做）
0
中级守护
这个豆子嘛，我再要15个不过分吧（doge）
0
中级守护
搞错了搞错了，我试了一下，2^70000会超时！！！
0
初级天翼
不会
0
新手启示者
优什么化……快速幂
