[规律]跳马

题目描述

一个骑士在一个无限大的国际象棋棋盘里跳。一开始，这个国际象棋棋盘的每一个格子都是被标记为未被走过的，而骑士一开始可以以任意的一个格子作为起点，并且这个格子标记为走过。然后，他可以以如下图的规则跳N次，每一个他所到过的格子都会被标记为已经走过。
 
现在，我们需要知道在N次跳跃之后，有多少个格子可能被标记为走过。

输入

第一行一个整数T，表示数据组数
接下来T行，每行一个整数N

输出

共T行，每行一个整数，表示对应测试数据的答案

样例输入

3
0
1
7

样例输出

1
9
649

提示

对于30%的数据，1<=T<=10，N<=1,000
对于60%的数据，1<=T<=100，N<=1,000,000
对于100%的数据，1<=T<=100,000，N<=1,000,000,000

 

思路：先把n=1~10的结果用bfs求出并打成表，发现 结果的增量(a[n]=ans[n]-ans[n-1]) 的增量(b[n]=a[n]-a[n-1]) 在n>=6时总为28

于是可以推出n>=4时求结果的公式 为：n-=3,ans=(14n+92)(n-1)+205

 

AC代码：

#include <iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define N 5010
typedef unsigned long long ll;
using namespace std;
/*打表部分
struct Node{
  ll x,y,step;
};
ll n;
ll ans[110];
ll b[110];
ll dire[8][2]={-2,1,-1,2,1,2,2,1,-2,-1,-1,-2,1,-2,2,-1};
queue<Node> q;
bool vis[N][N];

ll bfs(){
  ll ret=0;
  while(!q.empty()) q.pop();
  memset(vis,0,sizeof(vis));
  Node sta;
  sta.x=1000; sta.y=1000; sta.step=0; vis[sta.x][sta.y]=1;
  q.push(sta);
  while(!q.empty()){
    Node head=q.front();
    q.pop();
    ret++;
    for(ll i=0;i<8;i++){
        Node nxt;
        nxt.x=head.x+dire[i][0];
        nxt.y=head.y+dire[i][1];
        nxt.step=head.step+1;
        if(nxt.x>=0&&nxt.x<N&&nxt.y>=0&&nxt.y<N&&!vis[nxt.x][nxt.y]&&nxt.step<=n){
            vis[nxt.x][nxt.y]=1;
            q.push(nxt);
        }
    }
  }
  return ret;
}

int main()
{
    for(n=1;n<=10;n++){
        ans[n]=bfs();
        printf("ans[%lld]=%lld",n,ans[n]);
        if(n!=1) {
                b[n]=ans[n]-ans[n-1];
                printf(" %lld",b[n]);
                if(n!=2) printf(" %lld
",b[n]-b[n-1]);
                else printf("
");
        }
        else printf("
");
    }
    return 0;
}
*/
ll a[4]={1,9,41,109};//n=0~3时的结果
int main(){
  ll t;
  scanf("%llu",&t);
  while(t--){
    ll n;
    scanf("%llu",&n);
    if(n<=3) printf("%llu
",a[n]);
    else {
        n-=3;
        ll ans=(14*n+92)*(n-1)+205;
        printf("%llu
",ans);
    }
  }
  return 0;
}