NC208114. 宝藏男孩
描述
小明是一个喜欢探险的小孩，有一天，他的外婆带他去了一个大小为n×n网格的森林里，其中n是奇数(不能被2整除)，每个格子中，都放有一个宝藏，他想把这些宝藏都集中到同一个单元格中。但是，小明正沉迷于探险小说，所以想请你帮帮他。你的任务是找到所有宝藏进入一个单元格(即n2-1单元格应该包含0个宝藏，而一个单元格应该包含n2图形)所需的最小移动次数。
在一次移动中，你可以选择某个单元格中的一个宝藏，并将其移动到与当前单元格共享边或角的单元格中，也就是说，从单元格(i,j)你可以将其中的宝藏移动到以下单元格中:
· (i−1,j−1);
· (i−1,j);
· (i−1,j+1);
· (i,j−1);
· (i,j+1);
· (i+1,j−1);
· (i+1,j);
· (i+1,j+1);
输入描述
输入：
第一行输入一个整数t (1≤t≤200)，表示测试用例的数量。接下来的t行每行包含一个整数n (1≤n<5*105)表示网格规模。题目保证n全为奇数且所有测试用例中n的总和不超过5*105，即∑n≤5*105。
输出描述
输出：
每一行测试用例包含一个答案，即所需的最小移动次数。
示例1
输入:
3 1 5 499993
输出:
0 40 41664916690999888
Python(2.7.3) 解法, 执行用时: 75ms, 内存消耗: 10848K, 提交时间: 2020-06-20 13:50:23
def main():
n = int(raw_input())
m = (n - 1) // 2
ans = 0
for i in range(1 , m + 1):
c = (2 * i + 1) * (2 * i + 1) - (2 * i - 1) * (2 * i - 1)
ans += c * i
print ans
t = int(raw_input())
for i in xrange(t):
main()
C++(g++ 7.5.0) 解法, 执行用时: 3ms, 内存消耗: 384K, 提交时间: 2023-03-29 16:15:18
#include<bits/stdc++.h>
#define int long long
using namespace std;
int T,n;
signed main()
{
cin>>T;
while(T--)
{
cin>>n;
int ans=0,tmp=8;
for(int i=1;i<=n/2;i++)ans+=tmp*i,tmp+=8;
cout<<ans<<'\n';
}
return 0;
}
pypy3(pypy3.6.1) 解法, 执行用时: 193ms, 内存消耗: 55628K, 提交时间: 2020-06-20 13:22:51
from itertools import accumulate
N = 10 ** 6
delta = [(i * 2 + 1) ** 2 - (i * 2 - 1) ** 2 for i in range(N)]
delta[0] = 1
s = list(accumulate((i * delta[i] for i in range(N))))
t = int(input())
for _ in range(t):
n = int(input())
print(s[n // 2])
C++14(g++5.4) 解法, 执行用时: 2ms, 内存消耗: 500K, 提交时间: 2020-08-23 11:35:32
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
long long a;
cin>>a;
a/=2;
long long sum=0;
for(int i=0;i<=a;i++){
sum+=(long long)i*i*8;
}
cout<<sum<<endl;
}
return 0;
}
Go(1.9.1) 解法, 执行用时: 3ms, 内存消耗: 1004K, 提交时间: 2020-06-20 14:46:59
package main
import "fmt"
func main() {
var n int
fmt.Scan(&n)
for i:=0;i<n;i++{
var x int
fmt.Scan(&x)
var res int
for i:=1;i<=x/2;i++{
res+=i*((i*2+1)*(i*2+1)-(i*2-1)*(i*2-1))
}
fmt.Println(res)
}
}
C++11(clang++ 3.9) 解法, 执行用时: 3ms, 内存消耗: 376K, 提交时间: 2020-07-13 15:55:13
#include<iostream>
using namespace std;
int main()
{
long long i,t,n,l,ans;
cin>>t;
while(t--)
{
cin>>n;
ans=0;
l=(n-1)/2;
for(i=1;i<=l;i++)
ans+=8*i*i;
cout<<ans<<endl;
}
}
Python3(3.5.2) 解法, 执行用时: 176ms, 内存消耗: 3364K, 提交时间: 2020-07-07 19:02:28
for i in range(int(input())):
n=int(input())
k=(n+1)//2
ans=0
for j in range(k):
ans+=(j*min(j,2*k-j-1))
print(ans*8)