hduoj 1865 1sting

淩亂°似流年 2024-02-19 19:36 47阅读 0赞

## 1sting ##

**Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 7255 Accepted Submission(s): 2835**

Problem Description

You will be given a string which only contains ‘1’; You can merge two adjacent ‘1’ to be ‘2’, or leave the ‘1’ there. Surly, you may get many different results. For example, given 1111 , you can get 1111, 121, 112,211,22. Now, your work is to find the total number of result you can get.

Input

The first line is a number n refers to the number of test cases. Then n lines follows, each line has a string made up of ‘1’ . The maximum length of the sequence is 200.

Output

The output contain n lines, each line output the number of result you can get .

Sample Input

3 1 11 11111

Sample Output

1 2 8

Author

z.jt

Source

[2008杭电集训队选拔赛——热身赛 ][2008_]

Recommend

费波那奇数列+大数

#include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    int sum=0;
    
    int b[203][205]={0};
    
    void pre()
    {
    	int i,j;
    	b[0][0]=1;
    	b[1][0]=2;
    	b[2][0]=3;
    	int f=1;
    	int add=0;
    	for(i=3;i<202;i++)
    	{
    		for(j=0;j<23;j++){     // 这个地方哇了10次 
    			b[i][j]=(b[i-1][j]+b[i-2][j]+add);
    			add=b[i][j]/10000;
    			b[i][j]%=10000;
    		
    		}
    		if(add>0)
    		{
    			b[i][j]=add;
    			j++;
    		}
    		f=j;
    	
    	}
    }
    int main()
    {string a;
    	int n,i;
    	pre();
    	cin>>n;
    	while(n--)
    	{
    		cin>>a;
    		int n=a.length()-1;
    	    if(n==0)
    	    {
    	    	cout<<1<<endl;
    	    	continue;
    		}
    		i=204;
    		while(b[n][i]==0)
    		i--;
    		printf("%d",b[n][i]);
    		for(i--;i>=0;i--)
    		printf("%04d",b[n][i]);
    		printf("\n");
    		a.clear();
    	}
    	return 0;
    }

[2008_]: http://acm.hdu.edu.cn/search.php?field=problem&key=2008%BA%BC%B5%E7%BC%AF%D1%B5%B6%D3%D1%A1%B0%CE%C8%FC%A1%AA%A1%AA%C8%C8%C9%ED%C8%FC&source=1&searchmode=source