Triangle题解
前情提要
看博不点赞，ac少一半
小插曲
因为找不到题解差点心态炸了，还好有大佬指点，我来造福想不出这道题的人啦
题目描述：给你一个无向图，让你数里面三角形的个数，其中三角形三个顶点a,b,c序号要满足a<b<c
思路
很明显，暴力直接n* n *n,这里考虑优化、
首先枚举其中的的两个点是不可能少的（不然能给你3000?)，考虑第三个点的优化
我的思路：都已知两个点了，第三个点要求其中两个点都要和他有连线，其中一个没有就不行，然后我想了下所有的所学，好像&和这个很像的
是的，那么就这么继续，假设我已知道两个点所有连着的点，我们记作两个bool，s1,s2，那么他们有的公共点就是s1&s2中1的个数！用bitset，不仅可以降时间复杂度，还可以用.count很快算出来1的数量
真不戳，那三角形的a<b<c怎么限制呢？
首先在外面两个点的循环中我就不多赘述了，假若外面循环我们始终有点i（序号）<点j（序号），那么在二重循环里面的s1&s2(我们将结果设为S3),将S3右移j位就可以消掉了
（大不了我全部算出来再/3)(应该？)
代码如下
#include<bits/stdc++.h>
using namespace std;
int n;
string s;
bitset<3005> a[3005],si;
int main(){
ios::sync_with_stdio(false);
cin >> n;
for(int i=1;i<=n;i++) {
cin >> s;
s=" "+s;
for(int j=1;j<=n;j++){
//cin >> s;// can not cin >> ai j
a[i][j]=s[j]-'0';//jth 0 or 1
}
}
long long ans = 0;
for(int i=1;i<=n;i++) {
for(int j=i+1;j<=n;j++) {
if(!a[i][j]){
continue;
}
si=a[i]&a[j];// if all have 1,then they have a triangle
si>>=j;// make sure it is bigger than j
ans+=si.count();
}
}
cout<<ans;
return 0;
}