Prosjecni

【題目摘要】
描述
Slavko很無聊，所以他把正整數(shù)填到N*N的方陣中。
如果他填出來的方陣滿足以下條件，他會特別高興：
●每行中的數(shù)字的平均值是一個位于同一行的整數(shù)。
●每列中的數(shù)字的平均值是一個位于同一列的整數(shù)。
●表中的所有數(shù)字都不同。
幫助Slavko找到一種會讓他開心的填法。
輸入
第一行輸入包含整數(shù)N（1≤N≤100）。表示方陣的行數(shù)和列數(shù)。
輸出
輸出N行，每行輸出N個由空格分隔的整數(shù)。令第i行中的第j個數(shù)字對應(yīng)于Slavko將在方陣的第i行第j列寫下的值。
所有數(shù)字必須大于0且小于109。
如果有多個解決方案，則輸出任意一個。
如果沒有任何解決方案，則輸出-1。
分數(shù)分布
無特殊分數(shù)分布。
樣例輸入1
3
樣例輸出1
1 2 3
4 5 6
7 8 9
樣例輸入2
2
樣例輸出2
-1
注意n=2時的特判

【思路+題解】

這種一看就知道不是平常套路的題
做事原則：多次試驗尋找普遍規(guī)律暴力打出較簡單的一組解

再玄學(xué)一波神推搞出規(guī)律（maybe not right）

剛開始我就發(fā)現(xiàn)n是奇數(shù)時直接1~n^2打成矩陣就是一組解了
但偶數(shù)的時候

在之后的評講當中我重見天日Ac方法見下：

先分類討論：

1）$n$為奇數(shù)：雖然已經(jīng)知道了結(jié)論我們也要嚴謹推理 讓我們花簇矩陣

申明：這是一個有規(guī)律的矩陣第$i$行與第$1$行一樣&&第$j$列和第$1$列一樣

接下來的證明就以第$1$行和第$1$列為例 如果你不信可以從頭證到尾俺比較懶

需要等差數(shù)列公式

行：$S=(1+n)?n/2$

平均數(shù)$=S/n=(1+n)?n/2/n=(1+n)/2$

$n$為奇數(shù)所以$n+1$一定是偶數(shù)

除以$2$一定為整&&$1\le X\le n$那么一定出現(xiàn)在這一行中

列：（行也可以這么證）

第一個加上最后一個$S1：1+1+(n?1)?n$

第二個加上倒數(shù)第二個$S2:n+1+(n?2)?n=S1$

…以此類推
$n$為奇數(shù)所以$(n+1)/2$就是正中間的數(shù)$x,x$的前一個等于$x?n$

$x$的后一個等于$x+n$兩個相加除以二就剛好等于$x$

結(jié)合上面所有的$S1，S2,S3$相等可知列的平均數(shù)也一定出現(xiàn)

2）$n$為偶數(shù) 花簇$n=4$的情況表

多畫幾組可以發(fā)現(xiàn)前$n?1$個都是連續(xù)的

容易發(fā)現(xiàn)$6=n?(n?1)/2$ 那么這一行的和$S=n?(n?1)$ 平均數(shù)就是$S/n=n?1$

第i行的規(guī)律均是如此 如果你不信可以從頭證到尾本仙女比較懶

因為行的規(guī)律出來了那么下一行打頭的這個數(shù)就可以隨意選擇，但為了方便，我們可以接
著上一行最后一列的數(shù)加一打頭，方便且不重復(fù)，真是太有心了

BUT唯一的bug就在最后一行的選擇上你如果把倒數(shù)第二行最后一列直接加$1$

你發(fā)現(xiàn)這一列就滿足不了題意，這個時候技巧就在于把行的規(guī)律照搬到列上去

而就在這個時候你驚奇地發(fā)現(xiàn)最后一行自動滿足題意了

我們以第一列和第二列為例證明（先不看最后一行）：

第二列每一個數(shù)都比第一列的數(shù)大$1$

按照上面行推出來的結(jié)論

自然而然第二列最后一行的數(shù)會比第一列最后一行的數(shù)大$1$

如此最后一行自然也滿足我們的行結(jié)論了

#include <cstdio> #define MAXN 100 int n, tot; int num[MAXN][MAXN]; int main() {scanf ( "%d", &n );if ( n == 2 ) return ! printf ( "-1" );if ( n % 2 ) {for ( int i = 1;i <= n;i ++ )for ( int j = 1;j <= n;j ++ )num[i][j] = ++ tot;}else {int sum;for ( int i = 1;i < n;i ++ ) {sum = 0;for ( int j = 1;j < n;j ++ ) {if ( j == 1 ) num[i][j] = num[i - 1][n] + 1;else num[i][j] = num[i][j - 1] + 1;sum += num[i][j];}num[i][n] = num[i][n - 1] * n - sum;}for ( int j = 1;j <= n;j ++ ) {sum = 0;for ( int i = 1;i < n;i ++ )sum += num[i][j];num[n][j] = num[n - 1][j] * n - sum;}}for ( int i = 1;i <= n;i ++ ) {for ( int j = 1;j < n;j ++ )printf ( "%d ", num[i][j] );printf ( "%d\n", num[i][n] );}return 0; }

又A一道，來嗨起來！！！

總結(jié)

以上是生活随笔為你收集整理的Prosjecni（构造）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。