hdu-1041（大数模板）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1041

题意：电脑中存在数字1，进行扩展操作，如果遇到1变为“01”，如果遇到0，变为“10”，经过一次变换称为“01”，两次“1001”，三次“01101001”，

求经过n次变换，得到的01序列中有多少对相邻的0。

思路：先打表得到规律1,1,3,5,11,21,43……

找规律可以发现

1*2+1=3；

1*2+3=5；

3*2+5=11；

5*2+11=21；

……；

之后就是求和的事了，由于结果过大，用大数做就行了。

#include<iostream> #include<cstdio> #include<string> using namespace std; string str[1010]; string add(string s1,string s2) {if(s1.length()<s2.length()){string tmp=s1;s1=s2;s2=tmp;}int l1=s1.length(),l2=s2.length(),i,j;for(i=l1-1,j=l2-1;i>=0;i--,j--){s1[i]=char(s1[i]+(j>=0?s2[j]-'0':0));if(s1[i]-'0'>=10){s1[i]=char((s1[i]-'0')%10+'0');if(i) s1[i-1]++;else s1="1"+s1;}}return s1; } int main(void) {str[1]="0",str[2]="1",str[3]="1",str[4]="3",str[5]="5",str[6]="11";for(int i=7;i<=1005;i++){str[i]=add(add(str[i-2],str[i-2]),str[i-1]);} int n;while(~scanf("%d",&n)){cout<<str[n]<<endl;}return 0; }

 

转载于:https://www.cnblogs.com/2018zxy/p/9745592.html

总结

以上是生活随笔为你收集整理的hdu-1041（大数模板）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。