HDU 4920 Matrix multiplication(bitset)

HDU 4920 Matrix multiplication

题目链接

题意:给定两个矩阵,求这两个矩阵相乘mod 3

思路:没什么好的想法,就把0的位置不考虑。结果就过了。然后看了官方题解,上面是用了bitset这个东西,能够用来存大的二进制数,那么对于行列相乘。事实上就几种情况,遇到0都是0了,1 1得1,2 1,1 2得2,2 2得1。所以仅仅要存下行列1和2存不存在分别表示的二进制数。然后取且bitcount一下的个数,就能够计算出对应的数值了

代码:

暴力:

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std; inline void scanf_(int &num)//无负数
{
char in;
while((in = getchar()) > '9' || in < '0') ;
num = in - '0';
while(in = getchar(),in >= '0' && in <= '9')
num *= 10,num += in - '0';
} const int N = 805; int n; int a[N][N], av[N][N], an[N], b[N][N], bv[N][N], bn[N], c[N][N]; int main() {
while (~scanf("%d", &n)) {
int num;
memset(an, 0, sizeof(an));
memset(bn, 0, sizeof(bn));
memset(c, 0, sizeof(c));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf_(num);
num %= 3;
if (num == 0) continue;
av[j][an[j]] = i;
a[j][an[j]++] = num;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf_(num);
num %= 3;
if (num == 0) continue;
bv[i][bn[i]] = j;
b[i][bn[i]++] = num;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < an[i]; j++) {
for (int k = 0; k < bn[i]; k++) {
int x = av[i][j], y = bv[i][k];
c[x][y] = (c[x][y] + a[i][j] * b[i][k]) % 3;
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n - 1; j++)
printf("%d ", c[i][j]);
printf("%d\n", c[i][n - 1]);
}
}
return 0;
}

bitset:

#include <cstdio>
#include <cstring>
#include <string>
#include <bitset>
using namespace std; const int N = 805;
int n, num;
bitset<800> row[N][2], col[N][2]; int main() {
while (~scanf("%d", &n)) {
for (int i = 0; i < n; i++) {
row[i][0].reset();
row[i][1].reset();
col[i][0].reset();
col[i][1].reset();
for (int j = 0; j < n; j++) {
scanf("%d", &num);
if (num % 3 == 1)
row[i][0].set(j, 1);
if (num % 3 == 2)
row[i][1].set(j, 1);
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &num);
if (num % 3 == 1)
col[j][0].set(i, 1);
if (num % 3 == 2)
col[j][1].set(i, 1);
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int ans = 0;
ans += (row[i][0]&col[j][0]).count();
ans += 2 * (row[i][1]&col[j][0]).count() + 2 * (row[i][0]&col[j][1]).count();
ans += (row[i][1]&col[j][1]).count();
printf("%d%c", ans % 3, j == n - 1 ? '\n' : ' ');
}
}
}
return 0;
}
上一篇:运算符与选择结构的练习(if / if elseif / switch)


下一篇:matlab快速入门(21):决策分支