C. Board Moves(递推)

题意:有一个n*n的方格图,每个格子可以向周围8个方向移动,一次只能移动一步,最后要让所有的格子都移动到中间格子,问要多少步才能实现目标。

题解:

自己画的图:

C. Board Moves(递推)         C. Board Moves(递推)

 

当n=1时,只有中间一个小格,所以不需要移动,答案为0。

当n=3时,就要让橙色那一圈方格都移到中间,八个方格移动的步数就是8。

当n=5时,蓝色那圈每个格子需要两步,一共是16个格子,再加上橙色那圈,就是16x2+8,一共40步。

意思弄懂之后,就是解题,阿巴!

首先,某个方格在第n圈,它移动到中心就需要(n-1)步,

其次,第二圈是(2-1)*8格,第三圈是(3-1)*8,所以第n圈,就是(n-1)*8格;

设圈数为i,i=1时,step[1]=0;当i=2时,step[2]=(2-1)*8*(2-1)+step[1];当i=3时,step[3]=(3-1)*8*(3-1);也就是,每一圈对应的格数乘以每一格需要移动的次数,就是当前那一圈的步数,我们用递归把他加起来,存在数组里。

圈数和题中的n不相符合,但是,圈数=(n+1)/2,就可以处理数据了。

ACcode:

 

ll a[500100];

void calcu(ll n){

a[1] = 0;

for(ll i=2;i<n;i++)

a[i] = a[i- 1] + 8 * (i- 1) * (i - 1);

}

int main(){

calcu(500010);

int t;

cin >> t;

while (t--){

ll n;

cin >> n;

cout << a[(n + 1) / 2] << endl;//这里是把n转化成圈数,方便计算。

}

return 0;

}

 

上一篇:机器人能否返回原点


下一篇:求帮忙