链接：https://www.nowcoder.com/acm/contest/93/B
来源：牛客网
题目描述
给你一个n*n矩阵，按照顺序填入1到n*n的数，例如n=5，该矩阵如下
|
1 |
2 |
3 |
4 |
5 |
|
6 |
7 |
8 |
9 |
10 |
|
11 |
12 |
13 |
14 |
15 |
|
16 |
17 |
18 |
19 |
20 |
|
21 |
22 |
23 |
24 |
25 |
现在让你连接相邻两条边的中点，然后只保留他们围成封闭图形区域的数字，那么这个矩阵变为
|
3 |
||||
|
7 |
8 |
9 |
||
|
11 |
12 |
13 |
14 |
15 |
|
17 |
18 |
19 |
||
|
23 |
现在你们涵哥让你求变化后的矩阵的所有元素的和为多少
输入描述:
输入第一行一个整数T(1<=T<=100)
接下来有T组测试数据，每组测试数据输入一个整数n(3<=n<=10000)
保证输入的n为奇数
输出描述:
对于每组测试数据，输出对应答案
示例1
输入
2
3
5
输出
25
169
【分析】：不能数组存然后一行行相加，数组存不下会MLE。。。
#include<bits/stdc++.h> using namespace std; #define ll long long
#define N 10005
int a[N][N], sum;
int main()
{
int t;
int n;
cin>>t;
while(t--)
{
sum = ;
int tot = ;
cin >> n;
for(int i = ; i<=n; i++){
for(int j=; j<=n; j++){
a[i][j] = tot++;
}
}
int mid = n / + ; // 4列
//3~5 2~6(mid-- n-mid+1)
for(int i=; i<=n; i++){
int t = mid;
for(int j=; j<=n; j++){
if(j<t || j>n-t+){
a[i][j] = ;
}
}
if(i<=mid) mid--;
else mid++;
}
/*
for(int i = 1; i<=n; i++){
for(int j=1; j<=n; j++){
printf("%2d ",a[i][j]);
}
cout<<endl;
}
*/
for(int i = ; i<=n; i++){
for(int j=; j<=n; j++){
sum += a[i][j];
}
}
cout<<sum<<endl;
}
}
/* 1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31 32 33 34 35
36 37 38 39 40 41 42
43 44 45 46 47 48 49 */
MLE代码
后来尝试打表，把3~10000的输入再文件流输出答案，这下空间复杂度10000 时间O(1)总行了吧？然而更惨直接WA，不知道什么毛病
#include<bits/stdc++.h> using namespace std; #define ll long long
#define N 10005
ll a[N][N];
ll sum;
ll ans[]={,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,};
int main()
{
int t;
int n;
cin>>t;
while(t--)
{
cin>>n;//3-2=1 5-3=2
cout<<ans[(n-)/-]<<endl;
}
return ;
}
WA
最后找规律过的，发现对称位置总是在1~mid递增后mid~n递减。。。很惨很菜
#include<bits/stdc++.h> using namespace std;
#define ll long long
#define N 10005 int t;
int n;
int main()
{
cin>>t;
while(t--)
{
ll sum = , j = ;
cin>>n;
ll mid = (n+)/;
ll m = mid;
for(ll i=; i<=mid; i++)
{
sum += m*( * j + );
j++;
m += n;
}
j-=;
for(ll i=mid+; i<=n; i++)
{
sum += m*( * j + );
j--;
m += n;
}
cout<<sum<<endl;
}
}
找规律
【总结】：这种空间复杂度很大，涉及矩阵的SB题目似乎找规律是很司空见惯的事情，上次EOJ的蛇形矩阵也是找规律，被我模拟一下也挂了，18蓝桥杯那个螺旋矩阵也tm是找规律，上次的HDU幻方也是找规律。。。真实的哭了，以后看到矩阵我先找规律在考虑模拟满意了吗