网站开发iis怎么配置,岳阳汨罗网站建设,百度指数大数据,郑州市网站建设[COCI2016-2017#2] Prosječni 解题记录 题意简述
构造一个 n n n \times n nn 的矩阵#xff0c;使得每一行/列的平均都在这一行/列当中#xff0c;并且矩阵内各个数字不相同。 题目分析
观察样例就可以轻松发现#xff1a;当 n n n 为奇数时#xff0c;矩阵内的各个…[COCI2016-2017#2] Prosječni 解题记录 题意简述
构造一个 n × n n \times n n×n 的矩阵使得每一行/列的平均都在这一行/列当中并且矩阵内各个数字不相同。 题目分析
观察样例就可以轻松发现当 n n n 为奇数时矩阵内的各个元素就是 1 ∼ n 1 \sim n 1∼n 的按顺序排列。 证明
对于每一行公差为 1 1 1设每一行第一个数为 x x x第 k k k 项为 x ( k − 1 ) x(k-1) x(k−1) 其中 1 ≤ k ≤ n 1 \leq k \leq n 1≤k≤n那么这一行的和就是 ( x x n − 1 ) × n 2 \frac{(xxn-1)\times n}{2} 2(xxn−1)×n平均数是 x x n − 1 2 x ( n − 1 ) 2 \frac{xxn-1}{2}x\frac{(n-1)}{2} 2xxn−1x2(n−1)。因为 n n n 是奇数所以 n − 1 2 \frac{n-1}{2} 2n−1 是整数且 1 ≤ n − 1 2 ≤ n 1 \leq \frac{n-1}{2} \leq n 1≤2n−1≤n。每一列同理。 证毕。 如果 n n n 为偶数我们以同样的方式构造每一行的平均数同样为 x ( n − 1 ) 2 \frac{x(n-1)}{2} 2x(n−1)但是这个时候它是小数我们只需要对这个矩阵的每一项都 × 2 \times 2 ×2这样平均数就变成了 x ( n − 1 ) x(n-1) x(n−1) 这个整数。但是它也是一个奇数怎么办呢因为我们构造的矩阵公差相同所以和平均数最相近的两个数肯定是中间的为了使和不变我们可以将每一行的第 n ÷ 2 n\div2 n÷2 项 1 1 1同时将第 n ÷ 2 1 n \div 21 n÷21 项 − 1 -1 −1那么每一行就构造完成了这里也说明了只有 n 2 n2 n2 的时候才无解。 接下来考虑每一列只需要将最后一行加上 n 2 n^2 n2 即可满足条件。 证明对于每一列公差为 2 n 2n 2n设每一列第一个数为 x x x第 k k k 项就为 x ( k − 1 ) × 2 n x(k-1)\times 2n x(k−1)×2n 其中 1 ≤ k ≤ n 1 \leq k \leq n 1≤k≤n那么这一列的和就是 [ x x ( n − 1 ) × 2 n ] × n 2 \frac{[xx(n-1) \times 2n]\times n}{2} 2[xx(n−1)×2n]×n平均数是 x x ( n − 1 ) × 2 n 2 x n ( n − 1 ) x n − 1 2 × 2 n \frac{xx(n-1) \times 2n}{2}xn(n-1)x\frac{n-1}{2} \times 2n 2xx(n−1)×2nxn(n−1)x2n−1×2n。因为 n n n 是偶数所以 n − 1 2 \frac{n-1}{2} 2n−1 不是整数但是 n 2 \frac{n}{2} 2n 是所以考虑将每列的最后一项加上 n 2 n^2 n2等价于将每一项加上 n n n平均数也加上 n n n变为 x n 2 × 2 n x\frac{n}{2} \times 2n x2n×2n其中 1 ≤ n 2 ≤ n 1\leq \frac{n}{2} \leq n 1≤2n≤n。 证毕。 AC Code
#includebits/stdc.h
#define arrout(a,n) rep(i,1,n)std::couta[i]
#define arrin(a,n) rep(i,1,n)std::cina[i]
#define rep(i,x,n) for(int ix;in;i)
#define dep(i,x,n) for(int ix;in;i--)
#define erg(i,x) for(int ihead[x];i;ie[i].nex)
#define dbg(x) std::cout#x:x
#define mem(a,x) memset(a,x,sizeof a)
#define all(x) x.begin(),x.end()
#define arrall(a,n) a1,a1n
#define PII std::pairint,int
#define m_p std::make_pair
#define u_b upper_bound
#define l_b lower_bound
#define p_b push_back
#define CD const double
#define CI const int
#define int long long
#define il inline
#define ss second
#define ff first
#define itn int
CI N105;
int n,a[N][N];
signed main() {std::cinn;if(n2) {puts(-1);exit(0);}int k0;rep(i,1,n) {rep(j,1,n) {a[i][j]k;}}if(n1) {rep(i,1,n) {rep(j,1,n) {std::couta[i][j] ;}puts();}} else {rep(i,1,n) {rep(j,1,n) {a[i][j]*2;}}rep(i,1,n) {a[i][n/2];a[i][n/2-1]--;}rep(i,1,n) {a[n][i]n*n;}rep(i,1,n) {rep(j,1,n) {std::couta[i][j] ;}puts();}}return 0;
}
