首页 > 代码库 > BZOJ 2656 ZJOI2012 数列(sequence) 高精度+记忆化搜索
BZOJ 2656 ZJOI2012 数列(sequence) 高精度+记忆化搜索
题目大意:给定一个数列的通项公式,求数列的某一项
高精度+记忆化搜索没说的 其实不用记忆化搜索的但是既然写完了就写完了吧
顺便学习了一下友元函数之类的东西- -
#include <map> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; class Big_Int{ private: int num[110],cnt; public: Big_Int(int _=0) { memset(num,0,sizeof num); num[cnt=1]=_; } friend istream& operator >> (istream& _,Big_Int &x); friend ostream& operator << (ostream& _,Big_Int &x); bool Is_Odd() { return num[1]&1; } void operator += (const Big_Int& x) { int i,k=max(cnt,x.cnt); for(i=1;i<=k;i++) { num[i]+=x.num[i]; num[i+1]+=num[i]/10; num[i]%=10; } if(num[k+1]) k++; cnt=k; } void operator >>= (int x) { int i; for(i=cnt;i;i--) { num[i-1]+=(num[i]&1)*10; num[i]>>=1; } num[0]=0; if(!num[cnt]) --cnt; } bool operator < (const Big_Int &x) const { if(cnt != x.cnt) return cnt < x.cnt; int i; for(i=cnt;i;i--) if(num[i]!=x.num[i]) return num[i]<x.num[i]; return false; } }; map<Big_Int,Big_Int> f; istream& operator >> (istream& _,Big_Int &x) { static char s[110]; int i; scanf("%s",s);x.cnt=strlen(s); for(i=1;i<=x.cnt;i++) x.num[i]=s[x.cnt-i]-'0'; return _; } ostream& operator << (ostream& _,Big_Int &x) { int i; printf("%d",x.num[x.cnt]); for(i=x.cnt-1;i>0;i--) printf("%d",x.num[i]); return _; } Big_Int& Memorial_Search(Big_Int& x) { if(f.find(x)!=f.end()) return f[x]; Big_Int& re=f[x]; if(x.Is_Odd()) { Big_Int s1=x;s1>>=1; Big_Int s2=s1;s2+=Big_Int(1); re+=Memorial_Search(s1); re+=Memorial_Search(s2); } else { Big_Int s=x;s>>=1; re+=Memorial_Search(s); } return re; } int main() { int T; f[Big_Int(0)]=0; f[Big_Int(1)]=1; for(cin>>T;T;T--) { Big_Int n; cin>>n; cout<<Memorial_Search(n)<<endl; } return 0; }
BZOJ 2656 ZJOI2012 数列(sequence) 高精度+记忆化搜索
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。