hdu - 4920 - Matrix multiplication(缓存优化+开挂)
2024-08-27 06:22:16
题意:求两个n x n的矩阵相乘后模3的结果,n <= 800。
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4920
——>>呀呀。。
1、3层计算的for进行缓存优化,依据CPU的L1级缓存的实现原理,降低缓存的变更。假设每次都计算完一个单元格的结果再计算下一个单元格的结果。那么被乘矩阵的訪问就会频繁地更新缓存,使效率非常低。。
2、输入开挂,G++提效500ms+。。
3、对乘法进行剪枝。。
没有第1个操作,后果是严重的。。
n^3的复杂度A过,但。此不是正解。。
#include <cstdio>
#include <cstring> const int MAXN = 800 + 10; int n;
int A[MAXN][MAXN], B[MAXN][MAXN], mtRet[MAXN][MAXN]; int ReadInt()
{
int nRet = 0;
char cIn; while ((cIn = getchar()) >= '0' && cIn <= '9')
{
nRet = nRet * 10 + cIn - '0';
} return nRet % 3;
} void Read()
{
getchar();
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= n; ++j)
{
A[i][j] = ReadInt();
}
}
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= n; ++j)
{
B[i][j] = ReadInt();
}
}
} void Solve()
{
memset(mtRet, 0, sizeof(mtRet));
for (int i = 1; i <= n; ++i)
{
for (int k = 1; k <= n; ++k)
{
if(!A[i][k]) continue;
for (int j = 1; j <= n; ++j)
{
mtRet[i][j] += A[i][k] * B[k][j];
}
}
}
} void Print()
{
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j < n; ++j)
{
printf("%d ", mtRet[i][j] % 3);
}
printf("%d\n", mtRet[i][n] % 3);
}
} int main()
{
while (scanf("%d", &n) == 1)
{
Read();
Solve();
Print();
}
return 0;
}
最新文章
- CodeForces - 261B Maxim and Restaurant
- 【转】Java开发中JDBC连接数据库代码和步骤总结
- js 实现进度条功能。
- 浏览器angent分析工具
- [设计模式] javascript 之 迭代子模式
- 调整Excel的打印线
- transform的使用
- android线程间通讯
- java读写中文文件
- 什么是MBeanServer
- G - Reduced ID Numbers(第二季水)
- Android 之 Fragment
- 使用FreeHttp强制登出微信公众号登陆状态(实现~原理)
- 010_TCP queue的研究
- Druid(新版starter)在SpringBoot下的使用以及优点
- 对象copy的两种方式--序列化--clone
- http://ctf.bugku.com/challenges#%E9%80%86%E5%90%91%E5%85%A5%E9%97%A8:bugku--逆向入门
- paired-end reads的拼接
- 新一代Java模板引擎Thymeleaf
- 常用DOS命令和Linux命令
热门文章
- Coursera Algorithms week3 归并排序 练习测验: Merging with smaller auxiliary array
- A Round Peg in a Ground Hole(圆与凸包)
- 最短路径问题(floyd)
- codevs1688 求逆序对(权值线段树)
- HTML 打印 换页
- Cracking the Coding Interview 8.7
- F - Micro-World(简单模拟)
- xhtml1-transitional.dtd
- 【python】os.getcwd和getcwdu
- 【sqli-labs】 less41 GET -Blind based -Intiger -Stacked(GET型基于盲注的堆叠查询整型注入)