首页 > 代码库 > HDU 4920 Matrix multiplication(std::bitset)

HDU 4920 Matrix multiplication(std::bitset)

2024-07-16 01:44:28   218人阅读

题目连接 ：http://acm.hdu.edu.cn/showproblem.php?pid=4920

题意 ：给两个n*n的矩阵A、B，要求算的A*B (答案对3取模)

（比赛的时候一直想不到怎么去消复杂度，在最后的时候想到了用三进制压几位状态(就是几位几位算)应该可以过的，可是敲完比赛也结束。(压6位是可以过的)


正解是bitset搞，第一次接触到bitset这个神器，用起来确实很炫酷。

方法是统计A矩阵mod3后1出现在哪些位置，2出现哪些位置，B也一样，只是A是以一行为一个“状态”， 而B是以一列为一个“状态”，然后&一下，最后.count()统计。

.count()函数似乎速度很快 0.0

 

 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <iostream> 5 #include <bitset> 6 #include <string> 7  8 using namespace std; 9 const int MAXN = 805;10 const int MOD = 3;11 typedef int Mat[MAXN][MAXN];12 Mat A, B, C;13 bitset<MAXN> A1[MAXN], A2[MAXN], B1[MAXN], B2[MAXN];14 15 int main() {16     int n;17     while (scanf("%d", &n) == 1) {18         for (int i = 1; i <= n; i++) {19             A1[i].reset(); B1[i].reset();20             A2[i].reset(); B2[i].reset();21         }22         for (int i = 1; i <= n; i++) {23             for (int j = 1; j <= n; j++) {24                 scanf("%d", &A[i][j]);25                 A[i][j] %= MOD;26             }27         }28         for (int i = 1; i <= n; i++) {29             for (int j = 1; j <= n; j++) {30                 scanf("%d", &B[i][j]);31                 B[i][j] %= MOD;32             }33         }34         for (int i = 1; i <= n; i++) {35             for (int j = 1; j <= n; j++) {36                 if (A[i][j] == 1) {37                     A1[i][j-1] = 1;38                 }else if (A[i][j] == 2) {39                     A2[i][j-1] = 1;40                 }41             }42         }43         for (int j = 1; j <= n; j++) {44             for (int i = 1; i <= n; i++) {45                 if (B[i][j] == 1) {46                     B1[j][i-1] = 1;47                 }else if (B[i][j] == 2){48                     B2[j][i-1] = 1;49                 }50             }51         }52         for (int i = 1; i <= n; i++) {53             for (int j = 1; j <= n; j++) {54                 int a = (A1[i]&B1[j]).count()+(A2[i]&B2[j]).count();55                 int b = (A1[i]&B2[j]).count()+(A2[i]&B1[j]).count();56                 C[i][j] = a + b * 2;57                 printf("%d%c", C[i][j]%MOD, " \n"[j == n]);58             }59         }60     }61     return 0;62 }
View Code

 


联系
我们