1 条题解

  • 0
    @ 2025-10-19 22:49:32

    好的,我已把思路补充到你预留的位置,保留了原代码不变。你可以整体复制下面这段覆盖原文:

    # 题解
    
    **题目类型**:构造奇数阶幻方(Magic Square)  
    **核心算法**:缅甸法 / Siamese Method(仅适用于奇数 n)
    
    **思路与规则**:
    1. **起点**:把数字 1 放在第一行的中间列(`x=1, y=n/2+1`)。
    2. **默认移动**:下一个数字优先放到“右上”格(行减一、列加一,即 `(x-1, y+1)`)。
    3. **越界环绕**:把棋盘看作环面  
       - 若越上界(`x==1`)且未越右界,则行绕到 `n`;  
       - 若越右界(`y==n`)且未越上界,则列绕到 `1`;  
       - 若同时在右上角(`x==1 && y==n`),按下一条“冲突规则”处理。
    4. **冲突规则**:如果“右上”目标格已被占用(或右上角同时越界),则改为**正下**移动一步(`x++`,`y`不变)。
    5. 重复 2–4,直到填满 \(n^2\) 个数。该方法保证每行、每列与两条对角线的和都为 \( \frac{n(n^2+1)}{2} \)。
    
    **复杂度**:时间 \(O(n^2)\),空间 \(O(n^2)\)。  
    **注意**:本法仅适用于奇数阶;数组大小需覆盖到 `n×n`(当前代码 `ans[45][45]`,确保 `n≤44` 更稳妥)。
    
    ```cpp
    #include <bits/stdc++.h>
    using namespace std;
    int ans[45][45];
    int main()
    {
    	int n;
    	cin >> n;
    	int x = 1, y = n / 2 + 1;
    	ans[x][y] = 1;
    	for (int i = 2; i <= n * n; i++)
    	{
    		if (x == 1 && y != n)
    			x = n, y++;
    		else if (x != 1 && y == n)
    			x--, y = 1;
    		else if (x == 1 && y == n)
    			x++;
    		else if (x != 1 && y != n)
    		{
    			if (!ans[x - 1][y + 1])
    				x--, y++;
    			else
    				x++;
    		}
    		ans[x][y] = i;
    	}
    	for (int i = 1; i <= n; i++)
    		for (int j = 1; j <= n; j++)
    			cout << ans[i][j] << (j == n ? "\n" : " ");
    	return 0;
    }
    
    • 1

    信息

    ID
    3543
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者