题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4920
题目的意思就是求两个矩阵的乘法。只是该题目的时间复杂度要求比较要个。按照平常的解法是无法快速求得答案的。这里需要用一种。比较高大上的解法。有关硬件的。对于程序员来说,涉及硬件方面的东西总是令他们头疼的。。我也是。
这里面有一个论文+一个博客讲的很好。
博客:以矩阵乘法为例,了解cpu cache对程序性能的影响
讲的都很详细。
实际操作上,就是将本来的第三层循环和第二层循环交换一下既可以了。
Code:
#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; const int N = 805; int n, a[N][N], b[N][N], c[N][N]; template <class T> inline void scan_d(T &ret) { char c; ret=0; while((c=getchar())<'0'||c>'9'); while(c>='0'&&c<='9') ret=ret*10+(c-'0'),c=getchar(); } inline void out(int x) { if(x>9) out(x/10); putchar(x%10+'0'); } void a_b(){ for(int i = 1; i <= n; i ++){ for(int k = 1; k <= n; k ++){ for(int j = 1; j <= n; j ++) c[i][j] += a[i][k] * b[k][j]; } } } int main(){ while(~scanf("%d", &n)){ for(int i = 1; i <= n; i ++){ for(int j = 1; j <= n; j ++){ scan_d(a[i][j]); a[i][j] %= 3; c[i][j] = 0; } } for(int i = 1; i <= n; i ++){ for(int j = 1; j <= n; j ++){ scan_d(b[i][j]); b[i][j] %= 3; } } a_b(); for(int i = 1; i <= n; i ++){ for(int j = 1; j <= n; j ++){ out(c[i][j] % 3); if(j == n) printf("\n"); else printf(" "); } } } return 0; }
加了一个输入输出的外挂,在时间复杂度上没有什么实质上的提高。。。。