HDU 4920（杭电多校训练#5 1010 题） Matrix multiplication(不知道该挂个什么帽子。。。）...-白红宇

HDU 4920（杭电多校训练#5 1010 题） Matrix multiplication(不知道该挂个什么帽子。。。）...

阅读量：5056 次

发布时间：2019-06-12

本文共 894 字，大约阅读时间需要 2 分钟。

题目地址：

对这个题简直无语到极点。

。

。竟然O（n^3）的复杂度能过。。。。方法有三。。

1：进行输入优化和输出优化。

。

（前提是你的输入优化不能太搓。。。）

2：利用缓存优化。。详情请看。大体就是将后两个for循环换过来，让坐标改变的频率降下来。

3：叉姐题解中说的正规方法。

。利用biset存储，进行预处理。

。（事实上我还没看懂。。

我仅仅写了个另外一种。。

。代码例如以下。共勉。。奇妙的小代码。。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #include 
               
                using namespace std;int a[900][900], b[900][900], mp[900][900];int main(){ int n, i, j, k, x; while(scanf("%d",&n)!=EOF) { for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { scanf("%d",&x); a[i][j]=x%3; } } for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { scanf("%d",&x); b[i][j]=x%3; } } memset(mp,0,sizeof(mp)); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { for(k=1;k<=n;k++) { mp[i][k]+=a[i][j]*b[j][k]; } } } for(i=1;i<=n;i++) { for(j=1;j