题意 : 给你两个n*n的矩阵,然后两个相乘得出结果是多少。
思路 :一开始因为知道会超时所以没敢用最普通的方法做,所以一直在想要怎么处理,没想到鹏哥告诉我们后台数据是随机跑的,所以极端数据是不可能会有的,而我们一开始一直在想极端数据能接受的方法。。。。。。后来看了鹏哥的做法,就是把是0的地方都跳过就可以了,用矩阵保存前一个非0数的位置是多少。二师兄给我看了一个代码,人家根本没用别的优化,直接将最里层k的循环提到了最外层,然后就AC了,对此我表示无语。
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 5 using namespace std ; 6 7 int a[810][810],b[810][810]; 8 int a1[810][810],b1[810][810] ; 9 int c[810][810] ; 10 11 int main() 12 { 13 int n ; 14 while(~scanf("%d",&n)) 15 { 16 memset(a,0,sizeof(a)) ; 17 memset(b1,0,sizeof(b1)) ; 18 memset(c,0,sizeof(c)) ; 19 memset(a1,0,sizeof(a1)) ; 20 memset(b,0,sizeof(b)) ; 21 for(int i = 1 ; i <= n ; i++) 22 { 23 for(int j = 1 ; j <= n ; j++) 24 { 25 scanf("%d",&a[i][j]) ; 26 a[i][j] %= 3 ; 27 } 28 } 29 for(int i = 1 ; i <= n ; i++) 30 { 31 for(int j = 1 ; j <= n ; j++) 32 { 33 scanf("%d",&b[i][j]) ; 34 b[i][j] %= 3 ; 35 } 36 } 37 for(int i = 1 ; i <= n ; i++) 38 { 39 int pre = -1 ; 40 for(int j = n ; j >= 0 ; j--) 41 { 42 a1[i][j] = pre ; 43 if(a[i][j]) 44 pre = j ; 45 } 46 } 47 for(int i = 1 ; i <= n ; i++) 48 { 49 int pre = -1 ; 50 for(int j = n ; j >= 0 ; j--) 51 { 52 b1[i][j] = pre ; 53 if(b[i][j]) 54 pre = j ; 55 } 56 } 57 for(int i = 1 ; i <= n ; i++) 58 { 59 for(int j = a1[i][0] ; j + 1 ; j = a1[i][j]) 60 { 61 for(int k = b1[j][0] ; k + 1 ; k = b1[j][k]) 62 { 63 c[i][k] += a[i][j]*b[j][k] ; 64 } 65 } 66 } 67 for(int i = 1 ; i <= n ; i++) 68 { 69 for(int j = 1 ; j <= n ; j++) 70 { 71 printf("%d",c[i][j]%3) ; 72 if(j != n) 73 printf(" ") ; 74 } 75 printf("\n") ; 76 } 77 } 78 return 0 ; 79 }
看一下这个把k放在最外层的代码吧。。。。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<cmath> 5 using namespace std; 6 const int N = 805; 7 int a[N][N], b[N][N], ans[N][N]; 8 int main() 9 { 10 int n, i, j, k; 11 while(~scanf("%d",&n)) 12 { 13 for(i = 1; i <= n; i++) 14 for(j = 1; j <= n; j++) 15 { 16 scanf("%d",&a[i][j]); 17 a[i][j] %= 3; 18 } 19 for(i = 1; i <= n; i++) 20 for(j = 1; j <= n; j++) 21 { 22 scanf("%d",&b[i][j]); 23 b[i][j] %= 3; 24 } 25 memset(ans, 0, sizeof(ans)); 26 for(k = 1; k <= n; k++) //经典算法中这层循环在最内层,放最内层会超时,但是放在最外层或者中间都不会超时,不知道为什么 27 for(i = 1; i <= n; i++) 28 for(j = 1; j <= n; j++) 29 { 30 ans[i][j] += a[i][k] * b[k][j]; 31 //ans[i][j] %= 3; //如果在这里对3取余,就超时了 32 } 33 for(i = 1; i <= n; i++) 34 { 35 for(j = 1; j < n; j++) 36 printf("%d ", ans[i][j] % 3); 37 printf("%d\n", ans[i][n] % 3); 38 } 39 } 40 return 0; 41 }
2014多校第五场1010 || HDU 4920 Matrix multiplication(矩阵乘法优化),布布扣,bubuko.com
2014多校第五场1010 || HDU 4920 Matrix multiplication(矩阵乘法优化)
原文:http://www.cnblogs.com/luyingfeng/p/3893140.html