首页 > 代码库 > Codeforces 821A Okabe and Future Gadget Laboratory 题解
Codeforces 821A Okabe and Future Gadget Laboratory 题解
此文为博主原创题解，转载时请通知博主，并把原文链接放在正文醒目位置。
题目链接：http://codeforces.com/problemset/problem/821/A
时间限制：2秒
空间限制：256M
Okabe要改进他的实验室。实验室用一个n*n的正方形网格表示（n为正整数）。他认为，一个“好实验室”的网格内每一个不等于1的数字都可以用同一行和同一列的某个数字之和表示。换句话说，对于任意x,y（1 ≤ x, y ≤ n 且 ax, y ≠ 1,），存在两个数s和t，使得ax, y = ax, s + at, y，其中ai, j 表示第i行第j列的整数。
帮助Okabe找出以下的实验室中哪个符合他的要求。
输入
第一行描述实验室的大小n(1 ≤ n ≤ 50)
接下来的n行中，每行有n个整数（中间用空格隔开），表示实验室网格。
第i行第j列的整数是ai, j (1 ≤ ai, j ≤ 105).
输出
如果实验室符合要求，输出“Yes”，否则输出“No”
不考虑大小写问题
样例输入#1
3
1 1 2
2 3 1
6 4 1
样例输出#1
Yes
样例输入#2
3
1 5 2
1 1 1
1 2 3
样例输出#2
No
注释
在样例1中，左下角的6可以表示为2和4的和。同样地，网格中所有非1的数字都可以分别用同行、同列的两数之和表示，因此输出“Yes”.
在样例2中，5不能被表示为同行同列的两数字之和，因此输出“No”.
分析：
空间和时间都很充足，直接无脑暴力算_(:з」∠)_
特别注意的是如果输入所有的数字都是1，也应该输出“Yes”.
丑陋的AC代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cmath> 5 6 using namespace std; 7 int map[60][60]; 8 bool flag,ok = true; 9 10 int main()11 {12 int n;13 scanf("%d",&n);14 for(int i = 1;i <= n;i ++)15 for(int j = 1;j <= n;j ++)16 {17 scanf("%d",&map[i][j]);18 if(map[i][j] != 1)19 ok = false;20 }21 if(ok)22 {23 printf("Yes\n");24 return 0;25 }26 for(int i = 1;i <= n;i ++)27 for(int j = 1;j <= n;j ++)28 {29 if(map[i][j] == 1)30 continue;31 else32 {33 flag = false;34 for(int a = 1;a <= n;a ++)35 {//固定列 36 if(a == j) continue;37 for(int b = 1;b <= n;b ++)38 {39 if(b == i) continue;40 if(map[i][a] + map[b][j] == map[i][j])41 { flag = true;break; }42 }43 if(flag) break;44 }45 if(!flag)46 {47 printf("No\n");48 return 0;49 }50 }51 }52 if(flag) printf("Yes\n");53 return 0;54 }
Codeforces 821A Okabe and Future Gadget Laboratory 题解
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。