poj2506-Tiling(规律，大数)

水深无声 2022-08-04 10:48 136阅读 0赞

Tiling

<table style="text-align:center"> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;8300</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;4002</td> 
  </tr> 
 </tbody> 
</table>

Description

In how many ways can you tile a 2xn rectangle by 2x1 or 2x2 tiles?  
Here is a sample tiling of a 2x17 rectangle.  
![2506_1.jpg][]

Input

Input is a sequence of lines, each line containing an integer number 0 <= n <= 250.

Output

For each line of input, output one integer number in a separate line giving the number of possible tilings of a 2xn rectangle.

Sample Input

2
    8
    12
    100
    200

Sample Output

3
    171
    2731
    845100400152152934331135470251
    1071292029505993517027974728227441735014801995855195223534251

这题主要是找寻规律，剩下的就是大数了！

我们假设要找2\*n的种数：

2\*（n-1）的已经拼好了，2\*（n-2）也已经拼好了

我们可以知道，第n块只与n-1和n-1块有关系

第n-1块变成第n块只有一种方法

第n-2块变成第n块有三种方法，但是有一种和上边的那一种重复了

所以an=2\*a（n-2）+a（n-1）；

找出规律后代码也是可以优化的

未优化的 47ms：

#include<cstdio>
    #include<cstring>
    using namespace std;
    struct node
    {
    	int a[10000];
    }s[300];
    int main()
    {
    	int c,n,i,j;
    	s[0].a[0]=1;
    	s[1].a[0]=1;
    	for(i=2;i<260;i++)
    	{
    		c=0;
    		for(j=0;j<10000;j++)
    		{
    			s[i].a[j]=s[i-1].a[j]+2*s[i-2].a[j]+c;
    			c=s[i].a[j]/10;
    			s[i].a[j]%=10;
    		}
    	}
    	while(scanf("%d",&n)!=EOF)
    	{
    		for(i=10000-1;s[n].a[i]==0;i--);
    		for(j=i;j>=0;j--)
    		printf("%d",s[n].a[j]);
    		printf("\n");
    	}
    return 0;
    }

稍加优化 16ms：

#include<cstdio>
    #include<cstring>
    using namespace std;
    struct node
    {
    	int a[10000];
    }s[300];
    int main()
    {
    	int c,n,i,j,cot=1;
    	s[0].a[0]=1;
    	s[1].a[0]=1;
    	for(i=2;i<260;i++)
    	{
    		c=0;
    		for(j=0;j<cot;j++)
    		{
    			s[i].a[j]=s[i-1].a[j]+2*s[i-2].a[j]+c;
    			c=s[i].a[j]/10;
    			s[i].a[j]%=10;
    		}
    		while(c)
    		{
    			s[i].a[cot++]=c%10;
    			c/=10;
    		}
    	}
    	while(scanf("%d",&n)!=EOF)
    	{
    //		for(i=10000-1;s[n].a[i]==0;i--);
    //		for(j=i;j>=0;j--)
    //		printf("%d",s[n].a[j]);
    //		printf("\n");
    	for(i=cot-1;s[n].a[i]==0;i--);
    	for(;i>=0;i--)
    	printf("%d",s[n].a[i]);
    	printf("\n");
    	}
    return 0;
    }

优化后 0ms ：

#include<cstdio>
    #include<cstring>
    using namespace std;
    struct node
    {
    	int a[10000];
    }s[300];
    int main()
    {
    	int c,n,i,j,cot=1;
    	long long temp;
    	s[0].a[0]=1;
    	s[1].a[0]=1;
    	for(i=2;i<260;i++)
    	{
    		c=0;
    		for(j=0;j<cot;j++)
    		{
    			temp=s[i-1].a[j]+2*s[i-2].a[j]+c;
    			c=temp/100000;
    			s[i].a[j]=temp%100000;
    		}
    		if(c>0)
    		{
    			s[i].a[cot++]=c;
    		}
    	}
    	while(scanf("%d",&n)!=EOF)
    	{
    //		for(i=10000-1;s[n].a[i]==0;i--);
    //		for(j=i;j>=0;j--)
    //		printf("%d",s[n].a[j]);
    //		printf("\n");
    	for(i=cot-1;s[n].a[i]==0;i--);
    	printf("%d",s[n].a[i]);
    	for(i-=1;i>=0;i--)
    
    	printf("%05d",s[n].a[i]);
    	printf("\n");
    	}
    return 0;
    }

[2506_1.jpg]: /images/20220731/043c802391c04b6a9ac38261ae1e0c02.png