题意 ： 给你两个n*n的矩阵，然后两个相乘得出结果是多少。
思路 ：一开始因为知道会超时所以没敢用最普通的方法做，所以一直在想要怎么处理，没想到鹏哥告诉我们后台数据是随机跑的，所以极端数据是不可能会有的，而我们一开始一直在想极端数据能接受的方法。。。。。。后来看了鹏哥的做法，就是把是0的地方都跳过就可以了，用矩阵保存前一个非0数的位置是多少。二师兄给我看了一个代码，人家根本没用别的优化，直接将最里层k的循环提到了最外层，然后就AC了，对此我表示无语。
#include <cstdio>
#include <cstring>
#include <iostream> using namespace std ; int a[][],b[][];
int a1[][],b1[][] ;
int c[][] ; int main()
{
int n ;
while(~scanf("%d",&n))
{
memset(a,,sizeof(a)) ;
memset(b1,,sizeof(b1)) ;
memset(c,,sizeof(c)) ;
memset(a1,,sizeof(a1)) ;
memset(b,,sizeof(b)) ;
for(int i = ; i <= n ; i++)
{
for(int j = ; j <= n ; j++)
{
scanf("%d",&a[i][j]) ;
a[i][j] %= ;
}
}
for(int i = ; i <= n ; i++)
{
for(int j = ; j <= n ; j++)
{
scanf("%d",&b[i][j]) ;
b[i][j] %= ;
}
}
for(int i = ; i <= n ; i++)
{
int pre = - ;
for(int j = n ; j >= ; j--)
{
a1[i][j] = pre ;
if(a[i][j])
pre = j ;
}
}
for(int i = ; i <= n ; i++)
{
int pre = - ;
for(int j = n ; j >= ; j--)
{
b1[i][j] = pre ;
if(b[i][j])
pre = j ;
}
}
for(int i = ; i <= n ; i++)
{
for(int j = a1[i][] ; j + ; j = a1[i][j])
{
for(int k = b1[j][] ; k + ; k = b1[j][k])
{
c[i][k] += a[i][j]*b[j][k] ;
}
}
}
for(int i = ; i <= n ; i++)
{
for(int j = ; j <= n ; j++)
{
printf("%d",c[i][j]%) ;
if(j != n)
printf(" ") ;
}
printf("\n") ;
}
}
return ;
}
看一下这个把k放在最外层的代码吧。。。。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = ;
int a[N][N], b[N][N], ans[N][N];
int main()
{
int n, i, j, k;
while(~scanf("%d",&n))
{
for(i = ; i <= n; i++)
for(j = ; j <= n; j++)
{
scanf("%d",&a[i][j]);
a[i][j] %= ;
}
for(i = ; i <= n; i++)
for(j = ; j <= n; j++)
{
scanf("%d",&b[i][j]);
b[i][j] %= ;
}
memset(ans, , sizeof(ans));
for(k = ; k <= n; k++) //经典算法中这层循环在最内层，放最内层会超时，但是放在最外层或者中间都不会超时，不知道为什么
for(i = ; i <= n; i++)
for(j = ; j <= n; j++)
{
ans[i][j] += a[i][k] * b[k][j];
//ans[i][j] %= 3; //如果在这里对3取余，就超时了
}
for(i = ; i <= n; i++)
{
for(j = ; j < n; j++)
printf("%d ", ans[i][j] % );
printf("%d\n", ans[i][n] % );
}
}
return ;
}