首页 > 代码库 > POJ_2941_矩阵
POJ_2941_矩阵
题目描述:
每组数据给定一个n*n的矩阵,选定不同行不同列的n个元素,求和,若所有选法所产生的和相等,则输出 homogeneous,否则输出not homogeneous。
描述:
数据挺大,爆搜肯定超时,于是有下面的递推的规律。
当n为3时,有这么一个矩阵,数字表示编号。
1 | 2 | 3 |
4 | 5 | 6 |
7 | 8 | 9 |
我们只需要让它的每个2阶的子矩阵符合题目条件,则它必然符合条件。
1 | 2 |
4 | 5 |
2 | 3 |
5 | 6 |
4 | 5 |
7 | 8 |
5 | 6 |
8 | 9 |
然后就可以发现一个规律,对于任意一个n阶矩阵,只要它的所有n-1阶子矩阵是homogeneous的,则它便是homogeneous的,进一步可得,只要它所有的2阶子矩阵符合两对角线相乘相等即可。
这样,问题便解决了。最后,我提交程序的时候却是一直超时!一个O(n^2)的程序,不至于啊= =。然后修改了无数遍,最终发现了问题所在,iostream库中的cin和cout在与stdin同步的情况下,效率比scanf和printf相差很大,最大可达十几倍,可怕!改成scanf和printf之后再提交便AC了。可见,对于含有大量数据的题目,慎用cin和cout啊= =!
#include<iostream>#include<cstdio>using namespace std;int a[1005][1005];int main(){ int n; while(~scanf("%d",&n) && n) { int flag = 1; for(int i = 1;i <= n;i++) { for(int j = 1;j <= n;j++) scanf("%d",&a[i][j]); } for(int i = 1;i < n;i++) { for(int j = 1;j < n;j++) { if(a[i][j]+a[i+1][j+1] != a[i][j+1]+a[i+1][j]) { flag = 0; goto there; } } } there: if(flag) printf("homogeneous\n"); else printf("not homogeneous\n"); } return 0;}
POJ_2941_矩阵
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。