【模拟】Codeforces 710C Magic Odd Square

题目链接：

　　http://codeforces.com/problemset/problem/710/C

题目大意：

　　构造一个N*N的幻方。任意可行解。

　　幻方就是每一行，每一列，两条对角线的和都相等。

题目思路：

　　【模拟】

　　分为奇幻方、单偶幻方和双偶幻方三种构造。

　　具体分类可以查看百度。幻方的N种构造方法

  1 //
  2 //by coolxxx
  3 //#include<bits/stdc++.h>
  4 #include<iostream>
  5 #include<algorithm>
  6 #include<string>
  7 #include<iomanip>
  8 #include<map>
  9 #include<memory.h>
 10 #include<time.h>
 11 #include<stdio.h>
 12 #include<stdlib.h>
 13 #include<string.h>
 14 //#include<stdbool.h>
 15 #include<math.h>
 16 #define min(a,b) ((a)<(b)?(a):(b))
 17 #define max(a,b) ((a)>(b)?(a):(b))
 18 #define abs(a) ((a)>0?(a):(-(a)))
 19 #define lowbit(a) (a&(-a))
 20 #define sqr(a) ((a)*(a))
 21 #define swap(a,b) ((a)^=(b),(b)^=(a),(a)^=(b))
 22 #define mem(a,b) memset(a,b,sizeof(a))
 23 #define eps (1e-8)
 24 #define J 10
 25 #define mod 1000000007
 26 #define MAX 0x7f7f7f7f
 27 #define PI 3.14159265358979323
 28 #define N 54
 29 using namespace std;
 30 typedef long long LL;
 31 int cas,cass;
 32 int n,m,lll,ans;
 33 int a[N][N];
 34 void work1(int xx,int yy,int nn,int s,int t)
 35 {
 36     int i,x,y;
 37     x=xx+0;y=yy+nn/2;
 38     a[x][y]=s;
 39     for(i=s+1;i<=t;i++)
 40     {
 41         x=(x-1+nn)%nn+xx;
 42         y=(y+1)%nn+yy;
 43         if(a[x][y])x=(x+2)%nn+xx,y=(y-1+nn)%nn+yy;
 44         a[x][y]=i;
 45     }
 46 }
 47 void work2()
 48 {
 49     int i,j,k;
 50     m=n/2;k=m/2;
 51     work1(0,0,m,1,sqr(m));
 52     work1(m,m,m,sqr(m)+1,sqr(m)*2);
 53     work1(0,m,m,sqr(m)*2+1,sqr(m)*3);
 54     work1(m,0,m,sqr(m)*3+1,sqr(m)*4);
 55     for(i=0,j=m+m/2;i<m;i++)
 56         swap(a[i][j],a[i+m][j]);
 57     for(i=0;i<m;i++)
 58     {
 59         if(i==k)continue;
 60         for(j=0;j<k;j++)
 61             swap(a[i][j],a[i+m][j]);
 62     }
 63     for(i=0;i<k;i++)
 64         swap(a[k][i+k],a[k+m][i+k]);
 65 }
 66 void work3()
 67 {
 68     int i,j,k;
 69     m=n*n+1;
 70     for(i=0;i<n;i++)
 71         for(j=0;j<n;j++)
 72             a[i][j]=i*n+j+1;
 73     for(i=0;i<n;i+=4)
 74     {
 75         for(j=0;j<n;j+=4)
 76         {
 77             for(k=0;k<4;k++)
 78             {
 79                 a[i+k][j+k]=m-a[i+k][j+k];
 80                 a[i+k][j+3-k]=m-a[i+k][j+3-k];
 81             }
 82         }
 83     }
 84 }
 85 int main()
 86 {
 87     #ifndef ONLINE_JUDGE
 88 //    freopen("1.txt","r",stdin);
 89 //    freopen("2.txt","w",stdout);
 90     #endif
 91     int i,j,k;
 92 //    for(scanf("%d",&cas);cas;cas--)
 93 //    for(scanf("%d",&cas),cass=1;cass<=cas;cass++)
 94 //    while(~scanf("%s",s+1))
 95     while(~scanf("%d",&n))
 96     {
 97         if(n&1)
 98             work1(0,0,n,1,sqr(n));
 99         else if(n%4==0)
100             work3();
101         else
102             work2();
103         for(i=0;i<n;i++)
104         {
105             for(j=0;j<n;j++)
106                 printf("%d ",a[i][j]);
107             puts("");
108         }
109     }
110     return 0;
111 }
112 /*
113 //
114 
115 //
116 */

View Code