题解：P14133 【MX-X22-T4】「TPOI-4D」Another Matrix Problem

通过构造，无需任何算法就能解决这道题

本题解给出了较为严谨的证明

通过题目，我们可以得知要把

1

n^2

的所有数分成黑白两个部分，两个部分的差最小。我们分 n 为奇数和偶数来考虑。

n为偶数时，显而易见，两个偶数相乘一定是4的倍数，所以数字数量就是 4 的倍数。那就把

1

n^2

每4个分为一组，这里就用

a

，

a+1

，

a+2

，

a+3

来表示吧。把

a+1

和

a+2

放在一个部分，

a

和

a+3

放在一个部分，这样就能保证两部分的和永远相同，差直接输出0就行了。

至于 n 为奇数时，把 1 去掉，只看

2

n

，数字的数量就变成

n^2-1

，拆成

(n+1)\times(n-1)

，这样就是两个偶数相乘，依然是4的倍数，就可以用上述偶数的构造法，最后随便找一组加上1就行了，差值最小为 1。

然后就到了构造矩阵的这一步。双层 for 循环，判断行数加列数为奇偶即可。但这样还有一个问题，题目要求的是每行递增输出。解决方法很简单，一列一列的去构造，后一列的永远比前一列大，这样就完美解决了！

AC code

CPP

#include <bits/stdc++.h>
using namespace std;
int n;
int a[2005][2005],h[4000005],b[4000005];
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin >> n;
	n*= n;
	if(n % 2 == 0){
		for(int i = 1;i <= n/4;i++){
			h[i*2-1] = i*4-3;
			b[i*2-1] = i*4-2;
			b[i*2] = i*4-1;
			h[i*2] = i*4;
		}
		cout << 0 << endl;
	}
	else{
		h[1] = 1;
		for(int i = 1;i <= n/4;i++){
			h[i*2] = i*4-2;
			b[i*2-1] = i*4-1;
			b[i*2] = i*4;
			h[i*2+1] = i*4+1;
		}
		cout << 1 << endl;
	}
	int hi = 0,bi = 0;
	n = sqrt(n);
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= n;j++){
			if((i+j) %2 == 0){
				hi++;
				a[j][i] = h[hi];
			}
			else{
				bi++;
				a[j][i] = b[bi];
			}
		}
	}
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= n;j++) cout << a[i][j] << " ";
		cout << endl;
	}
	return 0;
}

题解：P14133 【MX-X22-T4】「TPOI-4D」Another Matrix Problem

文章操作

通过构造，无需任何算法就能解决这道题

AC code

相关推荐

评论

题解：P14133 【MX-X22-T4】「TPOI-4D」Another Matrix Problem