「题解」[COCI2016-2017#2] Prosječni

· · 题解

为了填入的数尽可能小，不妨令第一行的前 n-1 个数为 1,2,3,\dots,n-1。

若要使第一行的平均数为其倒数第二个数，则第一行的最后一个数为 \frac{(n-1)n}{2}。

将第一行的每个数加上 \frac{(n-1)n}{2}，即可得到第二行。

不难证明，第二行的平均数也是其倒数第二个数。

类似地，可以得到矩阵的前 n-1 行。

若要使第一列的平均数为其倒数第二个数，则第一列的最后一个数为1+\frac{(n-2)(n-1)n(n+1)}{4}。

类似地，可以得到最后一行的后 n-1 个数。

不难证明，最后一行的平均数也是其倒数第二个数。

最终的矩阵如下：

1 2 3 \cdots n-1 \frac{(n-1)n}{2}
1+1\times\frac{(n-1)n}{2} 2+1\times\frac{(n-1)n}{2} 3+1\times\frac{(n-1)n}{2} \cdots n-1+1\times\frac{(n-1)n}{2} \frac{(n-1)n}{2}+1\times\frac{(n-1)n}{2}
1+2\times\frac{(n-1)n}{2} 2+2\times\frac{(n-1)n}{2} 3+2\times\frac{(n-1)n}{2} \cdots n-1+2\times\frac{(n-1)n}{2} \frac{(n-1)n}{2}+2\times\frac{(n-1)n}{2}
\vdots \vdots \vdots \ddots \vdots \vdots
1+(n-2)\times\frac{(n-1)n}{2} 2+(n-2)\times\frac{(n-1)n}{2} 3+(n-2)\times\frac{(n-1)n}{2} \cdots n-1+(n-2)\times\frac{(n-1)n}{2} \frac{(n-1)n}{2}+(n-2)\times\frac{(n-1)n}{2}
1+\frac{(n-2)(n-1)n(n+1)}{4} 2+\frac{(n-2)(n-1)n(n+1)}{4} 3+\frac{(n-2)(n-1)n(n+1)}{4} \cdots n-1+\frac{(n-2)(n-1)n(n+1)}{4} \frac{(n-1)n}{2}+\frac{(n-2)(n-1)n(n+1)}{4}

这个矩阵中是否存在相同的数？

不难发现，第 $2,3,\dots,n-1$ 行的第一个数均大于上一行的最后一个数。 $1+\frac{(n-2)(n-1)n(n+1)}{4}>\frac{(n-1)n}{2}+(n-2)\times\frac{(n-1)n}{2}$ 在 $n\ge 3$ 时恒成立。那么，第 $n$ 行的第一个数也大于上一行的最后一个数。 所以，矩阵中不存在相同的数。 当 $n$ 取最大值 $100$ 时，矩阵中的最大数 $\frac{(n-1)n}{2}+\frac{(n-2)(n-1)n(n+1)}{4}=24502500\le 10^9$。也满足要求。 ------------ 参考代码： ``` #include<cstdio> int main(){ int n; scanf("%d",&n); if(n==1){ puts("1"); return 0; } if(n==2){ puts("-1"); return 0; } int k1=(n-1)*n/2,k2=(n-2)*(n-1)*n*(n+1)/4; for(int i=1;i<n;++i){ for(int j=1;j<n;++j){ printf("%d ",j+(i-1)*k1); } printf("%d\n",i*k1); } for(int j=1;j<n;++j){ printf("%d ",j+k2); } printf("%d\n",k1+k2); return 0; } ```