【蓝桥杯】阿坤老师的魔方挑战

目录

1.题目

2.暴力

2.1 代码一

3.正解

3.1 画图分析

3.2 代码二

---

1.题目

样例输入

3
7 8 9
4 5 7
1 2 3

样例输出

16

2.暴力

毫无疑问，纯暴力超时了......

2.1 代码一

#include <iostream>
using namespace std;
const int N=250010;
int main()
{
  int n,a[N],t[500],temp,maxi=0,sum;
  cin>>n;
  //输入
  for(int i=0;i<n;i++){
    temp=n*i;
    for(int j=0;j<n;j++)
      cin>>a[temp+j];
  }
  sum=0;
  for(int i=0;i<n;i++)
    sum+=a[i*n+i];
  if(sum>maxi)maxi=sum;
 
  for(int i=0;i<n-1;i++){
    //保存第一行
    for(int k=0;k<n;k++){
      t[k]=a[k];
    }
    //行循环移动
    for(int k=0;k<n;k++){
      for(int p=0;p<n-1;p++){
        a[p*n+k]=a[(p+1)*n+k];
      }
    }
  //最后一行等于第一行
  for(int k=0;k<n;k++)
    a[(n-1)*n+k]=t[k];
  sum=0;
  for(int i=0;i<n;i++)
    sum+=a[i*n+i];
  if(sum>maxi)maxi=sum;
  }
 
 
  //循环移动，第一行移到最后一行，N*N行移动就只有N种，列移动就N种
  for(int i=0;i<n;i++){
    //保存第一列
    for(int k=0;k<n;k++){
      t[k]=a[k*n];
    }
    //列循环移动
    for(int k=0;k<n;k++){
      for(int p=0;p<n-1;p++){
        a[k*n+p]=a[k*n+p+1];
      }
    }
  //最后一列等于第一列
  for(int k=0;k<n;k++)
    a[k*n+n-1]=t[k];
 
  //
    for(int i=0;i<n-1;i++){
    //保存第一行
    for(int k=0;k<n;k++){
      t[k]=a[k];
    }
    //行循环移动
    for(int k=0;k<n;k++){
      for(int p=0;p<n-1;p++){
        a[p*n+k]=a[(p+1)*n+k];
      }
    }
  //最后一行等于第一行
  for(int k=0;k<n;k++)
    a[(n-1)*n+k]=t[k];
  sum=0;
  for(int i=0;i<n;i++)
    sum+=a[i*n+i];
  if(sum>maxi)maxi=sum;
  }
  }
 
  cout<<maxi;
  return 0;
}

3.正解

3.1 画图分析

由于是循环行or列，所以很多相对位置是固定的

看了图，有没有豁然开朗呢QvQ

3.2 代码二

这个我觉得是比较好理解的，实在看不懂草稿纸上模拟一下过程吧

#include <iostream>
using namespace std;
const int N=250010;
int main()
{
  int n,a[N],maxi=0,sum,temp;
  cin>>n;
  //输入
  for(int i=0;i<n;i++){
    temp=n*i;
    for(int j=0;j<n;j++)
      cin>>a[temp+j];
  }
  //遍历
  for(int l=0;l<n;l++){
    sum=0;
    for(int r=0;r<n;r++){
      int line=(l+r)%n;
      int row=r;
      sum+=a[line*n+row];
    }
    if(sum>maxi)maxi=sum;
  }
  cout<<maxi;
  return 0;
}