AtCoder Beginner Contest竞赛题解 | 洛谷 AT_abc436_b Magic Square

​欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！

专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。

适合人群：

• 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
• 希望系统学习C++/Python编程的初学者
• 想要提升算法与编程能力的编程爱好者

附上汇总帖：AtCoder Beginner Contest竞赛题解 | 汇总

【题目来源】

洛谷：[AT_abc436_b ABC436B] Magic Square - 洛谷

【题目描述】

You are given an odd number $ N $ that is at least $ 3 $ .
给定一个至少为3 33的奇数N NN。

There is a grid with $ N $ rows and $ N $ columns, where all cells are initially empty. Now, you will write integers in each cell of this grid according to the following procedure. Let $ (i,j) $ denote the cell at the $ (i+1) $ -th row from the top and $ (j+1) $ -th column from the left ( $ 0\leq i<N, 0\leq j<N $ ).
有一个N NN行N NN列的网格，其中所有单元格初始为空。现在，你将按照以下步骤在该网格的每个单元格中写入整数。用( i , j ) (i, j)(i,j)表示从上往下第( i + 1 ) (i+1)(i+1)行、从左往右第( j + 1 ) (j+1)(j+1)列的单元格 （0 ≤ i < N , 0 ≤ j < N 0\leq i<N, 0\leq j<N0≤i<N,0≤j<N）。

1. Write $ 1 $ in cell $ (0,\frac{N-1}{2}) $ .
   在单元格( 0 , N − 1 2 ) (0,\frac{N-1}{2})(0,2N−1​)中写入1 11。

2. Repeat the following operation $ N^2-1 $ times:
   重复以下操作N 2 − 1 N^2-1N2−1次：

   • Let $ (r,c) $ be the cell where an integer was written last time, and $ k $ be the integer written. If cell $ ((r-1) \bmod N, (c+1) \bmod N) $ is empty, write $ k+1 $ in that cell; otherwise, write $ k+1 $ in cell $ ((r+1) \bmod N,c) $ . Here, $ x \bmod N $ denotes the remainder when $ x $ is divided by $ N $ .
     令( r , c ) (r, c)(r,c)表示上次写入整数的单元格，k kk表示写入的整数。若单元格( ( r − 1 ) m o d N , ( c + 1 ) m o d N ) ((r-1) \bmod N, (c+1) \bmod N)((r−1)modN,(c+1)modN)为空，则在该单元格中写入k + 1 k+1k+1；否则，在单元格( ( r + 1 ) m o d N , c ) ((r+1) \bmod N,c)((r+1)modN,c)中写入k + 1 k+1k+1。此处，x m o d N x \bmod NxmodN表示x xx除以N NN的余数。

Find the integer that will be written in each cell in this procedure. It can be proved that each cell will have an integer written in it exactly once.
求在此过程中每个单元格将被写入的整数。可以证明，每个单元格中将被写入恰好一个整数。

【输入】

The input is given from Standard Input in the following format:

$ N $

【输出】

Let $ a_{i,j} $ be the integer written in cell $ (i,j) $ , and print it in the following format:

$ a_{0,0} $ $ a_{0,1} $ $ \dots $ $ a_{0,N-1} $ $ \vdots $ $ a_{N-1,0} $ $ a_{N-1,1} $ $ \dots $ $ a_{N-1,N-1} $

【输入样例】

3

【输出样例】

8 1 6 3 5 7 4 9 2

【算法标签】

《洛谷 AT_abc436_b Magic Square》 #模拟# #枚举#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=105;// 最大矩阵大小intn;// 幻方大小（奇数）inta[N][N];// 幻方矩阵intmain(){// 输入幻方大小n（应为奇数）cin>>n;// 1. 初始化：将1放在第一行的中间列a[0][(n-1)/2]=1;intk=1;// 当前已放置的数字// 当前位置：i行，j列inti=0,j=(n-1)/2;// 2. 放置剩余的n*n-1个数字while(k<=n*n-1){// 计算右上角的位置（循环处理）intnext_i=(i-1+n)%n;// 上一行intnext_j=(j+1)%n;// 右一列// 如果右上角位置为空if(a[next_i][next_j]==0){// 将下一个数字放在右上角a[next_i][next_j]=k+1;// 更新当前位置i=next_i;j=next_j;}else{// 如果右上角被占用，放在正下方a[(i+1)%n][j]=k+1;// 更新当前位置i=(i+1)%n;// 下一行j=j;// 同一列}k++;// 已放置数字数量加1// 调试输出// cout << "i j " << i << " " << j << endl;}// 3. 输出幻方for(inti=0;i<n;i++){for(intj=0;j<n;j++){cout<<a[i][j]<<" ";}cout<<endl;}return0;}

【运行结果】

3 8 1 6 3 5 7 4 9 2