思路:
若x点能到y点,则y能到的点,x全都能到。
解题如梳理乱丝,首先是对已知条件的加工和转化,挖掘对解题有用的隐藏已知条件。
问:若是直接由字符串读到 bitset 里面不行吗?
string a[N];
bitset<N>s[N];
LL ans;
int n;
//输入数据到容器
scanf("%d",&n);
for(int i=0;i<n;i++){
cin>>a[i];
s[i]=bitset<N>(a[i]);
}
答:不行,因为如果这样,s[i][0]是最右边的字符,二进制串是从最右侧开始的。会把串的方向搞反。必须逐个读入。
#include <iostream>
#include <string>
#include <bitset>
using namespace std;
int main (){
bitset<10> a,b;
string s("010011");
a=bitset<10>(s);
cout<<a.to_string()<<endl;//输出全部10个位
for(int i=0;i<6;i++){//for输出部分位
cout<<a[i];//输出的是"110010",反的,因为默认最右侧的是第0位
}
cout<<endl;
for(int i=0;i<s.size();i++){
b[i]=s[i]-'0';
}
for(int i=0;i<6;i++){
cout<<b[i];
}
cout<<endl;//这样才是原样输出
return 0;
}
#include <cstdio>
#include <bitset>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int N=2e3+5;
char a[N][N];
bitset<N>s[N];
LL ans;
int n;
int main(){
//输入数据到容器
scanf("%d",&n);
for(int i=0;i<n;i++)scanf("%s",a[i]);//注意这里是从左至右的读取
//转换已知,整理数据到bitset位集
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
s[i][j]=a[i][j]-'0';
s[i][i]=1;
}
}
//y列代表能到y点为1,x行代表x可以到的点
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
//位或作用置1,根据s[i]中是1的位,把s[j]中对应位置1
if(s[j][i]==1) s[j]|=s[i];
}
}
for(int i=0;i<n;i++){
ans+=s[i].count();//把位集s[i]中1的个数累加到ans里
}
printf("%lld\n",ans);
return 0;
}