Codeforces Problem 710C Magic Odd Square

Accept: 0 Submit: 0
Time Limit: 1 second Memory Limit : 256 megabytes

Problem Description

Find an n?×?n matrix with different numbers from 1 to n^2, so the sum in each row, column and both main diagonals are odd.

Input

The only line contains odd integer n (1?≤?n?≤?49).

Output

Print n lines with n integers. All the integers should be different and from 1 to n^2. The sum in each row, column and both main diagonals should be odd.

Sample Input

   1 
   
 3

Sample Output

Hint

Problem Idea

解题思路:

【题意】
将1~这个数填入n*n的矩阵中,使得每行每列以及主对角线的数之和为奇数

输出符合条件的n*n的矩阵

【类型】
乱搞题

【分析】

在解决这题之前,我们要搞清楚的是:

奇数+奇数=偶数

偶数+奇数=奇数

偶数+偶数=偶数

奇数×奇数=奇数

奇数×偶数=偶数

偶数×偶数=偶数

所以1~中奇数个数恰好比偶数个数多1个

又因为,偶数+奇数=奇数 => 奇数+奇数=偶数偶数+偶数=偶数 n为奇数

所以每行每列以及主对角线,只要确保有1个奇数不成对,其他的都是成对的(奇数和奇数或偶数和偶数),那么就能保证这行或这列或主对角线的数之和为奇数.观察以下7*7的矩阵

我们可以看出,红色部分有2*(1+3+5)+7=25个格子,白色部分有4*(1+2+3)=24个格子

红色部分恰好比白色部分多一个格子(1~中奇数个数恰好比偶数个数多一个)

红色部分中每行每列以及主对角线恰好都有奇数个格子(奇数×奇数=奇数,偶数×偶数=偶数,奇数+偶数=奇数)

所以,我们只需在红色部分填入奇数,白色部分填入偶数,就可以使得每行每列以及主对角线上的数之和为奇数

如上图,剩下空位用偶数补上即可

【时间复杂度&&优化】
O(n^2)

题目链接→Codeforces Problem 710C Magic Odd Square

Source Code

/*Sherlock and Watson and Adler*/
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<bitset>
#include<cmath>
#include<complex>
#include<string>
#include<algorithm>
#include<iostream>
#define eps 1e-9
#define LL long long
#define PI acos(-1.0)
#define bitnum(a) __builtin_popcount(a)
using namespace std;
const int N = 50;
const int M = 100005;
const int inf = 1000000007;
const int mod = 1000000007;
int ans[N][N];
int main()
{int n,i,j,p=1;scanf("%d",&n);for(i=1;i<=n/2;i++)for(j=n/2+2-i;j<=n-n/2-1+i;j++)ans[i][j]=p,p+=2;for(;i<=n;i++)for(j=i-n/2;j<=n-i+n/2+1;j++)ans[i][j]=p,p+=2;for(p=2,i=1;i<=n;i++)for(j=1;j<=n;j++)if(ans[i][j])printf("%d%c",ans[i][j],j!=n?' ':'\n');elseprintf("%d%c",p,j!=n?' ':'\n'),p+=2;return 0;
}

菜鸟成长记