相关链接
题目传送门:http://oi.cyo.ng/wp-content/uploads/2016/10/noip_test1_statements.pdf
解题报告
虽然没能A掉
但明明是70分的dp却交成了40分的暴力
仍然不高兴 >︿<
四个点的话,就是三条边
考虑枚举中间的那一条边
则其对答案的贡献就是两点入度的乘积
但3元环不符合题意
于是搞一搞bitset可以在O(n/32)的时间复杂度内统计三元环
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 1500+9; LL vout; int n,in[N]; bitset<N> edg[N]; inline int read(){ char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret*f; } int main(){ n = read(); char pat[N]; for (int j=1;j<=n;j++) { scanf("%s",pat+1); for (int i=1;i<=n;i++) edg[j][i] = pat[i] - '0', in[i] += pat[i] - '0'; } for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if (edg[i][j]) { vout += (LL)(in[i] - 1) * (in[j] - 1); vout -= (edg[i] & edg[j]).count(); } printf("%lld\n",vout); return 0; }
最后来撸一发Claris的手写bitset:http://paste.ubuntu.com/23262667/
想一想好像这么写很优越的样子!
Heya i’m for the first time here. I found this board and I find It really useful & it helped me out a lot. I hope to give something back and help others like you aided me.
Do you mind if I quote a couple of your articles as long as I provide credit and sources back to your blog? My website is in the exact same area of interest as yours and my visitors would really benefit from a lot of the information you present here. Please let me know if this alright with you. Regards!