[Data Structure] [Status Compression] Brush

Nothing else, I just want to remember those functions by myself

1>floyd+bitset optimization

#include 

#include #include

using namespace std;

int n;

const int N=2003;

char s[N];

bitset  bs[N]; int main( )

{

 scanf("%d",&n);

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

 {

 scanf("%s",s+1);

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

 if(s[j]=='< span style="color: #800000;">1') bs[ i][j]=1;

 bs[i][i]=1;

}



 int ans=0;

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

 {

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

 if(bs[i][j])

 bs[i]|= bs[j];



 ans+=bs[i].count();

}



 printf("%d
",ans);

 return 0;

}

#include

#include #include

using namespace std;

int n;

const int N=2003;

char s[N];

bitset  bs[N]; int main( )

{

 scanf("%d",&n);

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

 {

 scanf("%s",s+1);

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

 if(s[j]=='< span style="color: #800000;">1') bs[ i][j]=1;

 bs[i][i]=1;

}



 int ans=0;

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

 {

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

 if(bs[i][j])

 bs[i]|= bs[j];



 ans+=bs[i].count();

}



 printf("%d
",ans);

 return 0;

}