NYOJ-45-棋盘覆盖

时间限制： 3000 ms  |  内存限制： 65535 KB 难度： 3 描述

在一个2^k×2^k（1<=k<=100）的棋盘中恰有一方格被覆盖，如图1（k=2时），现用一缺角的2×2方格（图2为其中缺右下角的一个），去覆盖2^k×2^k未被覆盖过的方格，求需要类似图2方格总的个数s。如k=1时，s=1;k=2时，s=5

                                                                                    

图1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                                             图2                     

 

 

 

 

  输入 第一行m表示有m组测试数据； 每一组测试数据的第一行有一个整数数k; 输出 输出所需个数s; 样例输入 3 1 2 3 样例输出 1 5 21 这道题是有个规律的，就是个数s=2^((k-1)*2)+(上一个s),比如 k                s          1                 2^0+0 2                 2^2+1          3                 2^4+5

对了还可以化简一下 s=4^(k-1)+(上一个s),这样写的时候就少了好多循环。

#include <stdio.h>#define M 100int main(int argc,const char* argv[]){ int result[M+1][M]={0}; for(int i=1;i<=M;i++) //相当于k,打表法 { int carry,sum=0; result[i][0]=1; for(int j=0;j<(i-1);j++)//乘以4的次数 { carry=0; for(int k=0;k<=j;k++) { int r=result[i][k]*4+carry; result[i][k] = r; carry=r/10; } } carry=0; for(int k=0;k<=i-1;k++) { sum = result[i][k] + result[i-1][k]+carry;//加上上一个k的答案 result[i][k]=sum; carry=sum/10; } } int n; scanf("%d",&n); while(n--) { int m,l; scanf("%d",&m); for(int j=M-1;j>=0;j--) if(result[m][j]!=0) { l=j; break; } for(;l>=0;l--) { printf("%d",result[m][l]); } printf("\n"); } return 0;}

这是我自己总结的，我还在其他地方看到什么分治算法什么的，原谅我渣渣不知道，大家有兴趣可以去看看。