首页 > 代码库 > 2014多校第五场1010 || HDU 4920 Matrix multiplication（矩阵乘法优化）
2014多校第五场1010 || HDU 4920 Matrix multiplication（矩阵乘法优化）
题目链接
题意 ： 给你两个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 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。