首页 > 代码库 > Codeforces 711B. Chris and Magic Square
Codeforces 711B. Chris and Magic Square
题目链接:http://codeforces.com/problemset/problem/711/B
题意:
给你一个n * n 的矩阵, 其中除了含有一个 ”0“ 以外, 都是正整数, 问你是否存在一个大于 0 的数, 使得这个数取代 ”0“ 的位置后, 这个矩阵每行, 每列, 主副对角线上的数加起来全部都相等.
思路：
把这个矩阵的每行每列还有主副对角线的数全部加起来存在一个sum数组里,且这个数组应该有 n * 2 + 2 个数, 排序后分情况讨论:
情况1:如果这个 ”0“ 既在主对角线上也在副对角线上, 那么排序后前4个数应该相等,其余的 (n * 2 + 2) - 4 个数也必须全部相等.
情况2:如果这个 ”0“ 在主对角线和副对角线其中一个上, 那么排序后前3个数应该相等,其余的 (n * 2 + 2) - 3 个数也必须全部相等.
情况3:如果这个 ”0“ 不在对角线上, 那么排序后前2个数应该相等,其余的 (n * 2 + 2) - 2 个数也必须全部相等.
这里需要特判一下 n = 1 的时候, 不应该输出 0, 随便输出一个正整数即可.还有种情况就是给的矩阵已经满足条件,即行, 列, 对角线加起来全部相等, 说明本身的 ”0“ 已经满足情况, 这时不存在一个正整数去替代这个 ”0“.
代码:
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 const int MAXN = 500; 6 typedef long long LL; 7 const double PI = acos(-1); 8 LL a[MAXN + 3][MAXN + 3]; 9 10 void input(int &x,int &y, int n) {11 for(int i = 0; i < n; i++) {12 for(int j = 0; j < n; j++) {13 cin >> a[i][j];14 if(a[i][j] == 0) x = i, y = j;15 }16 }17 }18 19 LL sum[MAXN * 2 + 7];20 bool check(int st, int ed) {21 for(int i = st; i < ed; i++) if(sum[i] != sum[i - 1]) return false;22 return true;23 }24 25 int main() {26 ios_base::sync_with_stdio(0); cin.tie(0);27 int n; cin >> n;28 int inx = -1, iny = -1;29 input(inx, iny, n);30 if(n == 1) {31 cout << (LL) 1e18 - 1 << endl;32 return 0;33 }34 int len = 0;35 for(int i = 0; i < n; i++) {36 for(int j = 0; j < n; j++) {37 sum[len] += a[i][j], sum[len + 1] += a[j][i];38 }39 len += 2;40 }41 for(int i = 0; i < n; i++) sum[len] += a[i][i], sum[len + 1] += a[i][n - i - 1];42 len += 2;43 sort(sum, sum + len);44 int end = -1;46 if(n % 2 != 0 && inx == iny && inx == n / 2) end = 4;//分三种情况讨论47 else if(inx == iny || inx == n - 1 - iny) end = 3;48 else end = 2;49 int flag = 0;50 if(check(1, end) && check(end + 1, len)) flag = 1; // 前后各部分的数要都相等51 if(flag == 1) cout<< (sum[len - 1] - sum[0] == 0 ? -1 : sum[len - 1] - sum[0]) << endl;52 else cout << -1 << endl;53 return 0;54 }
Codeforces 711B. Chris and Magic Square
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。