棋盘覆盖
时间限制：3000 ms | 内存限制：65535 KB
难度：3
- 描述
-
在一个2k×2k（1<=k<=100）的棋盘中恰有一方格被覆盖，如图1（k=2时），现用一缺角的2×2方格（图2为其中缺右下角的一个），去覆盖2k×2k未被覆盖过的方格，求需要类似图2方格总的个数s。如k=1时，s=1;k=2时，s=5
- 输入
-
第一行m表示有m组测试数据；
每一组测试数据的第一行有一个整数数k; - 输出
- 输出所需个数s;
- 样例输入
-
3 1 2 3
- 样例输出
-
1 5 21
思路：类似大数乘进行处理
#include <iostream> #include <cstdio> #include <cmath> using namespace std; int main(){ int a[10000]; int n; cin>>n; while (n--) { int m; cin>>m; int sum = 0; int temp; int k = 1; a[0] = 1; for (int i = 0 ; i < m ; i++) { for (int j = 0 ; j < k; j++) { temp = a[j] * 4 + sum; a[j] = temp % 10; sum = temp / 10; } while (sum > 0) { a[k++] = sum % 10; sum /= 10; } } a[0] -= 1; int d = k-1; int high = a[d]/3>0?d:d-1; sum = 0; while (d >= 0) { temp = a[d] + sum; if (temp / 3> 0) { a[d] = temp / 3; sum = (temp-a[d]*3)*10; d--; } else { sum = a[d]*10; a[d] = 0; d--; } } for (int z = high ; z>=0; z--) { cout<<a[z]; } cout<<endl; } return 0; }
原创文章，作者：奋斗，如若转载，请注明出处：https://blog.ytso.com/tech/pnotes/20697.html