bitset在acm中的应用

ps：最近碰到一些用bitset优化常数的题目,以前也有接触但是都没有记下来,所以来写一篇博文记录以后碰到的类似的题目。

应用一：优化boolean multiplication

在做dp的时候,有时候会需要将两个dp矩阵相乘,且矩阵的元素都是bool型。

计算矩阵A*B=C C[i,j]=1 当且仅当存在k,A[i,k]=1 && B[k][j]=1 。

直接算需要O(n³)的时间。可以用bitset 优化常数。做法如下：

 bitset<N> A[N],B[N],C[N];

 void Multi(bitset<N> A[],bitset<N> B[],bitset<N> C[])

 {

     for (int i=;i<N;i++)

     {

         for (int j=;j<N;j++)

         {

             if (A[i][j]) C[i]|=B[j];

         }

     }

 }

大致思想是：

如果A[i][j]=1, C[i][k] |= A[i][j] & B[j][k] <-> C[i][k] |= B[j][k] 相当于把B的第j行拿去和C的第i行做一次或操作。

题目：

http://codeforces.com/contest/781/problem/D

该题的dp矩阵是boolean矩阵,转移的时候可以用bitset来优化boolean multiplication。

 #include <iostream>

 #include <string>

 #include <cstring>

 #include <map>

 #include <cmath>

 #include <set>

 #include <bitset>

 using namespace std;

 typedef long long ll;

 #define N 510

 bitset<N> dp[][][N];

 int main()

 {

     //freopen("in.in","r",stdin);

     //freopen("out.out","w",stdout);

     int n,m,x,y,z;

     scanf("%d%d",&n,&m);

     while (m--)

     {

         scanf("%d%d%d",&x,&y,&z);

         x--,y--,dp[][z][x][y]=;

     }

     for (int l=;l<=;l++)

     {

         for (int i=;i<n;i++)

         {

             for (int j=;j<n;j++)

             {

                 if (dp[l-][][i][j]) dp[l][][i]|=dp[l-][][j];

                 if (dp[l-][][i][j]) dp[l][][i]|=dp[l-][][j];

             }

         }

     }

     ll ans=; set<int> S; S.insert();

     for (int l=,w=;l>= && ans<=1e18;l--)

     {

         set<int> SS;

         for (set<int>::iterator iter=S.begin();iter!=S.end();iter++)

         {

             int x=*iter;

             for (int j=;j<n;j++)  if (dp[l][w][x][j]) SS.insert(j);

         }

         if (!SS.empty()) ans+=1ll<<l,S=SS,w^=;

     }

     if (ans>1e18) ans=-;

     printf("%I64d\n",ans);

     return ;

 }

待补充...

巴特西

bitset在acm中的应用

最新文章

热门文章