Palindromic Matrix

题目链接http://codeforces.com/problemset/problem/1118/C
time limit per test:2 seconds

memory limit per test:256 megabytes

Let’s call some square matrix with integer values in its cells palindromic if it doesn’t change after the order of rows is reversed and it doesn’t change after the order of columns is reversed.

For example, the following matrices are palindromic:

题目大意：给你n²个数，让你判断是否能构成一个回文方阵（行的倒写和列的倒写都和原方阵一样），如果能输出YES后请你构造出这样的一个方阵，否则输出NO。
emmm。。。构造题一般是很伤脑筋的，我觉得他放到div3-C有点毒瘤，可以卡挺多人的。。。首先，判断它是否能构造成回文方阵，对于n为偶数来讲很简单，每个数都有必须是4的倍数，然后可以按行来构造，每次对于该数的个数-4，将其放入方阵与之对称的四个地方：

for (int i=1; i<=mac; i++)
	while (vis[i]) {
		if (cl>n/2) cl=1,num++;
		vis[i]-=4;
		mp[num][cl]=mp[num][n-cl+1]=mp[n-num+1][cl]=mp[n-num+1][n-cl+1]=i;
		cl++;
	}

然后偶数就over了。。。
但对于n为奇数来讲就很烦了，我就是奇数这里WA了两发。。。
首先对于n为奇数来讲，每个数的个数都应该是2的倍数，有且只有一个数不是。因为对于中间的十字来讲它只需上下对称或左右对称，即只有两个数也是可以的。所以第一次判断NO的方法就出来了：

for (int i=1; i<=mac; i++) {
	if (vis[i]%2) {
		mark++;
	}
}
if (mark!=1) {
	printf ("NO\n");
	return 0;
}

接下来就是对于方阵的构造了，和偶数的构造其实是差不多，只不过我们先将不是2的倍数的那个数填入方阵中心，然后将大于等于4的数填入非十字的区域，这样除了十字部分，其他地方都构造完成了，接下来就是对十字部分的填入，也是按层来，到了中间后按列来：

num=1,cl=n/2+1;
mak=0;
for (int i=1; i<=ex-1; i++) {
	while (vis[fork[i]]>=2) {
		if (num>n/2) {
			mak=1;
			break;
		}
		vis[fork[i]]-=2;
		mp[num][cl]=mp[n-num+1][cl]=fork[i];
		num++;
	}
	if (mak) break;
}
cl=1;
for (int i=1; i<=ex-1; i++) {
	while (vis[fork[i]]>=2) {
		vis[fork[i]]-=2;
		mp[num][cl]=mp[num][n-cl+1]=fork[i];
		cl++;
	}
}

这就是最终对十字部分的填入。
当然我们之前的判断NO是粗糙的，如果所有的数只有两个加上一个的话就GG了，所以当方阵构造完成时我们还需检查一遍方阵：

for (int i=1; i<=n; i++)
	for (int j=1; j<=n; j++)
		if (!mp[i][j]) {
			printf ("NO\n");
			return 0;
		}

然后本题就结束了，虽然想法很好，但实际上中间写的时候出现了很多bug，所以写起了就没有那么快了。。。
以下是详细代码：

#include <cstdio>
#define debug(n) printf ("%d",n)
int a[500],vis[1020],fork[1020];
int mp[30][30];
int main() {
	int n,mark=0,mac=0,num=1;
	scanf ("%d",&n);
	for (int i=1; i<=n*n; i++) {
		scanf ("%d",&a[i]);
		vis[a[i]]++;
		mac=(mac>a[i])?mac:a[i];
	}
	int cl=1,odd,p=0;
	if (!(n&1)) {
		for (int i=1; i<=n*n; i++) {
			if (vis[a[i]]%4) {
				printf ("NO\n");
				return 0;
			}
		}
		printf ("YES\n");
		for (int i=1; i<=mac; i++)
			while (vis[i]) {
				if (cl>n/2) cl=1,num++;
				vis[i]-=4;
				mp[num][cl]=mp[num][n-cl+1]=mp[n-num+1][cl]=mp[n-num+1][n-cl+1]=i;
				cl++;
			}
		for (int i=1; i<=n; i++)
			for (int j=1; j<=n; j++)
				if (j!=n) printf ("%d ",mp[i][j]);
				else printf ("%d\n",mp[i][j]);
	} 
	else {
		for (int i=1; i<=mac; i++) {
			if (vis[i]%2) {
				mark++;
				odd=i;
			}
		}
		if (mark!=1) {
			printf ("NO\n");
			return 0;
		}
		mp[n/2+1][n/2+1]=odd;
		vis[odd]--;
		int mak=0;
		for (int i=1; i<=mac; i++){
			while (vis[i]>=4) {
			    if (cl>n/2) cl=1,num++;
			    if (num>n/2) {
			    	mak=1;break;
				}
				vis[i]-=4;
				mp[num][cl]=mp[num][n-cl+1]=mp[n-num+1][cl]=mp[n-num+1][n-cl+1]=i;
				cl++;
			}
			if (mak) break;
	    }
		int ex=1;
		for (int i=1; i<=mac; i++) {
			if (vis[i]) fork[ex++]=i;
		}
		num=1,cl=n/2+1;
		mak=0;
		for (int i=1; i<=ex-1; i++){
			while (vis[fork[i]]>=2){
				if (num>n/2) {
					mak=1;break;
				}
				vis[fork[i]]-=2;
				mp[num][cl]=mp[n-num+1][cl]=fork[i];
				num++;
			}
			if (mak) break;
		}
		cl=1;
		for (int i=1; i<=ex-1; i++){
			while (vis[fork[i]]>=2){
				vis[fork[i]]-=2;
				mp[num][cl]=mp[num][n-cl+1]=fork[i];
				cl++;
			}
		}
		for (int i=1; i<=n; i++)
		 for (int j=1; j<=n; j++)
		   if (!mp[i][j]) {
		   	printf ("NO\n");
		   	return 0;
		   }
		printf ("YES\n");
		for (int i=1; i<=n; i++)
			for (int j=1; j<=n; j++)
				if (j!=n) printf ("%d ",mp[i][j]);
				else printf ("%d\n",mp[i][j]);
	}
	return 0;
}