题目链接：
https://acm.ecnu.edu.cn/problem/3536/
题目大意：
求蛇形矩阵的每一行的和，数据范围n<=200000。
思路：
由于n数据较大，所以感觉应该是需要找规律。
先附上蛇形矩阵的打表代码，先输出数据较小的蛇形矩阵，观察规律。
#include <iostream>
#include <malloc.h>
using namespace std;
int arr[][];
int startNum=;
void DrawCircle(int len,int n);
int main(){
int i,j,k,n,len;
cout<<"请输入蛇形矩阵阶数n\nn=";
cin>>n;
len=n;
if(n%!=){
while(len>){
DrawCircle(len,n);
len=len-;
}
arr[n/+][n/+]=n*n;
}
else{
while(len>){
DrawCircle(len,n);
len=len-;
}
}
cout<<"对应的蛇形矩阵如下"<<endl;
for(i=;i<=n;i++){
for(j=;j<=n;j++){
cout<<arr[i][j];
if(j<n){
if(arr[i][j]>=)
cout<<" ";
else
cout<<" ";
}
else
cout<<endl;
}
}
for(int i = ; i <= n; i++)
{
int tot = ;
for(int j = ; j <= n; j++)tot += arr[i][j];
cout<<tot<<endl;
}
return ;
}
void DrawCircle(int len,int n){
int i,number,row,col;
number=(n-len)/+;//当前画的是第几个圈
row=number;col=number;
for(i=;i<=len;i++){
arr[row][col]=startNum++;
col++;
}
col--;//for循环要跳出时候，列数多加了一次，这个地方减掉
for(i=;i<=len-;i++){
row++;
arr[row][col]=startNum++;
}
for(i=;i<=len-;i++){
col--;
arr[row][col]=startNum++;
}
for(i=;i<=len-;i++){
row--;
arr[row][col]=startNum++;
}
}
举个例子，先观察n = 9的时候。
对应的蛇形矩阵如下
1 2 3 4 5 6 7 8 9
32 33 34 35 36 37 38 39 10
31 56 57 58 59 60 61 40 11
30 55 72 73 74 75 62 41 12
29 54 71 80 81 76 63 42 13
28 53 70 79 78 77 64 43 14
27 52 69 68 67 66 65 44 15
26 51 50 49 48 47 46 45 16
25 24 23 22 21 20 19 18 17
第一行的和是S1 = 9*10/2=45。
第二行前8位比第一行多，第9位多1，S2 = 31*+1+S1=294
第三行第2位到第7位比第二行多， 第1位少1，后1位多1正好抵消，第8位多1，所以S3 = 23*+1+S2=433
第四行第3位到第6位比第三行多， 前2位少1，后2位多1正好抵消，第7位多1，所以S4 = 15*+1+S3=494
第五行第4位到第5位比第三行多， 前3位少1，后3位多1正好抵消，第6位多1，所以S5 = 7*+1+S4=509
这是上面的前半部分的规律，从a = 4 * n - 5（4*9-5=31）, b = n - 1（9-1=8）开始，a依次减，b依次减
第六行比第五行前4位少1， 后4位多1，中间位少，S6 = S5-1*3=506
第七行比第六行前3位少1， 后3位多1，中间位少， S7 = S6 - 3*11=473
第八行比第七行前2位少1， 后2位多1，中间位少， S8 = S7 - 5*19=378
第九行比第八行前1位少1， 后1位多1，中间位少， S9 = S8 - 7*27=189
后半部分的规律是从a = 3, b = 1开始，a依次加8， b依次加2
以上是n为奇数的规律，偶数的规律也类似：
以n = 6为例：
对应的蛇形矩阵如下
1 2 3 4 5 6
20 21 22 23 24 7
19 32 33 34 25 8
18 31 36 35 26 9
17 30 29 28 27 10
16 15 14 13 12 11
前三行的规律和上面一样，
S1 = 6 * 7 / 2 = 21
S2 = * + 1 + S1=117
S3 = * + 1 + S2=151
后三行的规律是
S4 = S3 + 4
S5 = S4 - *
S6 = S5 - *
多找几组偶数会发现每次都是这样的规律，后半部分的第一行 = 前半部分的最后一行 + 4，然后的规律都是依次减去a*b,a最开始为2，b最开始为7,之后依次a+=2，b+=8.
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
#include<set>
#include<queue>
#include<map>
#include<stack>
#include<vector>
#include<list>
#include<deque>
#include<sstream>
#include<cctype>
#define REP(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, s, t) for(int i = (s); i < (t); i++)
#define MEM(a, x) memset(a, x, sizeof(a));
#define DEBUG(x) cout<<x<<endl;
#define DBG cout<<"----------------"<<endl;
#define mid(x, y) x + (y - x)/ 2
#define lc o<<1
#define rc o<<1|1
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> Pair;
const int maxn = 1e6 + ;
const double eps = 1e-;
const int INF = 1e9;
const int dir[][] = {,,,,,-,-,};
const double pi = 3.1415926535898;
ll T, n, m, cases;
int main()
{
std::ios::sync_with_stdio(false);
cin >> n;
if(n & )//奇数的时候
{
ll a1 = (n + ) * n / ;//求出第一行
cout<<a1<<endl;
ll a = * n - , b = n - ;//a,b初始值
int i;
for(i = ; i <= (n + ) / ; i++)//前半部分输出
{
a1 = a1 + + a * b;
a -= ;
b -= ;
cout<<a1<<endl;
}
a = , b = ;
for(;i <= n; i++)//后半部分输出
{
a1 = a1 - a * b;
cout<<a1<<endl;
a += ;
b += ;
}
}
else//n为偶数
{
ll a1 = (n + ) * n / ;//输出第一个
cout<<a1<<endl;
ll a = * n - , b = n - ;
int i;
for(i = ; i <= (n + ) / ; i++)//前半部分和之前一样的规律
{
a1 = a1 + + a * b;
a -= ;
b -= ;
cout<<a1<<endl;
}
a1 += ;
cout<<a1<<endl;//中间的特殊规律
a = , b = ;
i++;//这里i++保证输出正好n行
for(;i <= n; i++)//后半部分输出
{
a1 = a1 - a * b;
a += ;
b += ;
cout<<a1<<endl;
}
}
return ;
}
注意坑点：最好所有的变量设成long long,如果n是int的话，计算a1 = (n + 1) * n / 2;的时候会溢出，导致出错。