【NOIP十连测】[D1T2] Tourist Attractions

相关链接

题目传送门: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/
想一想好像这么写很优越的样子!

2 thoughts to “【NOIP十连测】[D1T2] Tourist Attractions”

  1. 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.

  2. 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!

Leave a Reply

Your email address will not be published. Required fields are marked *