首页 > 代码库 > 2014多校第五场1010 || HDU 4920 Matrix multiplication（矩阵乘法优化）

2014多校第五场1010 || HDU 4920 Matrix multiplication（矩阵乘法优化）

2024-07-15 23:40:38   222人阅读

题目链接

题意 ： 给你两个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 }
View Code

 

看一下这个把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 }
View Code

 


联系
我们