T1
题目描述
实现矩阵相乘函数,暂不考虑整型溢出,请尽可能优化运行速度。
$0 < M, K, N < 1000$
$C[M][N] = A[M][K] * B[K][N]$
输入描述
输入$M, K, N$以及矩阵$A$和矩阵$B$的值
输出描述
输出矩阵C的值
示例1
样例输入
2 3 3
1 2 3
1 2 3
1 1
1 1
1 1
样例输出
6 6
6 6
算法
(?) $O(n ^ 3)$
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m, k;
int a[N][N], b[N][N], c[N][N];
int main() {
cin >> m >> k >> n;
for (int i = 1; i <= m; i ++ )
for (int j = 1; j <= k; j ++ )
cin >> a[i][j];
for (int i = 1; i <= k; i ++ )
for (int j = 1; j <= n; j ++ )
cin >> b[i][j];
for (int i = 1; i <= m; i ++ )
for (int j = 1; j <= n; j ++ )
for (int u = 1; u <= k; u ++ )
c[i][j] += a[i][u] * b[u][j];
for (int i = 1; i <= m; i ++ ) {
for (int j = 1; j <= n; j ++ )
cout << c[i][j] << ' ';
cout << endl;
}
return 0;
}
T2
题目描述
假设,小米商城有卖空盒子,各种大小的正方形空盒子。对于$i$($1 < i \leq n$),$a_i$是正方形盒子的边长。如果有顾客采购多个空盒子,快递打包的时候,可以将嵌套打包以节约成本。如果满足以下三个条件,盒子$i$可以放到$j$中:
1、盒子$i$没有放在另一个盒子里
2、盒子$j$不包含任何其它盒子
3、$a_i < a_j$
现在有顾客采购了$n$个空盒子。工作人员想知道,如何装箱,能使包裹数量最少。
输入描述
第一行包含一个整数$n$($1 \leq n < 5000$)顾客购买箱子的数量。
第二行包含了$n$个整数,($1 \leq a_i \leq 10^9$),$a_i$是盒子的边长。
输出描述
打印包裹的最小数量。
示例1
样例输入
4
4 2 4 3
样例输出
2
提示
在这个示例中,可以将盒子2放入盒子3中,将盒子4放入盒子1中
算法
(哈希表) $O(n)$
找众数
C++ 代码
#include <bits/stdc++.h>
using namespace std;
int n;
unordered_map<int, int> cnt;
int main() {
cin >> n;
while (n -- ) {
int x; cin >> x;
cnt[x] ++ ;
}
int ret = 0;
for (auto c: cnt) ret = max(ret, c.second);
cout << ret;
return 0;
}
T1可以先预处理嘛?
这题数据出的没那么严,我AC了,但是最优解法我还是不会hh
矩阵乘貌似可以用 $\text{FFT}$ 暴力优化?复杂度 $O(n^2 \log n)$
%%%
算法导论里分治那一节讲了矩阵乘法的优化解法Strassen,复杂度是O(n^log7),不过我看不懂orz
我也不懂hh