首页 > 代码库 > HDU 4920(杭电多校训练#5 1010 题) Matrix multiplication(不知道该挂个什么帽子。。。)
HDU 4920(杭电多校训练#5 1010 题) Matrix multiplication(不知道该挂个什么帽子。。。)
题目地址:HDU 4920
对这个题简直无语到极点。。。居然O(n^3)的复杂度能过。。。。方法有三。。
1:进行输入优化和输出优化。。(前提是你的输入优化不能太搓。。。)
2:利用缓存优化。。详情请看该论文。大体就是将后两个for循环换过来,让坐标改变的频率降下来。
3:叉姐题解中说的正规方法。。利用biset存储,进行预处理。。(其实我还没看懂。。
我只写了个第二种。。。代码如下,共勉。。神奇的小代码。。
#include <iostream> #include <cstdio> #include <string> #include <cstring> #include <stdlib.h> #include <math.h> #include <ctype.h> #include <queue> #include <map> #include <set> #include <algorithm> 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<n;j++) { printf("%d ",mp[i][j]%3); } printf("%d\n",mp[i][n]%3); } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。