链接：http://acm.hdu.edu.cn/showproblem.php?pid=6253
题意：
马可以往一个方向走两步，然后转个弯走一步，这样算一次动作，求问马n次动作后，能到达多少个点，重复到达的点只算一次。
思路：
一开始完全没思路，画图找了半天把自己画崩了，后面看到数据和样例感觉这应该是一道公式题，然后打了一个表。。
打表代码：
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long struct node{
int x,y,step;
}; int dx[] = {,,-,-,,,-,-};
int dy[] = {,-,,-,,-,,-};
int ans[],vis[][];
void bfs(){
node now;
queue<node>q;
now.x = ,now.y = ,now.step = ;
ans[] = ;
vis[][] = ;
q.push(now);
while(!q.empty()){
node now = q.front();
q.pop();
if(now.step == ) continue;
node nex;
for(int i = ;i < ;i ++){
nex.x = now.x + dx[i];
nex.y = now.y + dy[i];
if(vis[nex.x][nex.y]==)
nex.step = now.step+,q.push(nex),ans[nex.step]++,vis[nex.x][nex.y]=;
}
}
for(int i = ;i <= ;i ++)
cout<<ans[i]<<" ";//ans[i+1] += ans[i];
cout<<endl;
} int main()
{
bfs();
return ;
}
这个表求得是每一步多增加的点数，可以得到以下数据
1 8 32 68 96 120 148 176 204 232 260 288 316 344 372 400 428 456 484 512 540
我们可以发现这张表从120开始后面每一次都是+28
从120开始这个序列就可以变成一个等差数列，但是题目是要我们求所有的，那就直接等差数列前n项和公式就好了，把第一项设为120或者120后面随意一个数字就好了，前n项求和后加上第一项前面的那些数的和就好了
这道题会爆long long ，我们用 unsigned long long 就好了
实现代码;
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
/*
struct node{
int x,y,step;
}; int dx[] = {2,2,-2,-2,1,1,-1,-1};
int dy[] = {1,-1,1,-1,2,-2,2,-2};
int ans[10000],vis[1000][1000];
void bfs(){
node now;
queue<node>q;
now.x = 500,now.y = 500,now.step = 0;
ans[0] = 1;
vis[500][500] = 1;
q.push(now);
while(!q.empty()){
node now = q.front();
q.pop();
if(now.step == 20) continue;
node nex;
for(int i = 0;i < 8;i ++){
nex.x = now.x + dx[i];
nex.y = now.y + dy[i];
if(vis[nex.x][nex.y]==0)
nex.step = now.step+1,q.push(nex),ans[nex.step]++,vis[nex.x][nex.y]=1;
}
}
for(int i = 0;i <= 20;i ++)
cout<<ans[i]<<" ";//ans[i+1] += ans[i];
cout<<endl;
} int main()
{
bfs();
return 0;
}
*/
//1 8 32 68 96 120 148 176 204 232 260 288 316 344 372 400 428 456 484 512 540
//1 9 41 109 205 325 473 649 853 1085 1345 1633 1949 2293 2665 3065 3493 3949 4433 4945 5485 int a[] = {, , , , , ,};
int main()
{
ull t,n,cas = ;
ull ans;
cin>>t;
while(t--){
cin>>n;
if(n < ) cout<<"Case #"<<cas++<<": "<<a[n]<<endl;
else{
ans = *(n-) + (n-)*(n-)*;
cout<<"Case #"<<cas++<<": "<<ans+<<endl;
}
}
return ;
}