?

棋盤覆蓋

時(shí)間限制：3000 ms ?|? 內(nèi)存限制：65535 KB 難度：3 描述

在一個(gè)2^k×2^k（1<=k<=100）的棋盤中恰有一方格被覆蓋，如圖1（k=2時(shí)），現(xiàn)用一缺角的2×2方格（圖2為其中缺右下角的一個(gè)），去覆蓋2^k×2^k未被覆蓋過的方格，求需要類似圖2方格總的個(gè)數(shù)s。如k=1時(shí)，s=1;k=2時(shí)，s=5

????????????????????????????????????????????????????????????????????????????????????

?

圖1

?	?	?	?
?	?	?	?
?	?	?	?
?	?	?	?

?????????????????????????????????????????????圖2??????????????????? ?

?	?
?	?

?

?

輸入

第一行m表示有m組測試數(shù)據(jù)；
每一組測試數(shù)據(jù)的第一行有一個(gè)整數(shù)數(shù)k;

輸出

輸出所需個(gè)數(shù)s;

樣例輸入

3 1 2 3

樣例輸出

1 5 21

1 /* 功能Function Description: NYOJ-45 2 開發(fā)環(huán)境Environment: DEV C++ 4.9.9.1 3 技術(shù)特點(diǎn)Technique: 4 版本Version: 5 作者Author: 可笑癡狂 6 日期Date: 20120821 7 備注Notes: 8 本題求的是大數(shù)(4^k-1)/3,可以轉(zhuǎn)化為首項(xiàng)為1，公比為4的等比數(shù)列的前k項(xiàng)的和 9 把除法轉(zhuǎn)化為加法和乘法。 10 */ 11 #include<stdio.h> 12 #include<string.h> 13 14 void mult(int *tmp,int num,int &bit) 15 { 16 int t=0; 17 for(int i=0;i<bit;++i) 18 { 19 t=tmp[i]*num+t; 20 tmp[i]=t%10; 21 t/=10; 22 } 23 if(t) 24 { 25 tmp[bit]=t; 26 ++bit; 27 } 28 } 29 30 void add(int *sum,int *tmp,int &bit) 31 { 32 int i,t=0; 33 for(i=0;i<bit;++i) 34 { 35 sum[i]+=tmp[i]; 36 sum[i+1]+=sum[i]/10; 37 sum[i]%=10; 38 } 39 if(sum[i]) 40 ++bit; 41 } 42 43 int main() 44 { 45 int k,T,i,bit; 46 int tmp[100]; //存放每一項(xiàng)的值 47 int sum[100]; //存放結(jié)果 48 scanf("%d",&T); 49 while(T--) 50 { 51 memset(tmp,0,sizeof(tmp)); 52 memset(sum,0,sizeof(sum)); 53 scanf("%d",&k); 54 tmp[0]=1; 55 sum[0]=1; 56 bit=1; 57 for(i=1;i<k;++i) 58 { 59 mult(tmp,4,bit); 60 add(sum,tmp,bit); 61 } 62 for(i=bit-1;i>=0;--i) 63 printf("%d",sum[i]); 64 printf("\n"); 65 } 66 return 0; 67 }

?

總結(jié)

以上是生活随笔為你收集整理的NYOJ-45 棋盘覆盖的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。