首页 > 代码库 > HDU 4148 Length of S(n)(规律题)
HDU 4148 Length of S(n)(规律题)
Problem Description
http://acm.hdu.edu.cn/showproblem.php?pid=4148
A number sequence is defined as following:
S(1)=1,
S(2)=11,
S(3)=21,
S(4)=1211,
S(5)=111221,
S(6)=312211,
……
Now, we need you to calculate the length of S(n).
S(1)=1,
S(2)=11,
S(3)=21,
S(4)=1211,
S(5)=111221,
S(6)=312211,
……
Now, we need you to calculate the length of S(n).
Input
The input consists of multiple test cases. Each test case contains one integers n.
(1<=n<=30)
n=0 signal the end of input.
(1<=n<=30)
n=0 signal the end of input.
Output
Length of S(n).
Sample Input
2 5 0
Sample Output
2 6题目分析:/** *@xiaoran *规律题,就看能不能找到这个规律了,我还是挺幸运的找到了规律, *如果找不到还是看题解吧。规律如下: *s[i]是看s[i-1]形成的,例如;s[1]=1; *s[2]=11;代表的是s[i-1=1]里有1个1 *s[3]=21;代表的是s[i-1=2]里有2个1 *s[4]=1211;代表的是s[i-1=3]里有1个1,1个2,2个1, *明白了吧,注意从左向右看,不能跳跃,那么来模拟规律生成字符串吧 */
AC代码:/** *@xiaoran *规律题,就看能不能找到这个规律了,我还是挺幸运的找到了规律, *如果找不到还是看题解吧。规律如下: *s[i]是看s[i-1]形成的,例如;s[1]=1; *s[2]=11;代表的是s[i-1=1]里有1个1 *s[3]=21;代表的是s[i-1=2]里有2个1 *s[4]=1211;代表的是s[i-1=3]里有1个1,1个2,2个1, *明白了吧,注意从左向右看,不能跳跃,那么来模拟规律生成字符串吧 */ #include<iostream> #include<cstdio> #include<map> #include<cstring> #include<string> #include<algorithm> #include<queue> #include<vector> #include<stack> #include<cstdlib> #include<cctype> #include<cmath> #define LL long long using namespace std; //前30个的长度 const int a[33]={0,1,2,2,4,6,6,8,10,14,20 ,26,34,46,62,78,102 ,134,176,226,302,408 ,528,678,904,1182,1540 ,2012,2606,3410,4462 }; string s[33]; int main() { s[1]="1"; for(int i=2;i<=30;i++){ int j,k=1,len=s[i-1].size(); for(j=1;j<len;j++){ if(s[i-1][j]==s[i-1][j-1]){ k++; }else{ s[i]+=char (k+'0'); s[i]+=s[i-1][j-1]; k=1; } } s[i]+=char (k+'0'); s[i]+=s[i-1][j-1]; cout<<s[i].size()<<","; } int n; while(cin>>n&&n){ cout<<s[n].size()<<endl; //cout<<a[n]<<endl; } return 0; }
HDU 4148 Length of S(n)(规律题)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。