光棍的yy
时间限制:1000 ms | 内存限制:65535 KB
难度:2
- 描述
-
yy经常遇见一个奇怪的事情,每当他看时间的时候总会看见11:11,这个很纠结啊。
现在给你m个1,你可以把2个1组合成一个2,这样就不是光棍了,问这样的组合有多少种??
例如(111 可以拆分为 111 12 21 有三种)
- 输入
- 第一行输入一个n表示有n个测试数据
以下n行,每行输入m个1
(1 <= n,m <= 200) - 输出
- 输出这种组合种数,占一行
- 样例输入
-
3 11 111 11111
- 样例输出
-
2 3 8
- 来源
- hdu
-
上传者
思路:基本的大数进位
#include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> #include<cmath> using namespace std; int main() { int a[205][105]; memset(a,0,sizeof(a)); a[0][0]=1; a[1][0]=1; a[2][0]=2; for(int i=3;i<=200;i++) { int up=0; for(int j=0;j<=100;j++) { int sum=a[i-1][j]+a[i-2][j]+up; a[i][j]=sum%10; up=sum/10; } } int t; cin>>t; while(t--) { string str; cin>>str; int k=str.size(); int i; for(i=100; !a[k][i]; i--);//chu 0一开始wa了一次 忘记打;了 蛋筒 for(int j=i; j>=0; j--) { printf("%d",a[k][j]); } printf("\n"); } }