HDU 4920 水

本文主要是介绍HDU 4920 水，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

矩阵乘法

因为答案要MOD3，所以矩阵中会有很多值为0，对这些不乘就行了，，，，，，，这样也能水过。。。

BUT ：

这样写会超时：for (int i=1; i<=n; i++)for (int j=1; j<=n; j++)for (int k=1; k<=n; k++)c[i][j]+=a[i][k]*b[k][j];这样写就能过:for (int k=1; k<=n; k++)for (int i=1; i<=n; i++)for (int j=1; j<=n; j++)c[i][j]+=a[i][k]*b[k][j];

BECAUSE：

我们知道内存中二维数组是以行为单位连续存储的，逐列访问将会每次跳1000*4(bytes)。根据cpu cache的替换策略，将会有大量的cache失效。
时间居然会相差很多。 可见利用好cpu cache优化我们的程序，是非常有必要掌握的技能。
平时写程序时，也应当尽量使cpu对内存的访问，是尽可能连续的。

#include "stdio.h"
#include "string.h"
int a[810][810],b[810][810],c[810][810];
int main()
{int n,i,j,k;while (scanf("%d",&n)!=EOF){for (i=1;i<=n;i++)for (j=1;j<=n;j++){scanf("%d",&a[i][j]);a[i][j]%=3;}for (i=1;i<=n;i++)for (j=1;j<=n;j++){scanf("%d",&b[i][j]);b[i][j]%=3;}memset(c,0,sizeof(c));for (k=1;k<=n;k++)for (i=1;i<=n;i++)if (a[i][k]!=0)for (j=1;j<=n;j++){c[i][j]+=a[i][k]*b[k][j]%3;}for (i=1;i<=n;i++){for (j=1;j<n;j++)printf("%d ",c[i][j]%3);printf("%d\n",c[i][j]%3);}}return 0;
}

这篇关于HDU 4920 水的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---