题意:有一个n*n的方格图,每个格子可以向周围8个方向移动,一次只能移动一步,最后要让所有的格子都移动到中间格子,问要多少步才能实现目标。
题解:
自己画的图:
当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;
}